Qu’a découvert Alan Turing dans son article de 1936, « On Computable Numbers »?

En 1936, un mathématicien de 23 ans, à Cambridge, a écrit un article qui décrivait discrètement l’ordinateur avant que quiconque en ait construit un. « On Computable Numbers, with an Application to the Entscheidungsproblem », d’Alan Turing, imaginait une machine très simple qui effectue un calcul un symbole à la fois. Puis il a montré une chose étonnante : une seule machine de ce genre pouvait faire le travail de toutes les autres, pourvu qu’on lui donne à suivre une description écrite de la machine en question.

Il s’est servi de ces machines imaginaires pour répondre à une question profonde de logique, et la réponse était « non » : il n’existe aucune procédure mécanique capable de trancher tous les énoncés mathématiques. En chemin, il a donné au monde une définition précise de ce que signifie, pour une chose, être calculable.

Quand, où et qui

Turing avait étudié les mathématiques au King’s College de Cambridge et, en 1935, le collège a fait de lui l’un de ses fellows. Entre 1935 et le début de 1936, il a travaillé sur le problème de la décidabilité. En avril 1936, il a montré une ébauche au mathématicien Max Newman. Le même mois, le logicien américain Alonzo Church a publié un article qui arrivait à une conclusion semblable par une voie complètement différente.

L’article a été reçu par la London Mathematical Society le 28 mai 1936 et lu devant la Société le 12 novembre 1936. Il a paru dans les Proceedings de la Société en deux parties à la fin de 1936, avec une courte correction en 1937. Turing était alors parti à l’Université de Princeton pour étudier auprès de Church, qui, dans un compte rendu, a été le premier à appeler ces dispositifs des « machines de Turing ».

Le problème que Turing voulait résoudre

En 1928, le mathématicien allemand David Hilbert a posé ce qu’on a appelé l’Entscheidungsproblem, « problème de la décision » en allemand. En gros : existe-t-il une méthode déterminée qui, pour n’importe quel énoncé de logique formelle, peut toujours décider s’il peut être démontré? Hilbert espérait que la réponse serait oui. Pour montrer que la réponse était non, il fallait d’abord dire exactement ce qu’est une « méthode déterminée ». La machine de Turing était cette définition.

Il est parti d’une personne qui fait de l’arithmétique avec un crayon et du papier. Cette personne regarde quelques symboles à la fois, en écrit ou en efface un, déplace son attention et suit des règles qui dépendent de ce qu’elle pense à ce moment-là. Turing a réduit cela à une machine dotée :

• d’un ruban divisé en cases, chacune contenant au plus un symbole;
• d’une tête de lecture qui regarde une case à la fois;
• d’un ensemble fini d’états internes (Turing les appelait des « m-configurations »);
• d’une table de règles : pour chaque état et chaque symbole, quoi écrire, dans quel sens se déplacer et vers quel état passer ensuite.

Un exemple concret : la première machine de Turing

La première machine de l’article imprime simplement 0 1 0 1 0 1 à l’infini, en laissant une case vide entre chaque chiffre. Elle utilise quatre états, que Turing appelle b, c, e et f :

Suivez-la sur un ruban vierge. Dans l’état b, elle écrit 0 et avance vers la droite; dans c, elle saute une case; dans e, elle écrit 1; dans f, elle saute encore une case; puis elle revient à b. Le ruban se remplit ainsi : 0 _ 1 _ 0 _ 1, et ainsi de suite. Rien ne pourrait être plus simple et, pourtant, Turing soutenait que tout calcul qu’une personne peut effectuer en suivant des règles peut être décomposé en étapes aussi petites.

La machine universelle et les limites du calcul

La section 6 de l’article fait le grand saut. Turing a montré que la table de règles de n’importe quelle machine peut elle-même être écrite sur un ruban sous forme de suite de symboles. Il a ensuite conçu une seule machine, la machine universelle, qui lit une telle description et imite la machine décrite, étape par étape. Selon ses mots : « Il est possible d’inventer une seule machine qui peut servir à calculer n’importe quelle suite calculable. »

C’est l’idée qui se trouve derrière chaque ordinateur que vous utilisez : un seul appareil, beaucoup de programmes. Le programme n’est que des données que la machine lit.

Turing a ensuite tourné cet outil vers la question de Hilbert. Il a montré qu’il ne peut exister aucune procédure générale qui examine la description de n’importe quelle machine et décide à l’avance de son comportement, par exemple si elle continuera d’imprimer des chiffres à l’infini. Il en a tiré la preuve que l’Entscheidungsproblem n’a pas de solution. Church est arrivé au même résultat de façon indépendante, et on a vite montré que les deux approches étaient équivalentes.

Pourquoi c’était important

L’article de Turing a fourni un modèle de calcul clair et simple, qu’on enseigne encore dans tous les cours d’informatique. Il montrait ce que les machines pouvaient faire en principe, et aussi ce qu’aucune machine ne pourrait jamais faire. Après la Seconde Guerre mondiale, Turing a lui-même conçu l’un des premiers ordinateurs à programme enregistré, l’Automatic Computing Engine du National Physical Laboratory britannique, et il a décrit ces machines comme des versions pratiques de sa machine universelle. Les historiens débattent de l’influence directe qu’a eue l’article sur les premiers ordinateurs, comme le projet EDVAC, et ils mettent en garde contre l’idée de faire de Turing l’unique inventeur de l’ordinateur. Mais l’idée du programme vu comme des données qu’une seule machine générale peut exécuter remonte clairement à 1936.

Quel rapport la machine de Turing a-t-elle avec l’IA d’aujourd’hui?

Tous les systèmes d’IA de 2019, de la reconnaissance vocale d’un téléphone à un grand modèle de langage comme GPT-2, fonctionnent sur des ordinateurs ordinaires, et tout ordinateur ordinaire est, au sens de Turing, une machine universelle pratique dotée d’une mémoire finie. Les réseaux de neurones ne ressemblent guère aux tables de règles bien ordonnées de Turing, mais ce sont au bout du compte des programmes, et tout ce qu’ils calculent pourrait, en principe, être calculé par une machine de Turing disposant d’assez de ruban et de temps.

Cela donne une perspective utile. L’article de 1936 dit ce qui est calculable, pas à quelle vitesse ni avec quelle astuce. L’IA moderne porte sur cette seconde partie : trouver des programmes, souvent en apprenant à partir de données, qui font des choses utiles dans des limites pratiques de vitesse et de mémoire. Turing a aussi montré que certaines questions sur les programmes n’ont pas de réponse générale, ce qui explique en partie pourquoi il est si difficile de vérifier entièrement ce qu’un système d’IA complexe fera dans toutes les situations.

Turing est revenu aux machines et aux esprits dans son article de 1950 sur le jeu de l’imitation, qu’on appelle aujourd’hui le test de Turing. C’est la machine universelle de 1936 qui a rendu cette question ultérieure, « les machines peuvent-elles penser? », digne d’être posée.