Exercices indécidabilité

Exercice 1

Soit M une machine de Turing donnée (par exemple une machine qui accepte tous les mots se terminant par la lettre a).

Représenter graphiquement la machine M_ε qui efface le mot écrit sur son ruban, repositionne la tête de lecture au début du ruban puis se comporte exactement comme M.
Soit w un mot donné (par exemple abba). Représenter graphiquement la machine M_w qui écrit w sur le ruban (en effaçant tout mot qui s'y trouverait), repositionne la tête de lecture au début du ruban puis se comporte exactement comme M.

Exercice 2

Montrer que déterminer si une MT s'arrête sur le mot vide est indécidable (problème de l'arrêt sur le mot vide). Indication : par réduction à H, l'ensemble des couples (M,w) tels que M s'arrête sur w.

Exercice 3

Montrer que déterminer si une MT s'arrête pour au moins un mot d'entrée est indécidable (problème de l'arrêt existentiel). Indication : par réduction au problème de l'arrêt sur le mot vide.

Exercice 4

Montrer que déterminer si une MT s'arrête pour tout mot d'entrée est indécidable (problème de l'arrêt universel). Indication : par réduction au problème de l'arrêt sur le mot vide.

Exercice 5

On a vu en cours que LU, l'ensemble des couples (M,w) tels que M accepte w, est indécidable. Montrer cependant que LU est récursivement énumérable.
Que peut-on en déduire concernant le complément de LU, i.e., l'ensemble des couples (M,w) tels que M n'accepte pas w ?
Soient M1 et M2 deux MT qui terminent toujours. Soient f1 et f2 les deux fonctions calculées par ces machines. Montrer qu'il est impossible de déterminer algorithmiquement si f1=f2. Indication : par réduction au complément de LU.

Exercice 6

Montrer que déterminer si pour tout couple de machines de Turing M1 et M2, il existe un mot w tel que M1 et M2 s'arrêtent sur w est indécidable. Indication : par réduction au problème de l'arrêt sur le mot vide.