Le problème de l'arrêt est un problème de l'informatique. Il s'agit d'examiner un programme informatique et de déterminer s'il va fonctionner éternellement ou non. Nous disons qu'un programme "résout le problème de l'arrêt" s'il peut regarder n'importe quel autre programme et dire si ce dernier va s'exécuter pour toujours ou non.

Par exemple, un programme comme celui-ci :

 alors que Vrai : continuer ;

bouclera pour toujours, mais le programme

 alors que Faux : continuer ;

s'arrête très rapidement.

Existe-t-il un programme qui résout le problème de l'arrêt ? Il s'avère qu'il n'y en a pas. Nous prouvons ce fait en montrant que s'il existe un programme qui résout le problème de l'arrêt, alors quelque chose d'impossible se produit. Pour l'instant, nous allons donc agir comme s'il existait réellement un programme qui résout le problème de l'arrêt. Ici, P est une fonction qui évaluera la fonction F (appelée avec l'argument I) et retournera vrai si elle fonctionne éternellement et faux sinon.

 def P(F, I) :     si F(I) court pour toujours :       retour Vrai ;     sinon :       retour Faux ;

P peut examiner n'importe quel programme et savoir s'il sera exécuté pour toujours ou non. Nous utilisons P pour créer un nouveau programme que nous appellerons Q. Ce que fait Q, c'est regarder un autre programme et répondre à la question suivante : "Si nous exécutons ce programme et que nous lui faisons regarder une copie de lui-même, s'exécutera-t-il éternellement ? Nous pouvons faire Q parce que nous avons P. Il suffit de dire à Q de créer un nouveau programme qui est l'ancien programme se regardant lui-même, et ensuite d'utiliser P pour savoir si le nouveau programme s'exécute pour toujours ou non.

 def Q(F) :     renvoyer P(F, F) ;

Maintenant, nous faisons un autre programme. R. R regarde un autre programme et demande à Q sa réponse sur ce programme. Si Q répond "oui, si nous exécutons ce programme et que nous lui faisons regarder une copie de lui-même, il s'exécutera pour toujours", alors R s'arrête. Si Q répond "non, si nous exécutons ce programme et lui faisons regarder une copie de lui-même, il ne s'exécutera pas pour toujours", alors R entre dans une boucle infinie et s'exécute pour toujours.

 def R(F) :     si Q(F) :       return ;                 //terminate     else :       while True : continue ; //loop forever

Nous allons maintenant voir ce qui se passe si nous faisons en sorte que R regarde une copie de lui-même. Deux choses peuvent se produire : il s'arrêtera ou s'exécutera à jamais.

Si le fait d'exécuter R et de lui faire regarder une copie de lui-même ne fonctionne pas éternellement, alors Q a répondu "oui, si nous exécutons ce programme et lui faisons regarder une copie de lui-même, il fonctionnera éternellement". Mais Q a dit cela en regardant R lui-même. Donc, ce que Q a dit en fait, c'est : "oui, si nous lançons R et que nous lui faisons regarder une copie de lui-même, il s'exécutera pour toujours". Donc : Si R s'exécute sur une copie de lui-même, il ne s'exécute pas pour toujours, alors il s'exécute pour toujours. C'est impossible.

Si le fait d'exécuter R et de lui faire regarder une copie de lui-même fonctionne pour toujours, alors Q a répondu "non, si nous exécutons ce programme et lui faisons regarder une copie de lui-même, il ne fonctionnera pas pour toujours". Mais Q a dit cela en regardant R lui-même. Donc, ce que Q a dit en fait, c'est : "non, si nous lançons R et que nous lui faisons regarder une copie de lui-même, il ne s'exécutera pas éternellement". Donc : Si R s'exécute sur une copie de lui-même, alors il ne s'exécute pas pour toujours. C'est également impossible.

Quoi qu'il arrive, nous nous retrouvons dans une situation impossible. Nous avons fait quelque chose de mal, et nous devons découvrir ce que c'était. La plupart des choses que nous avons faites n'étaient pas mauvaises. Nous ne pouvons pas dire que "faire regarder à un programme une copie de lui-même est mal", ou que "regarder ce qu'un autre programme a dit et ensuite entrer dans une boucle s'il a dit une chose, et s'arrêter s'il a dit une autre chose" est mal. Cela n'a pas de sens de dire que nous ne sommes pas autorisés à faire ces choses. La seule chose que nous avons faite et qui semble pouvoir être fausse, c'est de prétendre qu'un programme comme P existe au départ. Et puisque c'est la seule chose qui pourrait être mauvaise, et que quelque chose doit être mauvais, c'est cela. C'est la preuve qu'un programme comme P n'existe pas. Il n'y a pas de programme qui résout le problème de l'arrêt.

Cette preuve a été trouvée par Alan Turing en 1936.