Le problème de l'arrêt est en quelque sorte le « père » de tous les problèmes indécidables (si vous en connaissez un qui n'est pas son rejeton direct ou indirect, je suis intéressé !). Figurez-vous qu'ils sont très nombreux, parfois pas évidents, et qu'on les rencontre en se promenant. J'en citerai quelques-uns plus tard. Pour l'heure, reste à terminer avec le Entscheidungsproblem.

L'idée est que, si votre monde mathématique est assez puissant (les entiers, ça suffit, comme d'habitude), il est possible de ramener le problème :

déterminer si une machine M s'arrête sur l'entrée X

À un problème :

déterminer si un énoncé mathématique P est vrai.

Il suffit d'avoir les bons outils, tout simplement, pour exprimer "M s'arrête sur l'entrée X" en langage mathématique.

Du coup, comme le premier est indécidable, le deuxième l'est aussi : s'il ne l'était pas... boum ! C'est d'ailleurs comme ça qu'on obtient tous les autres problèmes indécidables.

Gudule : blahbmeh...

J'achève de faire fondre le cerveau de Gudule avec l'idée d'une preuve du théorème de Gödel utilisant le Entscheidungsproblem (roulement de tambour. Gudule ? Ah, il s'est totalement liquéfié. Bon, pas de tambour.)

Supposez que le théorème de Gödel est faux : vous êtes dans le monde des entiers, et tout énoncé est soit démontrable vrai, soit démontrable faux. Dans ce cas, il est possible de décider à coup sûr si un énoncé donné est démontrable, donc de casser le Entscheidungsproblem.

Donnons en effet un énoncé E, qui dit un truc. Puisque vous supposez que Gödel a tort, ou bien E est démontrable, ou bien "non E" est démontrable.

Vous dites maintenant à Charlot d'énumérer les démonstrations d'énoncés. Dans ce cas, E ou "non E" va finir par apparaître. Si vous voyez E apparaître, c'est bon : E est démontrable. Si vous voyez "non E" apparaître, c'est bon aussi : E n'est pas démontrable.

Énumérer les démonstrations ce n'est pas compliqué, en fait, il suffit de combiner, d'appliquer des axiomes les uns après les autres. Donc ça ne peut que marcher.

Conclusion : Charlot aurait résolu le Entscheidungsproblem ! Tout ça parce qu'il a la patience d'énumérer les démonstrations, et qu'il sait qu'il va finir par tomber sur la bonne.

Vous sentez que le théorème de Gödel a une saveur diagonale ? Eh bien, c'est exactement ça. La preuve par Gödel lui-même est encore plus explicite. Il construit une formule, dans le monde de l'arithmétique, qui affirme : « je ne suis pas démontrable ».

Dans le modèle standard de l'arithmétique, cette formule est vraie. Car si elle était fausse, elle serait démontrable (c'est ce qu'elle dit), et on attend d'une formule démontrable qu'elle soit vraie (ce sont les maths qui le disent, c'est quand même la base de la notion de « démontrable »).  Donc cette formule est bien vraie dans le modèle standard.

Et elle est bien « pas démontrable ».

Ensuite, il faut remarquer que sa négation n'est pas démontrable non plus. C'est parce que sa négation « je suis démontrable » est fausse, dans le modèle standard, et qu'une formule fausse n'est pas démontrable.

Alors, chers lecteurs, quelle est la morale de cette histoire ?

Il existe, au plus profond des mathématiques, une arme laissée là par les dieux pour nous sauver de la domination des machines. La diagonale.

Et cet argument n'est pas considéré comme « profond » pour rien. Le FTM ayant inventé les mathématiques, il les a conçues comme il voulait. Peut-être est-ce qu'on touche ici à la nature de l'univers.

--------------------------------------------------

Je termine avec une bonne nouvelle.

J'en ai fini avec le procédé diagonal.

Et je ne ferai jamais plus quelque chose d'aussi compliqué que les trois derniers chapitres.

Les arguments diagonaux sont profonds, ingénieux, compliqués, et il font mal à la tête. Même maintenant pour moi, alors que ça fait déjà des années que je suis censé connaître / comprendre ça.

FTM : c'est parce que you know nothing.

Gudule : seule ma popularité sauve encore l'affaire, maître. Il va falloir songer à convertir PJAM en chronique de Gudule.

Je pense avoir vraiment besoin d'améliorer ces trois segments. Faites-moi part de tous vos commentaires !