Nous montrerons comment obtenir une contradiction logique à partir de l’hypothèse que le problème de l’arrêt peut être résolu par une machine de Turing.

1Il est en principe possible d’encoder automatiquement le programme de n’importe quelle machine de Turing comme un nombre naturel. Les détails importent peu ; il suffit de savoir que cela peut se faire (à vrai dire, par de nombreux moyens). En sélectionnant un encodage précis, nous pouvons assigner à toute machine de Turing un nombre naturel—son code—à partir duquel le programme de la machine peut être retrouvé par un décodage (automatique) approprié. S’il se trouve qu’un nombre naturel donné m soit le code d’une machine de Turing, nous désignons cette machine par T(m). En d’autres mots, T(m) est la machine de Turing (s’il y en a une) dont le code est m.

2Supposons maintenant qu’une certaine machine de Turing, disons H, résolve le problème de l’arrêt dans le sens suivant : H accepte comme entrée une paire (m, n) de nombres naturels et retourne comme sortie 1, si m est le code d’une machine de Turing ; et si cette machine—T(m) —finit tôt ou tard de calculer et s’arrête après avoir été mise en marche avec le nombre n sur son ruban d’entrée. Dans toute autre circonstance, la sortie de H est 0. Encore une fois, H écrit un 1 à la fin de son calcul, si T(m) finit par s’arrêter sur l’entrée n, et écrit un o dans tout autre cas, c’est-à-dire si m n’est pas le code d’une machine de Turing ou s’il est bien le code d’une machine de Turing, mais cette machine ne s’arrêtera jamais de calculer sur l’entrée n.

3Il est très facile d’écrire le programme d’une autre machine de Turing—appelons-la E—qui s’arrête immédiatement si son entrée est le nombre 0, et qui entre dans une boucle infinie si elle commence par lire le nombre 1. En connectant H et E « en série » (c’est-à-dire de sorte que la sortie de H devienne l’entrée de E), nous obtenons une troisième machine de Turing, C, qui se comporte de la façon suivante : pour chaque nombre naturel n,

4si T(n) - c’est-à-dire la machine de Turing avec le code n- ne s’arrête jamais sur l’entrée « , alors C s’arrête sur l’entrée n (l)

5si T(n) finit par s’arrêter sur l’entrée n, alors - sur l’entrée n-C ne s’arrête jamais (2)

6Encore une fois : sur l’entrée n, C se sert d’abord de H pour déterminer si T(n) s’arrêtera ou non, au cas où elle est mise en marche sur cette même entrée n. Ensuite, C agit en fonction de cette information pour faire exactement le contraire de ce que T(n) ferait : si cette dernière finit par s’arrêter, C s’arrange pour tourner à jamais ; si, au contraire, C « apprend » que T(n) ne s’arrêtera jamais, alors C met fin à son calcul.

7Il faut bien comprendre que si H existe, alors C existe aussi Ci-après, nous montrons que l’existence (jusqu’ici hypothétique) de C mène à une contradiction logique. Donc, il n’y a pas de C, et ainsi H non plus ne peut exister.

8Car, supposons que C soit construit selon ce qui a été indiqué. Le programme de C, une fois qu’il aura été encodé, devient un certain nombre naturel, c, par exemple—c’est-à-dire C=T(c). Maintenant, mettons en marche C sur l’entrée c et considérons ce qui pourrait se passer. Le comportement de C étant spécifié par les clauses (1) et (2) ci-dessus, nous pouvons les exprimer avec n (l’entrée générique) remplacé par la présente entrée c. Ces clauses se lisent maintenant comme suit :

9si T(c) ne s’arrête jamais sur l’entrée c, alors C s’arrête sur l’entrée c, et

10si T(c) finit par s’arrêter sur l’entrée c, alors - sur l’entrée c-C ne s’arrête jamais.

11Or C et T(c) sont la même machine. Par conséquent, si C existe, elle devra en même temps finir par s’arrêter et tourner perpétuellement sur une de ses entrées—ce qui est une impossibilité logique.