Problème de l'arrêt

Un article de Wikipédia, l'encyclopédie libre.

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 élaborer un compilateur capable de déterminer dans tous les cas si le programme bouclera indéfiniment ou non^[1]. 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 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.

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

[modifier] Notes et références