Éléments d’Informatique Théorique Série 8

L’espoir de cette série est d’aider à la compréhension de divers concepts vus jusqu’ici, en posant les problèmes sous un angle un peu différent de l’angle habituel: deux points de vue vallent mieux qu’un! Elle est destinée à être faite pendant les TPs de façon interactive, et n’est donc pas un document complet en soi.

Exercice 8.1

Définition 1 Une TM non déterministe est un algorithme M avec deux bandes d’entrées: la bande d”’entrée” et la bande de “choix”. On définit L(M) par: L(M) := {x | ∃y M(x, y) = 1}.

Ecrire un algorithme A (dans votre langage de prédilection) prenant en paramètre une TM non déterministe M, t.q. [∀x A_{M}(x) = 1] ⇔ [x ∈ L(M)].

Exercice 8.2 Démontrer informellement que cette définition de TM correspond à celle du cours.

Exercice 8.3 Donner la définition informelle d’un énumérateur. Matériel à disposition: un ordinateur et une imprimante...

Exercice 8.4 Soit M une TM. Quel est le langage énuméré par un énumérateur exécutant l’algorithme A suivant:

    Begin(A)

i := 0;

     While ( i ≥ 0 ) {
         Compute s_{i}; # s_{i} est le ième mot de l'ordre canonique.
         Compute M(s_{i});

If ( M(s_{i}) = 1 ) { Print s_{i} };

i := i + 1;

}

End(A)

Exercice 8.5 Montrer qu’un langage peut être énuméré par un enumerateur ssi il peut être accepté par une TM.

Exercice 8.6 Quel est le “problème” avec la TM suivante, qui semble \underline{décider} le langage des polynômes avec au moins une racine.

Input: p un polynôme multivarié.

• Soit p = p(X_{1}, …, X_{k}).

• Essayer chaque valeurs possibles de (x_{1}, …, x_{k}) ∈ ℕ^{k}.

• Evaluer p sur chacunes de ces valeurs.

• Si ∃ une valeur t.q. p(x_{1}, …, x_{k}) = 0, accepter.

• Sinon rejeter.

Exercice 8.7 Imaginez un protocole permettant d’accepter les langages acceptés par une TM non déterministe. Matériel à disposition: un “vérificateur”, qui est un ordinateur. Personel à disposition: M.Dupont, qui est capable d’intuition... Monsieur Dupont peut partler à l’ordinateur, (via le clavier), et est capable d’une intuition surprenante, néanmoins, il arrive que son intuition le trompe, et qu’il fasse une erreur. (Heureusement, le “vérificateur” ne se laisse pas tromper, lui).

Exercice 8.8 Quels sont les langages acceptés par l’AFN et la TM suivants:

Attention, les deux lanagages sont différents!!!