Problème de l'arrêt
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de Le problème de l'arrêt est le problème de décider si un programme informatique (ou une machine de Turing) finit par s'arrêter ou non.
L'impossibilité de la décision du problème de l'arrêt est un résultat central de la théorie de la calculabilité. On a ainsi démontré qu'il était impossible pour un programme informatique de décider automatiquement et dans tous les cas, à la lecture d'autres programmes informatiques, si ceux-ci terminent. Cela signifie concrètement qu'il n'existera jamais de compilateur capable de vous dire que le programme que vous avez écrit est mal conçu et qu'il bouclera indéfiniment. Ce résultat est généralisé par le théorème de Rice à de nombreuses autres propriétés concernant l'analyse des programmes.
[modifier] Preuve
La preuve de ce résultat repose, comme celle du théorème d'incomplétude de Gödel, sur un argument diagonal.
Preuve en termes imagés : Considérons l'ensemble des programmes informatiques qui lisent en entrée un programme informatique P et répondent par « oui », ou éventuellement bouclent indéfiniment. Voici un exemple de tel programme :
- Lire en entrée P
- Exécuter P
- Afficher « oui »
La troisième étape ne pourra être exécutée qu'à l'issue de la seconde étape, c’est-à-dire lorsque P se sera terminé. Si P boucle indéfiniment, il en est de même du programme principal et l'affichage « oui » n'aura jamais lieu.
Intéressons-nous maintenant à l'ensemble X des tels programmes P qui bouclent indéfiniment lorsqu'ils sont appliqués à eux-mêmes. Supposons maintenant que cet ensemble X est semi-décidable, c'est-à-dire qu'il existe un programme P0 tel que P0 réponde « oui » sur une entrée P si et seulement si P est dans cet ensemble. Nous pouvons maintenant nous demander si P0 est lui-même dans X. P0 répond « oui » sur l'entrée P0 si et seulement si P0 est dans X, c'est-à-dire si P0 appliqué à l'entrée P0 ne termine pas. La supposition d'existence de P0 est absurde. X n'est donc pas semi-décidable.
(Notons que le complémentaire de X est semi-décidable : le programme de semi-décision prend en entrée P, applique P à lui-même, puis répond « oui ».)
A fortiori, X n'est pas décidable.
Considérons maintenant le problème T de tester au vu d'un programme P si celui-ci termine sur l'entrée vide. On va réduire le problème de l'arrêt à celui-ci, c'est-à-dire montrer qu'on peut, au vu d'une question sur le problème de l'arrêt, construire algorithmiquement une question au problème T dont la réponse sera équivalente.
Soit P un programme dont on veut déterminer s'il appartient à X. On peut algorithmiquement construire un programme P2 qui ne prenne aucune entrée et lance P sur lui-même. Si on sait décider en général si P2 termine, on sait décider en général si P termine, donc X serait décidable. Cela est absurde.
Donc : il n'existe pas de moyen algorithmique de déterminer si un programme arbitraire termine.
[modifier] Applications
De très nombreux problèmes en informatique, notamment concernant l'analyse statique de programmes, sont équivalents au problème de l'arrêt. On le montre là encore en réduisant la résolution du problème de l'arrêt à celle du problème étudié.
Citons par exemple le problème du ramasse-miettes : on cherche à libérer des zones mémoires juste après leur dernière utilisation. Ce problème est équivalent à celui de l'arrêt. La réduction est simple : soit P un programme dont on veut tester l'arrêt ; considérons le programme :
- créer une zone mémoire X (jamais utilisée dans P)
- exécuter P
- écrire dans X.
Clairement, la zone mémoire X sert après sa création si et seulement si P termine. Donc, si on savait déterminer automatiquement au vu de la lecture du programme si on peut libérer X juste après son allocation, on saurait si P termine. Cela est impossible, donc il n'existe aucun algorithme de ramasse-miette optimalement précis.
