Exercices indécidabilité
Exercice 1
Les langages réguliers sont-ils décidables ?
Les langages hors-contexte sont-ils décidables ?
Exercice 2
Soit M une machine de Turing.
- 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 comme M.
- Soit w un mot donné. Représenter graphiquement la machine Mw qui écrit w sur le ruban
(en effaçant tout le mot qui s'y trouvait),
repositionne la tête de lecture au début du ruban puis se comporte comme M.
Exercice 3
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.
Exercice 4
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 5
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 6
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 7
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.