Probleme de l'arret

En théorie de la calculabilité, le problème de l'arrêt consiste, étant donné un programme informatique quelconque (au sens machine de Turing), à dire s'il finira par s'arrêter ou non.

Ce problème n'est pas décidable, c'est-à-dire qu'il n'existe pas de programme informatique qui prendrait comme entrée le code d'un programme informatique quelconque et qui grâce à la seule analyse de ce code ressortirait VRAI si le programme s'arrête et FAUX sinon. Plus concrètement, on ne peut pas élaborer un compilateur capable de déterminer dans tous les cas si le programme bouclera indéfiniment ou non, bien qu'il soit cependant possible pour certaines séquences de codes identifiables de s'assurer que la construction génère potentiellement un bug). 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.

Preuve

La preuve de ce résultat repose sur un argument diagonal, tout comme la preuve d'indénombrabilité des réels Cantor (1891) et celle du théorème d'incomplétude de Gödel (1931).

Sans entrer dans le formalisme des machines de Turing, il suffit de savoir que toute machine de Turing (autrement appelée programme) prend en entrée une chaîne de caractères "ch" (disons que les caractères autorisés sont "0" "1", et un autre par exemple "," ce n'est pas restrictif), effectue une suite d'opérations, et, soit ne s'arrête jamais, soit s'arrête et renvoie une autre chaîne de caractères. Dans le cas général tout programme PROG() est en fait une chaîne de caractères (qui représente le codage de PROG). Pour que toute chaîne ait ainsi un sens, on ordonne ces codes (comme un dictionnaire), et le numéro (en binaire) obtenu pour "PROG()" est appelé "prog". Tout cela pour dire que, à une chaîne de 0 et de 1 correspond un programme bien déterminé. Ce codage n'utilise pas ",".

Dans la suite on notera ch1,ch2 la chaîne obtenue en concaténant les deux chaînes ch1 et ch2 avec le caractère "," entre les deux pour les séparer.

Supposons par l'absurde qu'il existe un programme HALT() tel que HALT(prog,ch)=1 si PROG(ch) s'arrête, et HALT(prog,ch)=0 si au contraire PROG(ch) ne s'arrête pas. Remarquons que, comme les codes des programmes ne contiennent pas de "," il n'y a qu'une seule manière d'interpréter l'entrée "prog,ch" donnée à HALT.

On pourrait alors construire le programme TROUBLE() suivant :

TROUBLE(ch)

1. Si "ch" contient une virgule, terminer et renvoyer "0".

Sinon, faire HALT(ch,ch)

2. si HALT(ch,ch)=1, alors faire une boucle infinie, et ne jamais terminer.

Sinon, terminer et renvoyer "0".

Ce programme est bien défini car, si "ch" n'a pas de "," le programme "HALT" s'arrête forcement. Mais, on obtient une contradiction pour l'entrée trouble (qui ne contient pas de "," car c'est le code d'un programme). En effet, supposons que TROUBLE(trouble) s'arrête, alors par définition de HALT(), on a HALT(trouble,trouble)=1. Par définition de TROUBLE(), on a alors que TROUBLE(trouble) boucle infiniment, ce qui contredit l'hypothèse. Admettons alors que TROUBLE(trouble) boucle infiniment. Dans ce cas par définition de HALT(), on a HALT(trouble,trouble)=0 et donc par définition de TROUBLE(), on a TROUBLE(trouble) qui s'arrête. C'est encore une contradiction.

Finalement, on a prouvé que si l'on suppose l'existence de "HALT()", on a l'existence de "TROUBLE()" qui contredit son fonctionnement. Cela prouve donc que HALT() n'existe pas.

Applications

Le problème de l'arrêt est un problème tenant aux fondements de l'informatique théorique. Des applications importantes appartiennent donc à ce domaine :

Il existe un ensemble d'entiers naturels récursivement énumérable qui n'est pas un ensemble récursif. En termes plus simples, il existe un ensemble d'entiers dont on peut produire la liste exhaustive par un algorithme, mais pour lequel il n'existe pas de programme permettant de dire sans faillir si un entier appartient à cet ensemble ou non.

Cela traduit le fait qu'un sens du problème de l'arrêt est facile (si une machine de Turing s'arrête, on fini évidemment par le savoir), alors que l'autre est impossible. Par ailleurs un théorème profond de Yuri Matiyasevich (fondé sur des travaux de Julia Robinson) assure que tout ensemble récursivement énumérable est Diophantien, et la réciproque est facile. (Un ensemble E de nombre entiers est Diophantien s'il existe un polynôme à plusieurs variables qui possède une solution entière si et seulement si la valeur de sa première inconnue est dans E). En prenant un ensemble Diophantien non récursif (le problème de l'arrêt nous en assure l'existence), on montre ainsi qu'il n'existe aucun algorithme qui peut indiquer si un polynôme à plusieurs variables donné admet une solution constitué d'entiers. C'est en fait la réponse au dixième problème de Hilbert sur la résolubilité des équations diophantiennes.

Une autre application aisée est une forme faible du théorème d'incomplétude de Gödel sur l'existence d'énoncés vrais mais non démontrables. En effet, l'énumération de preuves mathématiques peut se faire algorithmiquement. L'impossibilité de décider l'arrêt permet donc de dire qu'il existe une machine de Turing T et une entrée e telles que T ne s'arrête pas sur e, mais aussi telles qu'il n'existe pas de preuve de ce fait. L'énoncé "T s'arrête sur e" (pour cette machine et cette entrée dont on n'a que l'existence ; on ne les connait pas) est bien un énoncé vrai mais non démontrable.

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-miettes optimalement précis.