*Yvan Lavallée est directeur de rédaction de Progressistes.

---

L’année 1900 est la dernière année du XIXe siècle.

La charnière entre le XIXe et le XXe siècle est riche de découvertes et avancées scientifiques et philosophiques qui vont marquer l’avenir et qui nous interpellent toujours aujourd’hui, qu’il s’agisse de la théorie d’Einstein et de la fameuse formule E= mc² (1905) qui permet de caractériser l’équivalence énergie/matière qui préoccupait la science de l’époque, ou de la démonstration par Louis Bachelier de la caractérisation mathématique du mouvement brownien, ou encore de l’émergence du concept de complexité avec le problème à trois corps abordé par Henri Poincaré, et Gaston Bachelard, le facteur philosophe qui publie le Nouvel Esprit scientifique en 1934.

Au tout début du XXe siècle paraît une critique rationaliste et marxiste de l’empiriocriticisme, doctrine à la mode à l’époque, par Vladimir Illitch Oulianov, dit Lénine, sous le titre Matérialisme et Empiriocriticisme (1908) qui ouvre la voie philosophique à la révolution bolchevique. Le décor scientifico-philosophique est posé !

C’est en 1900 que, pour ce qui nous concerne ici, les choses prennent racine. Le mathématicien David Hilbert va poser au congrès des mathématiques de Paris une série de vingt-trois problèmes, dont le dixième va conduire à une révolution, à la fois conceptuelle, mathématique et philosophique, à l’émergence d’une nouvelle discipline scientifique. On peut donner une version « grand public » de ce dixième problème, et surtout de sa reformulation en 1928 sous le nom allemand de Entscheidungsproblem, ou problème de décision; en fait il se compose de deux parties, deux conjectures¹.

Première partie de la conjecture: il existe une façon unique de poser tout problème de mathématique.

Deuxième partie de la conjecture: si cette première partie de la conjecture est vraie, alors il existe une façon unique de résoudre tout problème de mathématique.

Je laisse là imaginer un peu l’enjeu. C’est dans les années 1930 que des réponses vont être données.

En 1931, le mathématicien logicien Allemand Kurt Gödel va provoquer un séisme en publiant deux théorèmes, dont le premier, dit « théorème d’incomplétude² de Gödel », est le plus puissant pour ce qui nous préoccupe.

Il peut s’énoncer comme suit : Dans n’importe quelle théorie récursivement axiomatisable, cohérente et capable de « formaliser l’arithmétique », on peut construire un énoncé arithmétique qui ne peut être ni démontré ni réfuté dans cette théorie.

Passons sur « récursivement axiomatisable », qui ne parle qu’aux spécialistes et dont ce n’est pas ici le lieu de développer la signification. Kurt Gödel, à vingt-quatre ans, vient là de balayer tous les espoirs de la construction cohérente de l’édifice mathématique que le prestigieux mathématicien Bertrand Russel poursuivait ; et l’espoir d’une théorie parfaite et close. Le concept d’indécidabilité est né !

Mais la démonstration en est particulièrement abstruse. C’est Alan Mathison Turing qui va donner une réponse nettement plus simple et lumineuse à ces problèmes dans un article, majeur encore aujourd’hui, « On computable numbers with an application to the Entscheidungs problem »³
Pour ce faire, Turing avance un concept abstrait de machine, qu’on appellera par la suite machine de Turing⁴. Ce concept⁵ va permettre de refonder le concept de calcul, celui de problème, puis de solution d’un problème en formalisant ce qui va devenir fondamental par la suite, le concept d’algorithme.

Quoique son nom de « machine » puisse conduire à imaginer un objet matériel, palpable, la machine de Turing est un concept, une entité abstraite, un objet mathématique, ce qu’on appelle aussi « une expérience de pensée ». Une machine de Turing est constituée des éléments suivants :

1.Un ruban infini (c’est d’ailleurs ce qui fait de la machine de Turing un être abstrait) divisé en cases consécutives. Chaque case contient un symbole et un seul parmi un alphabet fini⁶. L’alphabet contient un symbole spécial ( ) appelé « symbole blanc » et plusieurs autres symboles. Le ruban est supposé infini tant à droite qu’à gauche; la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases non écrites du ruban contiennent le symbole « blanc » ou « vide ».

2.Une tête de lecture/écriture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban d’une seule case à la fois, ou ne pas se déplacer.

3.Un registre d’état qui mémorise l’état courant de la machine de Turing, et celui-ci seulement. Le nombre d’états possibles est toujours fini, la machine possède donc un alphabet d’états.

4. Une table d’actions, table à double entrée⁷ dans laquelle on lit en ligne le symbole qui vient d’être lu sur le ruban, en colonne l’état de la machine, et la case correspondante de cette table à double entrée indique à la machine quelle action effectuer sur le ruban en fonction de son < état courant et du symbole présent dans la case sous la tête de lecture/écriture: effacer le symbole lu, écrire un symbole sur le ruban, comment déplacer la tête de lecture (par exemple « G » pour une case vers la gauche, « D » pour une case vers la droite, « N » pour neutre, c’està- dire stagnation), et dans quel nouvel état passer éventuellement, toujours en fonction du symbole lu sur le ruban et de l’état courant de la machine.

Ce concept de machine de Turing est d’une puissance phénoménale; il est à l’origine de l’informatique, et partant de là de la révolution numérique. Du point de vue logique, même si au plan technologique ce n’est pas tout à fait vrai, tous les ordinateurs séquentiels modernes sont fondés sur ce principe. Ce concept permet d’appréhender toutes les activités humaines, et plus : il permet de modéliser y compris des phénomènes qui sont hors du champ mathématique, comme le comportement  d’espèces animales⁸, ou la théorie de l’évolution de Darwin⁹.

Il s’agit ici (ci-dessus) d’une machine de Turing particulière qui effectue une addition comme on l’apprend aux enfants, avec des bûchettes.

Là par exemple, à partir de la position au départ, la machine lit (I,q0), c’est-à-dire qu’elle lit le I alors qu’elle est dans l’état q0, elle efface alors le contenu de la case du ruban¹⁰ « Λ » puis opère un décalage à droite « D » puis la machine passe dans l’état « q1 », et ainsi de suite…

On peut aussi coder chacun de ces symboles avec des 0 et des 1, auquel cas, à la suite de petites manipulations de codage, on obtient une machine de Turing universelle qui permet de simuler toute machine de Turing particulière comme celle-ci.

Par rapport à la double conjecture énoncée par Hilbert, Turing donne le moyen de répondre positivement à la première partie ; la machine de Turing universelle permet effectivement – théoriquement – de poser tout type de problème mathématique (et beaucoup d’autres accessoirement) en codant l’énoncé sur le ruban. Mais, ce n’est pas parce que l’on sait poser de façon unique tout problème de mathématique qu’on sait nécessairement le résoudre.

En introduisant ce qu’il est convenu d’appeler le problème de la halte, Turing donne une démonstration originale du premier théorème de Gödel. Le problème de la halte consiste, dans une acception « grand public », à poser la question de savoir si une machine de Turing universelle va s’arrêter pour une écriture donnée sur le ruban. Dans le cas général, la réponse est « on ne peut pas répondre », c’est indécidable !

1. En mathématiques, une conjecture est un énoncé qu’on a toutes les raisons de penser être vrai, mais qu’on ne sait pas démontrer et pour lequel on n’a jusqu’à présent aucun contre-exemple.
2. Le second porte sur la cohérence logique d’une théorie. Il dit en substance qu’une théorie sera dite cohérente lorsqu’on ne peut y démontrer une proposition et son contraire, A et non A.
3. « Sur les nombres calculables avec une application au problème de la décision ».
4. Voir une description simple dans l’Homme et les techniques, Messidor-La Farandole, 1991, p.48.
5. N’en déplaise à Deleuze et Gattari, les mathématiciens aussi créent des concepts !
6. En fait, on montre – mais ce n’est pas ici le lieu de le faire – que cet alphabet peut se résumer à [0,1] dans ce qu’on appelle la machine de Turing universelle, c’est-à-dire la machine de Turing capable de simuler toute machine de Turing spécifique.
7. C’est une représentation parmi d’autres, on pourrait présenter ça autrement.
8. https://hal.archives-ouvertes.fr/hal-00814812v2 et aussi https://arxiv.org/abs/1304.5604
9. Leslie Valiant, Probablement approximativement correct (trad.), Cassini, 2018.
10. Le symbole Λ signifie ici le « blanc ».