Exercices indécidabilité
Exercice 1
On utilise un langage de programmation impérative (comme C, Java ou Python) disposant
de l'instruction execute(P) qui exécute le programme P.
Montrer que déterminer si l'exécution d'un programme P passe sur une ligne de code numérotée n est un problème indécidable.
Indication : par réduction à partir du problème de l'arrêt.
Exercice 2
On utilise un langage de programmation impérative (comme C, Java ou Python) disposant
de l'instruction execute(P) qui exécute le programme P.
On suppose que l'exécution d'un programme, si elle termine, retourne un booléen.
Montrer que déterminer si les exécutions de deux programmes P et Q retournent la même valeur booléenne est un problème indécidable.
Indication : par réduction à partir du problème de l'arrêt.
Exercice 3
On utilise un langage de programmation impérative inspiré de C disposant
de l'instruction execute(P) qui exécute le programme P. Dans le code qu'il écrit, le programmeur doit explicitement allouer (avec l'instruction
new(Type)) puis rendre (avec l'instruction free(Var)) la mémoire que son programme utilise. On souhaite
automatiser la gestion mémoire : le programmeur crée les variables à l’aide de l’instruction new(Type),
la libération de la mémoire serait gérée automatiquement par le compilateur, par insertion d'instructions free(Var) aux bons endroits dans le code écrit par le programmeur.
Montrer qu'il ne peut pas exister de ramasse-miettes
optimal qui ajouterait un free(Var) au plus tôt après un new(Type) dans tout code source au moment de la compilation.
Indication : par réduction à partir du problème de l'arrêt.
Exercice 4
Soit Ma 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 MMa,ε
qui efface le mot écrit sur son ruban,
repositionne la tête de lecture au début
du ruban puis se comporte exactement comme Ma.
- Soit w un mot donné (par exemple abba). Représenter graphiquement la machine MMa,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 Ma.
Exercice 5
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 à partir de H, l'ensemble des couples (M,w) tels que M s'arrête sur w.
Exercice 6
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 à partir du problème de l'arrêt sur le mot vide.
Exercice 7
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 à partir du problème de l'arrêt sur le mot vide.
Exercice 8
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 à partir du problème de l'arrêt sur le mot vide.
Exercice 9
- 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 à partir du complément de LU.