Ceci est la machine A.
Elle effectue des calculs arithmétiques.
Elle reçoit un problème écrit sur support papier,
et elle imprime la réponse.
Elle imprime toujours la bonne réponse.
Voici une autre machine, C.
C joue aux dames ("Checkers" en Anglais).
Elle reçoit l'état actuel du plateau de jeu
et imprime comment il faut déplacer l'une des pièces rouges.
C joue aux dames si bien qu'elle ne perdra jamais une partie.
A et C sont des machines que nous pouvons déjà construire aujourd'hui,
et les ordinateurs sont de plus en plus intelligents.
Mais vont-ils fini par être en mesure de tout faire?
Par exemple la première machine peut-elle jouer aux dames ?
Non, A n'a pas été conçue pour gérer ce type d'entrée,
et quand elle essaie de le traiter, ça bogue : elle ne s'arrête pas, elle boucle.
La même chose arrive à C lorsqu'elle est alimentée par une addition.
En examinant A, nous obtenons sa notice détaillée
qui définit parfaitement comment fonctionne A.
Nous sommes maintenant enfin prêt à introduire une machine extraordinaire appelée H.
H résout le problème de l'arrêt (ou de la halte) :
H peut analyser la notice d'une autre machine,
et déterminer les entrées pour lesquelles elle va s'arrêter, et celles pour lesquelles elle va boucler.
Elle reçoit la notice de la machine à tester,
et une entrée pour tester avec.
A partir de la notice donnée en entrée, H simule la machine correspondante,
et détermine alors si ça boucle ou non. "Not stuck" = "ne boucle pas" "Stuck" = "boucle"
H résout parfaitement le problème de l'arrêt.
H imprime toujours la bonne réponse.
Voici deux autres exemples avec la notice de la machine qui trouve les meilleurs coups aux dames.
H est une belle machine, mais peut-on vraiment la construire?
Nous allons maintenant prouver que son existence même
est logiquement impossible.
Supposons que H existe.
Nous la placerons sur ici pour des raisons qui seront plus claires dans une minute.
Rappelons que nous supposons H résout parfaitement le problème de l'arrêt:
H imprime toujours la bonne réponse.
Nous sommes sur le point de mettre cette hypothèse à l'épreuve.
Voici la machine P qui est une machine à photocopier. Elle imprime simplement deux exemplaires de son entrée.
Nous allons la placer avant H.
Voici une autre machine simple. Nous l'appelons le Négateur.
Lorsque le Négateur reçoit les mots "ne boucle pas" en entrée, le Négateur se met à boucler lui-même.
Et quand il reçoit «boucle», il s'arrête
et imprime un sourire.
Nous le placerons après H.
Regroupons le tout dans un emballage soigné que nous appelons la machine X.
X possède une entrée et une sortie.
Examinons X pour obtenir sa notice détaillée.
Comme précédemment, cette notice définit entièrement X.
Que pensez-vous qui va se passer si nous alimentons X avec sa propre notice ?
X va-t-elle boucler ou s'arrêter ? Voyons.
D'abord P duplique tout simplement notre entrée.
Donc H reçoit deux exemplaires de la notice de X.
Il faut maintenant déterminer le résultat de H.
Supposons que H renvoie "ne boucle pas" pour la machine X sur l'entrée X.
La négateur N nie cela, et donc se met à boucler.
En résumé, alimenter X avec sa propre notice l'amène à boucler.
Mais, paradoxalement, H a dit que X ne bouclerait pas. H avait donc tort.
Essayons encore.
Cette fois, supposons que H renvoie «boucle» pour la machine X sur l'entrée X.
Sur l'entrée "boucle", le négateur s'arrête. Donc, globalement, X s'arrête sur l'entrée X, ce qui contredit le fait que H a dit qu'elle bouclerait.
En résumé, H a de nouveau tort.
Mais H est censée avoir toujours raison. . .
C'est une contradiction qui prouve que H ne peut exister.