Problème de l'arrêt

Donnons ici la preuve de ce résultat fondée sur l'idée utilisée par Turing dans son article fondateur de 1936 (page 247). Elle repose sur un argument diagonal[2], tout comme la preuve d'indénombrabilité des réels de 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 des mots finis ${\displaystyle m}$ sur un alphabet fini. Par ailleurs, on décrit un programme (machine de Turing) par un mot fini prog, qui représente son codage.

Montrons par l'absurde que le problème de l'arrêt est indécidable. Supposons qu'il existe un programme halt qui décide le problème de l'arrêt. C'est-à-dire :

• Si prog(m) s'arrête, alors halt accepte (prog, m) en un temps fini ;
• Si prog(m) ne s'arrête pas, alors halt refuse (prog, m) en un temps fini.

On construit le programme diagonale suivant[3] :

procedure diagonale(x):
    si halt accepte (x, x)
        boucle infinie
    sinon
        accepter

Mais, on obtient une contradiction pour l'entrée diagonale. En effet, diagonale(diagonale) boucle à l'infini si et seulement si halt accepte (diagonale, diagonale), c'est-à-dire si et seulement si diagonale(diagonale) termine. Cela prouve donc par l'absurde que halt n'existe pas.

Une autre preuve fondée sur une idée légèrement différente a été établie par Gregory Chaitin[4]. Cette preuve est également une démonstration par l'absurde, partant de l'hypothèse que HALT(prog), déterminant si le programme PROG s'arrête, existe.

Imaginons le programme PARADOXE qui énumère tous les programmes dont la taille est plus petite que 10 fois[5] la taille de PARADOXE, et qui exécute la fonction HALT sur tous ces programmes. PARADOXE exécute les programmes qui s'arrêtent et mémorise leur résultat. PARADOXE dresse ainsi une liste de tous les résultats possibles que peuvent retourner toutes les machines de Turing qui s'arrêtent et dont la taille est inférieure à 10 fois la taille de PARADOXE. À partir de cette liste, PARADOXE détermine le plus petit entier positif n'appartenant pas à cette liste, et termine en retournant cet entier.

Mais, PARADOXE se terminant inévitablement, le résultat retourné par PARADOXE devrait se trouver dans la liste de tous les résultats possibles des machines de Turing qui se terminent et dont la taille est inférieure à 10 fois la taille de PARADOXE, ce qui n'est pas le cas par construction de PARADOXE qui retourne un nombre n'appartenant pas à cette liste.

On démontre ainsi l'impossibilité de l'existence de HALT.

Un raisonnement similaire démontre qu'aucun programme de taille sensiblement inférieure à N bits ne peut résoudre le problème de l'arrêt pour tous les programmes dont la taille est inférieure à N bits[4]. Ce qui signifie que même si HALT pouvait exister, sa taille croîtrait vers l'infini à mesure que la taille des programmes qu'il devrait tester croitrait aussi vers l'infini.

On peut s'intéresser à savoir si une machine s'arrête depuis toute configuration (pas forcément des configurations initiales). Le problème est appelé le problème de l'arrêt uniforme et il est également indécidable[6].

Le problème de l'arrêt est en théorie décidable dans le cas d'une mémoire de taille finie[7], car l'ensemble des états de la mémoire, bien que très grand, est fini lui-même. Or, dans le cas d'une mémoire finie, les états successifs de la mémoire finissent toujours par se répéter quand le programme ne s'arrête pas, avec un cycle de répétition au plus égal au nombre d'états possibles de la mémoire[8]. En effet, une machine de Turing étant déterministe, si un même état de mémoire se présente de nouveau, alors l'état suivant est nécessairement toujours celui déterminé par l'état précédent et ainsi de suite, et un cycle s'ensuit inévitablement.

Il est donc théoriquement possible de déterminer si la machine à mémoire finie boucle ou non en un temps fini. Un algorithme possible est celui du slow-fast[9]. Ce calcul doit cependant être effectué par un superviseur examinant en permanence les deux processus, et leur donnant le contrôle instruction par instruction pour l'un, deux instructions par deux instructions pour l'autre.

Le nombre exponentiellement élevé de combinaisons des états d'une mémoire limite dans la pratique cette méthode à de petits programmes comportant moins d'un millier de données scalaires (les instructions n'ont pas à être examinées si elles sont dans des segments protégés contre l'écriture, et donc ne varient jamais). C'est typiquement le cas des calculs par corrections successives d'un pangramme autodescriptif, qui ne décrivent qu'un sous-ensemble extrêmement petit des états mémoires possible.

Ce résultat qui concerne les machines finies ne contredit en rien la démonstration générale, qui porte sur des machines infinies n'existant pas dans la pratique.

• (en) Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem : Proceedings of the London Mathematical Society, London Mathematical Society, 1937 (DOI 10.1112/PLMS/S2-42.1.230, lire en ligne) et « [idem] : A Correction », Proc. London Math. Soc., 2^e série, vol. 43,‎ 1938, p. 544-546 (DOI 10.1112/plms/s2-43.6.544, lire en ligne)
  L'article fondateur où Turing définit les machines de Turing, formule le problème de l'arrêt, et démontre qu'il ne possède pas de solution (ainsi que l'Entscheidungsproblem).
• Olivier Ridoux et Gilles Lesventes, Calculateurs, calculs, calculabilité, Dunod, coll. « Sciences sup », 2008, 204 p. (ISBN 978-2-10-051588-2), chap. 3 (« Le problème de l'arrêt »)