Problème de l'arrêt
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 :
bouclera pour toujours, mais le programme
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.
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.
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.
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.
Questions et réponses
Q : Qu'est-ce que le problème de Halting ?
R : Le problème de Halting est un problème en informatique qui examine un programme informatique et détermine si le programme s'exécutera indéfiniment ou non.
Q : Comment savons-nous si un programme résout le problème de halte ?
R : Nous disons qu'un programme "résout le problème de la halte" s'il peut regarder n'importe quel autre programme et dire si cet autre programme s'exécutera éternellement ou non.
Q : Existe-t-il un moyen de prouver qu'un tel programme n'existe pas ?
R : Oui, en montrant que s'il existait un tel programme, quelque chose d'impossible se produirait. Cette preuve a été trouvée par Alan Turing en 1936.
Q : Que fait P ?
R : P est une fonction qui évalue une autre fonction F (appelée avec l'argument I) et renvoie true si elle s'exécute indéfiniment et false sinon.
Q : Que fait Q ?
R : Q examine un autre programme et répond ensuite à la question de savoir si l'exécution de ce même programme sur lui-même entraînera ou non une boucle infinie. Pour ce faire, il utilise P pour effectuer une évaluation de la fonction F donnée.
Q : Que fait R ?
R : R regarde un autre programme et demande à Q sa réponse sur ce programme particulier. Si Q répond "oui, si on exécute ce programme et qu'on lui fait regarder une copie de lui-même, il fonctionnera éternellement", alors R s'arrête ; cependant, si Q répond "non, si on exécute ce programme et qu'on lui fait regarder une copie de lui-même, il ne fonctionnera pas éternellement", alors R entre dans une boucle infinie et fonctionne éternellement.
Q : Que se passe-t-il lorsque vous faites en sorte que R se regarde lui-même ?
R : Deux choses peuvent se produire - soit R s'arrête, soit il tourne éternellement - mais les deux résultats sont impossibles selon ce qui a été prouvé à propos de l'inexistence de programmes comme P, donc quelque chose a dû mal se passer quelque part sur le chemin menant au fait que R se regarde lui-même.
