Dans la vie j'aime écrire. Et j'aime les maths. Bon, ça dépend quels domaines en particuliers (détails à venir).
Les maths sont pleines de choses bizarres. Vraiment bizarres. Donc marrantes. Intrigantes. Stupéfiantes. Renversantes. Bouleversifiant...
Gudule, qu'est-ce que c'est que ce truc qui met de l'huile partout ?
Gudule : c'est Charlot, le petit robot.
Gudule, tu vas remettre cette machine de Turing là où tu l'as trouvée tout de suite.
Gudule : mais il était tout seul et malheureux !
Charlot : je veux un ruban. Vous avez un ruban ?
Norbert : je suis Norbert, le coléoptère.
(Une pantoufle vole à travers la pièce. Norbert est aplati contre la vitre. Ses dernières pensées sont « je suis Norbert... le quoi, déjà ? »)
---------------------------------
Grâce aux machines, nous savons traduire mathématiquement la notion de « calculabilité ». Est calculable ce qui est calculable par une machine de Turing. Par exemple, le doublement d'un entier, c'est calculable. Savoir si un nombre est premier ou pas, c'est calculable. Trier un paquet d'entiers par ordre croissant, c'est calculable. Tout ce qu'on peut calculer avec un programme C++, c'est calculable.
Gudule : et déterminer si une proposition donnée est démontrable, c'est calculable ?
Tu aimerais bien, Gudule, pas vrai ? Moi pas. Ça voudrait dire que tous les mathématiciens depuis l'aube de l'humanité auraient été obsolètes, parce que le petit Charlot...
Charlot : je veux un ruban.
... à lui seul, bien programmé, pourrait tout de suite déterminer si un théorème donné est vrai ou faux, et peut-être même en donner automatiquement une preuve. En bref, on n'aurait plus besoin de mathématiciens, tout serait automatique.
Pire encore, tout le travail des mathématiciens depuis le commencement des temps n'aurait eu pour ultime fin que de donner le jour à Charlot.
Un robot pour les gouverner tous, un robot pour les trouver
Un robot pour les renvoyer tous et bêtement les remplacer
Tu veux vraiment qu'un robot devienne le maître du monde, Gudule ? Moi, je ne me laisserai pas faire ! Dussé-je lutter jusqu'à mon dernier souffle ! Et ça tombe bien, le créateur de l'univers est avec moi !
FTM : ne vous inquiétez pas, j'ai tout prévu.
Ce « problème de décision » se nomme « Entscheidungsproblem », de l'allemand, langue natale du mathématicien David Hilbert qui en fait l'un des 23 problèmes de 1900. Et depuis les années 30, nous en avons la réponse.
Théorème (Gudule) : il n'existe pas d'algorithme, au sens de Church et Turing, pour déterminer si un énoncé mathématique donné est démontrable.
Ça dépend un peu de la théorie considérée, en fait. Mais tant qu'on a les entiers naturels, c'est vrai. Il n'existe pas d'algorithme pour le « Entscheidungsproblem ». Church l'a montré en 1936 à l'aide du lambda-calcul et Turing peu après avec les machines de Turing. Je ne suis pas un spécialiste du lambda-calcul, et ça tombe bien, on parle ici de machines de Turing. Voyons pourquoi le « Entscheidungsproblem » n'a pas de solution algorithmique. On le dit « indécidable », et par déformation professionnelle, je vais essentiellement employer ce mot.
Tout part d'un autre problème, en fait, le « problème de l'arrêt » des machines de Turing. C'est le suivant : existe-t-il un algorithme, donc une machine, qui sur une entrée qui représente à la fois le codage d'une machine et l'entrée donnée à cette machine, dit si ça s'arrête ou pas ? En version C++ : peut-on coder un algorithme en C++ qui, sur n'importe quel code C++ et n'importe quelle entrée, dit à coup sûr si ça s'arrête ou pas ?
Gudule : bah, on fait tourner le programme et on attend.
Et quand voudrais-tu t'arrêter ? On ne sait jamais.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
Eh bien, le problème de l'arrêt est lui-même indécidable. Charlot ne peut pas être programmé pour dire si, étant donnée une machine de Turing et une entrée, la machine va finir par s'arrêter ou continuer à l'infini.
Le problème est identique pour le C++. Et il n'existe pas de "vérificateur de code universel" qui vous dira s'il n'y a pas de bug dans un code donné.
Gudule : mais pourquoi est-ce que le problème de l'arrêt est indécidable ?
Devine.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
Imaginons que Charlot le robot est La machine de Turing qui décide le problème de l'arrêt. Oublions que c'est une machine de Turing. Charlot est un programme qui mange un programme M et une entrée X donnée, et qui dit si M s'arrête sur l'entrée X, ou si M ne s'arrête pas sur l'entrée X et fait n'importe quoi.
Il est maintenant possible de construire un autre programme, Bob, qui va être la source du problème. Bob mange lui aussi un programme M et une entrée X, mais il fait la chose suivante :
- si Charlot dit "M s'arrête sur X", alors Bob part en vrille et écrit des trucs à l'infini ; donc ne s'arrête pas.
Bob : vers l'infini et au-delààààààààà !
(Bob s'enfuit au loin en courant, sous un coucher de Soleil)
- si Charlot dit "M ne s'arrête pas sur X", alors Bob s'arrête tout de suite et meurt.
Et maintenant, le paradoxe : que répond Bob si vous lui donnez à manger (Bob, Bob) ?
- si Charlot répond "Bob s'arrête sur l'entrée Bob" : Bob doit partir en vrille. Donc ne pas s'arrêter. Mais ça veut dire que Charlot avait tort ! Impossible.
- si Charlot répond "Bob ne s'arrête pas sur l'entrée Bob" : Bob doit s'arrêter.
Ça ne vous dit rien ?
Gudule : j'ai déjà ressenti ce même sentiment de confusion et d'arnaque dans l'air.
C'est un procédé diagonal, en fait. Comme le paradoxe de Russell. Nous avons construit un objet contradictoire, en l'occurrence, une machine de Turing. C'est un tout petit peu plus compliqué à expliquer qu'avec Russell qui construisait un ensemble contradictoire ; mais c'est exactement le même principe.
C'est aussi le même principe que le théorème de Gödel.
