Problème de l'arrêt

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 un autre programme informatique quelconque et qui ressortirait VRAI si le programme s'arrête et FAUX sinon. Plus concrètement, on ne peut élaborer un compilateur capable de vous dire à tous les coups si le programme que vous avez écrit bouclera indéfiniment ou non. 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.

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).

Dans le cas général tout programme est une fonction PROG() qui transforme une chaîne de bits ch (appelée l'entrée) en une autre chaîne de bits PROG(ch) (appelée la sortie, éventuellement la sortie peut ne pas dépendre de l'entrée). Bien sûr, tout programme PROG() est en fait une chaîne de bits prog (qui représente le codage de PROG). Dans la suite on notera ch1ch2 la chaîne obtenue en concaténant les deux chaînes ch1 et ch2.

Supposons par l'absurde qu'il existe un programme HALT() tel que HALT(progch)=1 si PROG(ch) s'arrête, et HALT(progch)=0 si au contraire PROG(ch) boucle infiniment. On pourrait alors construire le programme TROUBLE() suivant:

TROUBLE(ch)

1. faire HALT(chch)

2. si HALT(chch)=1, alors faire{...} tant que(vrai)

Mais, on obtient une contradiction pour l'entrée trouble. En effet, supposons que TROUBLE(trouble) s'arrête, alors par définition de HALT(), on a HALT(troubletrouble)=1. Par définition de TROUBLE(), on a alors que TROUBLE(trouble) boucle infiniment. Admettons alors que TROUBLE(trouble) boucle infiniment. Dans ce cas par définition de HALT(), on a HALT(troubletrouble)=0 et donc par définition de TROUBLE(), on a TROUBLE(trouble) qui s'arrête. Cette contradiction prouve donc que HALT() n'existe pas.

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.