Turing et la question fondatrice (1950)

Alan Turing adolescent, vers 1928. Domaine public — Wikimedia Commons.

Le moment

En 1950, peu après la fin de la Seconde Guerre mondiale, le mathématicien britannique Alan Turing publie un article intitulé Computing Machinery and Intelligence. L’article commence par une question qui occupera tout un domaine pendant les décennies suivantes :

« Les machines peuvent-elles penser ? »

La première page de « Computing Machinery and Intelligence », Mind, vol. LIX, n^o 236, octobre 1950.

Turing est déjà connu à ce moment. Pendant la guerre, il a joué un rôle décisif dans le décryptage des communications chiffrées par la machine Enigma des armées allemandes. Il a conçu des dispositifs électromécaniques capables d’explorer mécaniquement des millions de combinaisons. Ce travail est longtemps resté secret, et les historiens estiment qu’il a pu écourter le conflit de plusieurs années. Turing sait donc mieux que quiconque à son époque qu’une machine peut accomplir des tâches qu’on croyait réservées à l’esprit humain. Son article examine si une machine qui déchiffre des messages peut aussi être considérée comme une machine qui pense.

Une machine Enigma. Photo : Karsten Sperling, domaine public.

Reconstitution d'une « bombe » de décryptage, Bletchley Park. Photo : Sarah Hartwell, CC BY-SA 3.0, via Wikimedia Commons.

Le jeu de l’imitation

Turing remarque que la question « les machines peuvent-elles penser ? » est mal posée. La réponse dépend entièrement de ce qu’on accepte d’appeler « penser », et on ne sait pas définir clairement ce mot, même pour les humains. Plutôt que d’entrer dans ce débat, Turing remplace la question par une autre, à laquelle on peut réellement répondre.

Au lieu de demander si une machine peut penser, il propose une épreuve concrète, le jeu de l’imitation (imitation game), qu’on appelle aujourd’hui le test de Turing. Un juge humain dialogue par écrit avec deux interlocuteurs cachés, un être humain et une machine. Les messages passent par clavier, pour que ni la voix ni le visage ne permettent de savoir qui est qui. Le juge peut poser n’importe quelle question, par exemple sur la météo, la poésie, l’arithmétique ou ses souvenirs d’enfance. Il doit deviner lequel des deux interlocuteurs est la machine. Selon Turing, si la machine parvient, sur un grand nombre de parties, à se faire passer pour un humain aussi souvent qu’un humain y parvient, il n’y a plus de raison sérieuse de refuser de dire qu’elle pense.

Dans l’article, le jeu est d’abord présenté avec un homme et une femme, que l’interrogateur doit distinguer. Turing demande ensuite ce qui arriverait si une machine prenait la place de l’un des deux. C’est cette seconde version qui a été retenue par la suite, et vous pouvez le vérifier sur la page de Mind reproduite plus haut.

Cette proposition est à la fois philosophique et technique. Turing remplace la question de l’intériorité par celle du comportement. Ce qui se passe « à l’intérieur » de la machine, ou le fait qu’elle « ressente » quelque chose, n’a pas d’importance. Ce qui compte, c’est ce qu’elle est capable de faire. Ce changement de point de vue soulève une question de fond, que les philosophes débattent encore aujourd’hui :

Le test de Turing est souvent mal compris. Ce n’est pas un test de conscience, ni une définition de l’intelligence au sens large. C’est une proposition pragmatique : si on ne peut plus distinguer la machine de l’humain en conversation, alors chercher à savoir si elle « pense vraiment » devient un débat sans issue. Le test contourne une question insoluble, il ne la résout pas.

La pensée comme calcul

Le test repose sur une idée plus fondamentale, qui constitue le principal apport de Turing à l’IA. Dès 1936, bien avant son article sur le jeu de l’imitation, Turing avait inventé un objet mathématique qu’on appelle aujourd’hui la machine de Turing. C’est un dispositif imaginaire très simple, qui se contente de lire et d’écrire des symboles sur un ruban en suivant un ensemble de règles fixes.

Turing montre que ce mécanisme élémentaire peut, en principe, calculer tout ce qui est calculable. La machine de Turing donne ainsi une définition précise d’une notion qu’on emploie couramment sans la définir, celle d’algorithme. Un algorithme est une suite finie d’étapes sans ambiguïté. On admet que tout ce qu’un algorithme peut accomplir, une machine de Turing peut l’accomplir aussi, et réciproquement. Les expressions « algorithme », « machine de Turing » et « ce qui est calculable » désignent donc la même chose. De plus, il existe une machine universelle, capable d’imiter n’importe quelle autre machine à partir de sa description, qu’elle reçoit en entrée. C’est le principe de l’ordinateur moderne : un seul appareil physique qui, selon le programme qu’on lui fournit, sert de traitement de texte, de jeu vidéo ou de calculatrice. Votre téléphone est, en ce sens, une machine universelle de Turing.

Turing laisse ainsi aux fondateurs de l’IA un pari implicite : si penser n’est qu’une forme de calcul (manipuler des symboles selon des règles), et si une machine peut tout calculer, alors une machine devrait pouvoir penser. Tout le programme de recherche des décennies suivantes, que nous suivrons dans ce module, découle de ce raisonnement. Turing laisse cependant ouverte une question qui sera centrale dans la suite : penser se réduit-il vraiment à calculer ?

Pour aller plus loin : qu’est-ce qu’une machine de Turing, concrètement ?

Une machine de Turing comprend un ruban de papier infini divisé en cases, une tête qui se déplace le long du ruban en lisant et en écrivant un symbole à la fois, et une petite table de règles de la forme « si je suis dans l’état A et que je lis un 0, alors j’écris un 1, je me déplace d’une case vers la droite et je passe à l’état B ». Elle ne comprend rien d’autre, ni grande mémoire ni intelligence cachée, seulement des symboles, des règles et un état courant. Ce mécanisme minimal suffit pourtant à exprimer n’importe quel calcul réalisable par n’importe quel ordinateur, aussi puissant soit-il. Voici un exemple complet. La machine ci-dessous calcule une fonction précise, ajouter 1 à un nombre écrit en binaire, avec trois états et six règles. Dans l’état droite, elle avance sans rien changer jusqu’à dépasser le dernier chiffre. Elle revient ensuite vers la gauche dans l’état retenue et fait la même chose que vous lorsque vous posez une addition. Tant qu’elle lit un 1, elle écrit 0 et reporte la retenue à gauche. Dès qu’elle lit un 0 (ou une case vide, si le nombre n’était composé que de 1), elle écrit 1 et s’arrête. Suivez l’exécution ligne par ligne : onze, 1011, devient douze, 1100, en huit pas.

La machine ne sait pas qu’il s’agit de nombres et ne connaît ni « onze » ni « douze ». Elle lit un symbole, consulte sa table, écrit, se déplace et change d’état. Le sens existe pour nous, mais pour elle il n’y a que la règle. Des machines un peu plus grandes additionnent, multiplient ou trient. On peut aussi en construire une, dite universelle, qui lit sur son ruban la table de n’importe quelle autre machine et l’exécute. C’est exactement l’idée d’un ordinateur et de son programme.

Une fois qu’on connaît une machine à trois états, on peut se poser une question d’apparence simple : parmi toutes les machines à n états qui finissent par s’arrêter, laquelle effectue le plus de pas avant de s’arrêter ? On appelle cette machine le castor affairé (busy beaver), et le nombre de pas qu’elle effectue est une fonction de n. Les premières valeurs sont petites : 6 pas pour deux états, 21 pour trois, 107 pour quatre. Pour cinq états, la réponse, 47 176 870 pas, n’a été établie qu’en 2024 par une collaboration internationale d’amateurs, le Busy Beaver Challenge. Ce groupe a dû examiner une à une des dizaines de millions de machines et faire vérifier sa preuve par ordinateur. Pour six états, on sait seulement que le nombre dépasse tout ce qu’on peut raisonnablement écrire. Au-delà, la difficulté devient une impossibilité, car cette fonction est non calculable (uncomputable). Aucun algorithme ne peut la donner pour tout n, parce que la connaître permettrait de savoir, pour n’importe quelle machine, si elle s’arrêtera un jour. Il suffirait de laisser tourner la machine pendant le nombre de pas du castor affairé. Si elle tourne encore après ce nombre de pas, elle ne s’arrêtera jamais. Il s’agit en fait du problème de l’arrêt, présenté plus bas, sous une autre forme. On a donc une suite de nombres parfaitement définis, dont les premiers sont petits, mais dont on ne connaîtra jamais que les tout premiers termes. Elle montre concrètement où se trouve une limite du calcul.

La machine de Turing ne sert pas à calculer rapidement. Elle sert à définir précisément ce que « calculer » veut dire. L’idée que tout procédé de calcul imaginable se ramène à une machine de Turing porte d’ailleurs un nom, la thèse de Church-Turing.

L’ombre de Gödel

L’idée que penser revient à calculer comportait pourtant une limite, établie presque au même moment. En 1931, cinq ans avant la machine de Turing, un jeune logicien autrichien, Kurt Gödel, avait démontré un résultat qui a profondément remis en question les fondements des mathématiques, son théorème d’incomplétude (incompleteness theorem).

Kurt Gödel étudiant, vers 1925. Domaine public — Wikimedia Commons.

Le résultat est simple à énoncer. Tout système de règles formelles assez puissant pour faire de l’arithmétique contient des énoncés qui sont vrais, mais que le système est incapable de prouver. La vérité dépasse donc toujours la démonstration, et aucun ensemble de règles, aussi complet soit-il, ne peut tout capturer. La preuve repose sur une idée qui sera importante pour nous, l’auto-référence (self-reference). Gödel construit, à l’intérieur du système, un énoncé qui parle de lui-même et qui affirme en substance : « Cet énoncé n’est pas démontrable. » Si le système démontrait cet énoncé, il prouverait quelque chose de faux. Il ne peut donc pas le démontrer, et c’est précisément pour cette raison que l’énoncé est vrai. Le système ne peut pas sortir de cette boucle.

Turing a lui-même prolongé ce résultat. Sa machine de 1936 servait aussi à montrer qu’il existe des questions qu’aucun algorithme ne pourra jamais trancher. La plus connue est le problème de l’arrêt (halting problem) : déterminer, pour un programme donné, s’il finira par s’arrêter ou s’il tournera à l’infini. Celui qui a proposé l’idée « penser = calculer » a donc aussi établi les frontières du calcul. Le projet de l’IA comporte ainsi, dès son origine, la reconnaissance de ses propres limites.

Pour la question de savoir si une machine peut penser, on a tiré de Gödel deux conclusions opposées. Toutes deux reviendront jusqu’à la fin du cours.

Première lecture : le théorème est une limite. Le physicien Roger Penrose en a tiré l’argument le plus connu contre l’IA. Selon lui, nous, humains, sommes capables de voir qu’un tel énoncé est vrai, alors que la machine ne le peut pas. Si notre esprit saisit une vérité qu’aucun système formel ne peut prouver, c’est qu’il ne se réduit pas à un système formel, autrement dit que penser ne se ramène pas à du calcul. Nous reviendrons en détail sur cette thèse au Module 5, avec celle d’un autre critique connu de l’IA, le philosophe John Searle.

Seconde lecture : le théorème est une source. Pour le penseur américain Douglas Hofstadter (auteur du livre Gödel, Escher, Bach (1979), où il développe précisément cette idée), la boucle auto-référentielle de Gödel n’est pas un défaut, mais le fondement même de l’esprit. Un système assez riche pour se représenter lui-même produit une « boucle étrange » (strange loop). Selon Hofstadter, c’est de ce retour sur soi que naîtraient le sentiment d’un « je », le sens et la conscience. L’auto-référence n’empêcherait donc pas la machine de penser, elle en serait la source. Nous retrouverons Hofstadter et ses idées à plusieurs reprises dans ce module.

Le même théorème conduit donc à deux conclusions inverses : l’auto-référence est soit une limite infranchissable, soit l’origine de l’esprit. Ce désaccord n’est toujours pas tranché. Il faut surtout retenir que, dès son origine, le projet d’une pensée mécanique s’accompagne de questions sur ses limites.

Pour aller plus loin : ce que dit, et ne dit pas, le théorème de Gödel

Le théorème s’applique à tout système formel cohérent (sans contradiction) et assez riche pour exprimer l’arithmétique. Gödel établit en fait deux résultats. Un tel système ne peut pas prouver tous les énoncés arithmétiques vrais (premier théorème), et il ne peut pas non plus prouver sa propre cohérence (second théorème). L’outil technique central est le codage de Gödel (Gödel numbering), qui consiste à numéroter chaque énoncé pour que le système puisse, en parlant de nombres, parler de lui-même. Gödel peut ainsi construire la phrase « je ne suis pas démontrable ».

Cette phrase est une variante du paradoxe du menteur (liar paradox : « cette phrase est fausse »), dont Gödel s’est explicitement inspiré. Le paradoxe du menteur aboutit à une contradiction. Gödel remplace « faux » par « indémontrable », si bien que sa phrase ne se contredit pas. Elle est simplement vraie sans être démontrable. Ce remplacement transforme un paradoxe sans issue en théorème.

La science-fiction a souvent prêté ce paradoxe aux humains pour piéger les machines. Dans l’épisode « I, Mudd » de la série Star Trek (1967), le capitaine Kirk et l’escroc Harry Mudd mettent hors d’état de fonctionner un androïde en lui servant une variante du paradoxe du menteur.

Il faut éviter deux contresens. Le théorème ne dit pas que « les mathématiques sont fausses », ni que la vérité serait une affaire d’opinion. C’est une limite précise sur ce qu’une démonstration formelle, à l’intérieur d’un système donné, peut atteindre. On peut toujours prouver l’énoncé en question dans un système plus puissant, mais ce nouveau système aura à son tour ses propres énoncés indémontrables. Quant à l’argument de Penrose, il reste contesté. Ses critiques objectent que rien ne garantit qu’un humain puisse réellement « voir » la vérité de cet énoncé sans supposer d’avance, sans justification, la cohérence du système.

Une fin tragique, et une porte qui s’ouvre

La vie de Turing se termine tragiquement. En 1952, il est poursuivi par la justice britannique en raison de son homosexualité, alors illégale, et condamné à subir un traitement hormonal, une castration chimique. Écarté et privé de son habilitation de sécurité, il meurt en 1954, à 41 ans, empoisonné au cyanure, dans des circonstances qu’on a longtemps considérées comme un suicide. Il ne verra pas les machines pensantes qu’il avait imaginées. Le gouvernement britannique présente des excuses officielles en 2009, et Turing reçoit une grâce royale posthume en 2013.

Turing a posé la question et proposé une orientation, la pensée comme calcul, mais il n’a pas précisé comment construire concrètement une machine intelligente. Cette tâche revient à la génération suivante. Dès le départ, celle-ci se divise entre deux réponses rivales, apparues presque en même temps, qui reposent sur deux conceptions très différentes de l’intelligence. C’est le sujet de « Deux paris rivaux ».