La loi des cycles de taille et de construction · Série IA · 03

Turing invente une machine pour prouver qu’une chose est impossible

Han Qin · Environ 29 minutes · Publication

I. Le problème principal

Calculer suivant des règles a cette particularité : celui qui sait faire le calcul n’a pas besoin de le comprendre.

Donnez à quelqu’un une addition. En posant les chiffres en colonnes et en procédant dans l’ordre, il peut trouver le bon résultat sans savoir ce que les nombres représentent. La règle est sur le papier ; il n’a qu’à l’exécuter.

À la fin du XIXe siècle, des mathématiciens se demandèrent si l’on pouvait faire ainsi pour tous les problèmes des mathématiques. Prenez n’importe quelle formule de logique du premier ordre. Existe-t-il des règles fixes qui permettent de dire en un nombre fini d’étapes si la formule vaut sous toute interprétation ?

Ce qu’on voulait, ce n’était pas qu’une personne intelligente y réfléchisse. C’était que quelqu’un qui ne comprenait pas puisse y arriver en suivant les consignes.

On appelait alors un tel ensemble de règles une procédure. Son existence était, selon un manuel de 1928, le problème principal de la logique mathématique.

Cette procédure n’existe pas. On l’a prouvé en 1936. Pour pouvoir l’affirmer sans réserve, l’auteur de la preuve a d’abord dû définir entièrement ce qu’était une procédure. Et pour la définir, il a inventé une machine.

Cette machine a ensuite servi de modèle à l’ordinateur.

En 1928, un éditeur berlinois publia les Éléments de logique théorique, manuel de David Hilbert et Wilhelm Ackermann. Hilbert, professeur de mathématiques à Göttingen, était l’une des grandes figures de sa discipline. Ackermann était son élève.

Le livre posait un problème : étant donné une expression logique, trouver une procédure qui permette de décider, en un nombre fini d’opérations, si elle vaut sous toute interprétation, ou du moins si elle vaut sous l’une d’elles.

Sur la même page, un jugement : le problème de la décision doit être appelé le problème principal de la logique mathématique.

Ce n’est pas une recommandation. Le livre tranche. Il dit « doit ».

Il ne dit pas que le problème est intéressant ou mérite une étude. Il dit qu’il est le principal. Lorsqu’une discipline désigne ainsi son centre, ce point devient la mesure de tout le travail qui suivra. Qui résout ce problème accomplit ce que la discipline s’est donné à faire. Si l’on prouve que la chose est impossible, la discipline doit changer de forme. En 1928, le livre ne faisait pas de place à cette seconde issue. C’était un manuel. Ce qu’on écrit dans un manuel, des élèves sont censés l’apprendre, pas le mettre en doute. Inscrire un problème dans un manuel, c’est déclarer qu’il est en bonne et due forme. Et l’on s’attend à ce qu’un problème en bonne et due forme ait une réponse.

La demande avait un précédent. Dans la liste des problèmes que Hilbert présenta à Paris en août 1900, le dixième réclamait, pour toute équation d’une certaine classe, une procédure pour décider en un nombre fini d’opérations si elle a des solutions entières. En 1900, la portée était plus étroite : la décision concernait une classe précise d’équations arithmétiques. Mais les mots étaient les mêmes : procédure, nombre fini d’opérations, décision. En vingt-huit ans, la portée s’était accrue, pas la forme de la demande. Dans l’introduction du même discours, Hilbert disait aussi qu’un problème mathématique bien posé devait recevoir une solution déterminée, ou une preuve qu’il était impossible de le résoudre. Cette dernière proposition était alors une issue de secours. Trente-six ans plus tard, ce fut la porte principale.

À Zurich, en 1917, Hilbert inscrivit la décidabilité, notamment par un nombre fini d’opérations, parmi les objets à étudier. En 1922, Heinrich Behmann fit entrer le problème de la décision dans le titre même d’un article. Décider du vrai et du faux devait, écrivait-il, se ramener à un calcul mécanique effectué suivant des instructions fixées. La demande était désormais explicite : des consignes qu’on puisse suivre sans réfléchir. Durant le semestre d’hiver 1922-1923, Hilbert et Paul Bernays donnèrent à Göttingen un cours sur les fondements logiques des mathématiques.

Entre 1900 et 1928, la demande se fit de plus en plus précise. Une chose n’y fut pourtant jamais précisée.

Qu’est-ce qu’une procédure ?

De quels gestes parle-t-on dans « un nombre fini d’opérations » ? Jusqu’où va le « mécanique » de ce calcul qui suit des instructions fixées ? Personne ne l’avait défini, parce qu’en 1928 il ne semblait pas nécessaire de le faire. Un mathématicien savait reconnaître un algorithme quand il en voyait un. Puisqu’il le reconnaissait, pourquoi le définir ?

Pour prouver qu’une chose est impossible, on ne peut pas passer outre. Il faut d’abord faire le tour de toutes les possibilités sans en oublier une. Sans cela on ne peut pas dire que la chose n’existe pas, seulement qu’on ne l’a pas trouvée. Ne pas trouver n’est pas une preuve. Il faut dessiner toutes les formes possibles pour pouvoir dire qu’aucune ne convient. Voilà la forme de l’article de Turing : construire une cage aussi grande que possible, puis prouver que quelque chose reste dehors. Plus la cage est grande, plus la preuve de ce qui reste dehors a de force. La neuvième section explique précisément pourquoi la cage enferme tout ce qu’elle doit enfermer. Turing ferme une à une les ouvertures qu’on pourrait lui signaler ; pour chacune, il prend une chose à la personne qui fait le calcul.

Pendant vingt-huit ans, on avait donc réclamé une procédure sans définir la forme que prendrait cette chose. La demande était établie, ce qu’elle réclamait n’avait pas de forme. La construction tendait la main au-dehors pour saisir quelque chose qu’elle ne savait pas encore nommer. Si la suite a pu se produire, c’est que quelqu’un est d’abord revenu sur ses pas pour construire cette chose sans nom.

II. Deux salles

Septembre 1930, Königsberg. Deux choses se produisent dans la même semaine. Par la suite on les confondra souvent.

L’une passe aujourd’hui pour avoir refait la discipline. Quand elle eut lieu, personne dans la salle ne prit la parole. Plus d’un an dut passer, jusqu’à la publication de l’article, avant qu’on voie peu à peu ce qui s’était passé. Souvent, au moment où une chose se fait, elle n’a pas de forme. La forme s’imprime plus tard sur le papier.

La première eut lieu du 5 au 7 septembre, à la deuxième conférence sur l’épistémologie des sciences exactes, organisée par un groupe de philosophie empirique. Il y avait alors plusieurs écoles qui ne s’entendaient pas sur les fondements à donner aux mathématiques. Le 5, chacune eut une heure de parole ; John von Neumann exposa la position de l’école de Hilbert. D’autres conférences suivirent le 6. Un Viennois de vingt-quatre ans, Kurt Gödel, disposait de vingt minutes pour parler d’un travail qu’il venait de terminer.

Le dimanche 7, une discussion sur les fondements des mathématiques fut organisée sous la présidence de Hans Hahn. Von Neumann et Gödel y prirent la parole. Vers la fin de la discussion, Gödel annonça un résultat qu’il n’avait pas encore officiellement publié.

La seconde chose fut la conférence de Hilbert le 8 septembre : « Connaissance de la nature et logique ». Elle n’appartenait pas au colloque précédent, mais au congrès des naturalistes et médecins allemands qui se tint ensuite dans la même ville. Il existe aussi une version radiodiffusée d’environ quatre minutes. On en a conservé l’enregistrement, qui se termine ainsi : « Nous devons savoir. Nous saurons. »

C’est aux mathématiques que s’adressait cette phrase. Hilbert refusait d’admettre que quelque chose pût être inconnaissable par principe. Il s’opposait à une idée courante : certaines choses resteraient à jamais hors de la compréhension humaine, et il fallait s’en tenir là. C’est ce point final qu’il refusait. Six ans après, de sa propre discipline sortit une preuve que cette voie ne menait nulle part. Or cette preuve n’avait pas la forme du point final auquel il s’opposait. Elle ne disait pas que les gens ne parviendraient pas à comprendre. Elle disait que la chose elle-même n’existait pas. On confond souvent ces phrases ; dans cette série, elles occupent des places tout à fait différentes. L’une concerne les limites humaines, l’autre la forme du monde.

Ces deux événements se touchent, à un jour de distance. On les met souvent en scène comme un seul : à peine une déclaration prononcée, le résultat qui l’annule se fait entendre dans la pièce à côté.

Les documents de la semaine ne montrent aucune rencontre entre les deux hommes. Le nom de Hilbert ne figure ni parmi les participants ni parmi les intervenants à la discussion du 7. Pas une ligne ne dit si Gödel écoutait la conférence le lendemain. Deux salles, deux réunions, et rien ne dit qu’elles se soient entendues.

La scène composée plus tard fait tenir une affaire compliquée en une phrase. Dans les papiers de cette semaine-là, il y a des dizaines de personnes réparties entre deux réunions. Chacune y tient son propos. L’une annonce un résultat le dimanche après-midi, peu avant la fin, et personne ne lui répond.

L’article de Gödel parut en 1931 dans une revue mensuelle de mathématiques. Il traitait d’une question voisine mais distincte. Dans le type de systèmes formels qu’il étudiait, pourvu qu’ils puissent exprimer l’arithmétique et remplissent la condition de cohérence voulue, il y a des énoncés dont on ne peut prouver ni l’affirmation ni la négation. Par système, on entend ici un ensemble de ce genre dont les règles ont été fixées.

Cela ne réglait pas le problème du manuel. Le problème de la décision demandait une procédure valable pour toute formule de logique du premier ordre. L’article de 1931 parlait d’énoncés à l’intérieur de certains systèmes. En 1936, la question de la décision restait ouverte.

III. Trois manuscrits en 1936

En 1936, trois manuscrits arrivèrent l’un après l’autre, de trois personnes qui empruntaient des chemins différents. Toutes s’étaient heurtées au même problème : comment préciser ce que c’est que calculer suivant des règles. L’une fait un calcul de fonctions et de substitutions ; l’autre emploie une bande et une table de conduite ; la troisième, une rangée de cases et quelqu’un qui travaille sur consignes. Des idées voisines peuvent naître séparément, mais il faut encore travailler pour prouver qu’elles reviennent à la même chose. Une fois la preuve faite, on dirait qu’il n’y a jamais eu qu’un seul chemin.

En mars, dans le premier numéro d’une nouvelle revue de logique symbolique, Alonzo Church, de Princeton, publia une note de deux pages qui portait le problème de la décision dans son titre. En avril, dans une revue américaine de mathématiques, il publia un article de dix-neuf pages : « Un problème insoluble de la théorie élémentaire des nombres ».

Le 28 mai, la London Mathematical Society reçut le manuscrit d’un chercheur de King’s College, Cambridge : Alan Turing, vingt-trois ans. L’article s’intitulait « Sur les nombres calculables, avec une application au problème de la décision ». Il fut présenté le 12 novembre et publié en trente-six pages.

Le 7 octobre, la revue de logique symbolique reçut le troisième manuscrit. L’auteur était le mathématicien américain Emil Post. Le titre : « Procédés combinatoires finis. Formulation I ». Trois pages, le plus court des trois textes. Il parut dans une revue encore jeune, dont l’un des rédacteurs était l’auteur des articles de mars et d’avril. Le même nom revient trois fois cette année-là : comme auteur, comme celui qu’un autre chercheur rattrape, puis comme rédacteur recevant le troisième texte. L’année suivante, il reviendra comme auteur d’un compte rendu et comme directeur de recherche. C’est lui aussi qui donnera son nom à la machine.

Dès le début de l’article, Turing reconnaît que les récents travaux de Church ont donné le résultat d’impossibilité. Dans un appendice, il démontre l’équivalence de sa calculabilité et de la définissabilité de Church.

L’appendice montre que l’article fut modifié après son envoi. Quelqu’un d’autre avait trouvé la conclusion le premier. Turing devait désormais prouver que son propre chemin et celui de l’autre conduisaient au même endroit. Cette preuve ne faisait pas partie du projet initial. C’est la chronologie qui l’a imposée.

Turing écrivait encore l’année suivante au début d’un article comparant les deux formulations que la sienne était peut-être plus convaincante. Les deux choses étaient équivalentes en mathématiques, non par leur pouvoir de convaincre. La différence n’était pas dans la conclusion, mais dans la forme de ses raisons.

Au bas des trois pages de Post, une note de la rédaction invitait à comparer l’article de Turing à paraître et précisait que, malgré sa date plus tardive, le texte de Post avait été écrit de façon entièrement indépendante.

Voici donc ce qu’établit l’année 1936. Church et Turing démontrèrent séparément que le problème de la décision était insoluble. Post proposa indépendamment un autre modèle de calcul, qu’il prévoyait équivalent à la récursion dont parlaient Gödel et Church. Ses trois pages ne constituaient pas une troisième preuve de la même conclusion.

L’équivalence entre deux définitions formelles fut plus tard considérée comme un indice important. Mais, pour Turing en 1936, il fallait d’abord travailler à montrer que sa méthode et celle de Church calculaient les mêmes choses. Alors seulement il pouvait indiquer où les chemins se rejoignaient.

En 1937, Turing publia un correctif de trois pages, en précisant que Bernays avait relevé l’erreur dans le texte original. Moins d’un an après la parution d’un article qu’on ne cesserait d’appeler fondateur, quelqu’un y avait trouvé une erreur. Elle fut corrigée. La machine et le résultat tenaient toujours.

IV. Celui qui est en train de calculer

Au début de la neuvième section, Turing concède que, jusque-là, il n’a pas démontré que son sens formel de « calculable » contient tout ce qu’on appelle d’ordinaire calculable.

Il donne trois genres de raisons. Le premier fait directement appel à l’intuition ; le deuxième établit l’équivalence de définitions différentes ; le troisième fournit de nombreux exemples.

Ce qu’il examine pour donner ce genre de raisons, c’est quelqu’un qui calcule avec du papier et des signes.

En anglais, en 1936, le mot computer désigne une personne. C’est un métier, un titre qu’on peut mettre sur un curriculum vitae. Des gens sont assis à leur table, calculent suivant les règles qu’on leur a données et produisent des tables. Astronomie, navigation, assurances : leurs tables sont faites ainsi. Ces gens sont partout à l’époque. La plupart sont payés pour un travail répétitif. On les assied en rang dans une salle, chacun chargé d’un morceau. Des décennies plus tard, le mot passe à la machine. Les personnes qui faisaient le travail reçoivent un autre nom ou n’en ont plus. Quand le nom d’un métier passe à une machine, c’est souvent que ce travail ne compte plus comme travail. Dans cette section, Turing désigne la personne qui calcule par « il ».

Il écrit qu’à chaque instant le comportement de la personne est déterminé par les signes qu’elle observe alors. Il ajoute aussitôt un autre facteur : l’état dans lequel se trouve à cet instant son esprit.

Il y a donc deux choses dans le modèle dès le départ : les signes visibles et l’état invisible. Tout le mouvement de la section consiste à rendre le second visible à son tour. Si on ne le peut pas, on le remplace. C’est la méthode du troisième argument de la neuvième section, et celle de l’article entier.

Il resserre ensuite, point par point. Le procédé est toujours le même : partir de ce qu’une personne peut faire, et non de ce qui arrange les mathématiques.

Le papier a généralement deux dimensions. Turing en fait une bande divisée en cases. Il ne dit pas que les gens se servent réellement de bandes. Il dit que les deux dimensions ne sont pas essentielles au calcul et qu’on peut s’en passer.

Le nombre de signes doit être fini. La raison qu’il donne vient de l’expérience, non des mathématiques. Si l’on traite une longue suite de caractères comme un seul signe composé, elle finit par être trop longue pour qu’on la reconnaisse d’un coup d’œil. Turing prend pour exemple deux très longues suites de neuf : on ne peut pas voir d’un coup si elles sont identiques.

C’est une raison d’expérience, pas une raison formelle. Pour définir un concept de base dans la discipline la plus soucieuse de rigueur, Turing prend pour preuve que l’œil humain ne suffit pas. À cet endroit, il mesure la limite du modèle à une faculté humaine : ni par la physique ni par la logique, mais par ce qu’on peut voir d’un coup d’œil. Plus tard, on y verra souvent une propriété de la machine elle-même.

Le nombre de cases qu’on peut observer à un instant donné a une borne, désignée par une lettre. Pour en voir davantage, il faut continuer de regarder, les unes après les autres.

Les états de l’esprit à prendre en compte doivent être en nombre fini eux aussi. S’il y en avait une infinité, certains pourraient être aussi proches qu’on veut et se confondre. Quant aux états compliqués, on peut en déplacer une partie et l’inscrire sous forme de signes supplémentaires sur la bande.

Il y a un geste dans cette phrase : déplacer au-dehors. Si l’esprit a trop de choses à contenir, on en écrit sur le papier. Ce qui est sur le papier n’est plus dans l’esprit. Moins il reste dans l’esprit, moins il faut supposer ; moins il faut supposer, mieux l’argument tient. Toute la section verse ainsi dehors ce qui se trouvait dedans : elle le verse sur le papier jusqu’à ce qu’il ne reste plus rien à l’intérieur.

L’endroit où se pose ensuite le regard a lui aussi une limite. La nouvelle case observée ne peut s’éloigner de la précédente au-delà d’une distance fixée. Turing envisage une objection : une case numérotée au loin ne pourrait-elle pas être reconnue d’un coup ? Si le numéro est long, répond-il, il faut encore en vérifier les caractères un à un.

À partir de ces hypothèses, il construit une machine qui reproduit le travail de calcul de cette personne. À chaque état de l’esprit qu’elle prend en compte correspond une configuration interne de la machine. Celle-ci examine le nombre voulu de cases, puis déplace son regard dans les limites de la distance fixée.

Ce que la machine peut reproduire, c’est le procédé de calcul symbolique que l’on vient d’analyser. Autrement dit, le travail de quelqu’un qui calcule suivant des règles. C’est un travail précis, monotone, pour lequel on payait déjà des gens.

À l’automne de la même année, quelqu’un donne en trois pages une autre forme à la même idée. Post imagine une rangée de cases qui s’étend à l’infini dans les deux sens. Chaque case est soit vide, soit marquée. Il appelle celui qui y travaille le résolveur, ou l’ouvrier. À partir d’une case, l’ouvrier suit des consignes fixes, qu’il ne peut pas modifier. Ses gestes de base : voir si la case où il se trouve est marquée, effacer, marquer, avancer d’une case à droite ou à gauche.

L’Atlantique sépare les deux manuscrits. Ils n’ont pas les mêmes mots, mais ils partent de la même chose : une personne, du papier et des règles qu’on ne peut pas changer.

Les deux hommes cherchent chacun de leur côté ce qu’est un calcul. La première chose qui leur vient à l’esprit est quelqu’un en train de travailler. Pas une horloge, pas un métier à tisser, pas un circuit électrique. Ils veulent faire un modèle du calcul. Et ce qu’il y a alors au monde de plus semblable au calcul, c’est quelqu’un qui calcule suivant des règles.

V. Le billet sur le papier

Dans la neuvième section, le troisième argument procède encore autrement. Turing trouve sur le papier un substitut à l’état de l’esprit. Son premier argument admettait quelque chose que personne d’autre ne pouvait voir ni vérifier ; or l’article entier s’efforçait d’établir une chose sans laisser de prise au doute.

Turing imagine que le calculateur humain peut s’arrêter, s’en aller, oublier son travail, puis y revenir en suivant les consignes d’un billet laissé sur le papier. Avec les signes déjà inscrits sur la bande, ce billet donne un équivalent matériel plus précis de l’état de l’esprit.

Il ne dit pas que l’état de l’esprit n’existe pas. Il ne dit pas qu’il est sans importance, et n’enquête pas pour savoir ce qu’il est. Il trouve quelque chose qui permet à l’argument de continuer sans lui. Là où se trouvait auparavant une chose que personne d’autre ne pouvait examiner, il pose une feuille. On peut la faire lire, la copier, la vérifier, ou la prendre pour poursuivre le travail. Dès que quelqu’un d’autre peut s’en charger, on n’a plus besoin de la personne qui le faisait. En 1936, c’est un pas dans un argument ; au cours du siècle suivant, ce sera la situation de bien des gens. Dans cette section, il n’y a encore qu’une commodité de preuve, qui permet de retirer une hypothèse impossible à vérifier.

Il va jusqu’à faire exécuter un seul pas à la fois par la personne qui s’assied : une fois le pas effectué, elle laisse de nouvelles consignes pour la suite. Ainsi tout l’état du calcul à ce moment-là est écrit dans le billet et dans les signes de la bande.

Cette personne peut être remplacée par une autre. L’autre s’assied, lit le billet, fait un pas, écrit le nouveau billet et s’en va. Qui fait le pas ne change pas le résultat, parce que tout ce qu’il faut faire se trouve sur le papier. À cet instant, la personne devient remplaçable. Dans le premier argument, elle conservait son état d’esprit. Dans le troisième, on la déplace sur le papier avec cet état d’esprit. Une fois le déplacement fait, peu importe qui occupe sa place.

On a continué d’employer cette méthode. Lorsqu’on tombe sur une chose hors d’atteinte dont on ne peut pas faire le tour, on lui trouve un substitut accessible, et l’argument continue. On juge le substitut à la possibilité de faire marcher l’argument. Quant à savoir ce qu’était vraiment la chose remplacée, on n’a désormais plus besoin de répondre.

Ce qu’il a fait, c’est un modèle d’un travail précis, avec du papier et un crayon. Ce que d’autres ont dit par la suite, c’est que ce modèle était celui de l’esprit. Il y a tout un chemin entre les deux phrases. Dans les trente-six pages de 1936, on n’en fait pas un pas.

On voit déjà une chose qui reviendra dans la série. Dès qu’un substitut entre dans un argument, il y reste. Si l’argument marche, le substitut devient la chose même. Celle qu’il a remplacée n’est ni réfutée ni reconnue ; on cesse peu à peu d’en parler.

VI. Une machine qui peut tenir lieu de toutes les autres

La sixième section s’intitule « La machine à calculer universelle ».

Dès le début, Turing écrit qu’on peut concevoir une seule machine. Il stipule ensuite qu’en y entrant la description standard d’une autre machine, on obtiendra la même suite que celle que calcule l’autre. La septième section donne la table complète de conduite de cette machine.

Elle reçoit donc la description d’une autre machine comme une donnée à traiter. La description et la chose décrite tombent sur une même bande : les spécifications de l’une deviennent les signes à traiter par l’autre. En 1936, ce geste n’est qu’une commodité de preuve. Il deviendra la prémisse de toute une industrie.

Une telle machine occupe une place particulière. Elle n’est pas la plus puissante d’une multitude de machines ; elle peut tenir lieu de n’importe laquelle d’entre elles. Elle peut faire tout ce qui se fait dans cette classe. Pour la première fois, la construction se referme dans sa propre classe : rien au-dedans ne lui échappe.

Les constructions précédentes poussaient vers le dehors. À chaque pouce gagné, il restait un pouce de moins au-dehors. Mais il restait toujours un dehors. Celle-ci est différente : elle remplit sa propre classe d’un seul coup, sans avoir à s’étendre davantage. Pour lui faire faire autre chose, inutile de la modifier ; il suffit de changer la suite de signes qu’on lui donne. On pouvait depuis longtemps changer les cartes du métier Jacquard ou les prémisses du piano de bois. Mais ce que l’on pouvait y changer relevait chaque fois des règles propres au dispositif. Turing sépare la machine de la chose qu’elle doit faire. Le mot machine change de sens : ce n’est plus un objet fait pour une tâche particulière, mais un objet qui attend qu’on lui en assigne une. La personne qui la lui assigne reste au-dehors. Quelle tâche lui donner, et qui en décide : la machine ne reprend aucune de ces deux questions, et l’article ne les traite pas. À chaque nouveau morceau de travail déplacé vers la machine, elles restent à la même place.

Or dans le même article, la huitième section donne un résultat négatif. Il n’existe pas de procédure générale qui, à la lecture de la description de n’importe quelle machine, détermine toujours si elle appartient à une certaine classe définie par Turing. La onzième section transpose cette indécidabilité dans la notation logique du manuel de 1928. La conclusion tombe : le problème qu’on avait appelé huit ans plus tôt le principal problème de la logique mathématique est insoluble.

Les deux choses se trouvent dans le même article. La construction se referme dans sa classe, et l’on prouve au même moment qu’elle a un dehors.

Mieux, ces deux choses sortent d’une seule démarche. Parce que toute machine de cette classe peut être écrite en signes et donnée à la machine universelle, on peut se servir de cette suite de signes pour établir le résultat. Parce qu’elle peut imiter sans exception les machines de sa classe, on peut poser la question à laquelle elle ne peut répondre. La fermeture et le dehors ne sont pas deux résultats : ce sont les deux faces d’un seul.

Et ce dehors n’est pas provisoire. Il ne disparaîtra pas avec le progrès technique. Une machine plus grande et plus rapide n’y entrera pas. L’existence de ce dehors a été démontrée.

Dans les deux articles précédents, des personnes traçaient la limite. Quelqu’un regardait une machine et disait : elle s’arrête ici. Cette fois, la limite ne vient pas d’un jugement humain ; on la déduit des règles que suit la machine. Personne ne la déplacera en changeant simplement d’avis. Dès lors, quand on dit qu’une machine ne peut pas faire quelque chose, on peut demander : de quelle sorte d’impossibilité s’agit-il ? Pour la première fois dans cette série, le reste ne vient pas de quelqu’un qui le désigne du doigt. Il se déduit des règles de la construction elle-même.

Prenons le problème de l’arrêt, plus familier aujourd’hui, pour donner la forme de ce genre d’argument. Si la procédure de décision existait, on pourrait s’en servir pour construire une machine qui se contredit par principe : chaque fois que la procédure dit qu’elle fera quelque chose, elle fait exprès de ne pas le faire. Pour cette machine, la procédure ne donne plus de réponse cohérente, alors qu’elle devrait en donner une pour toute machine. L’hypothèse ne tient donc pas. On appelle cela un raisonnement diagonal. Dans sa huitième section, Turing se demandait si une machine peut continuer à produire une suite et si l’on peut décider qu’elle imprimera un signe donné.

C’est pour arriver à ce point que l’article se sert de la machine.

Pour dire exactement qu’une chose est impossible, il faut d’abord dire ce qu’est faire une chose possible. Dans cet article, le possible prend la forme d’une machine. Ce qui deviendra un modèle du calcul est ici un maillon d’une conclusion négative.

Cette machine servait de preuve. Pour prouver qu’aucune procédure ne peut faire une chose, il faut d’abord dire les formes qu’une procédure peut prendre. Alors seulement on peut les ramasser toutes dans un filet et montrer la chose qu’aucune ne peut faire. La machine était ce filet. Turing l’avait tissé pour prendre les procédures, pas les machines. Une fois le filet fait, c’est lui qui est resté.

VII. Le nom est venu plus tard

Dans les trente-six pages, le mot intelligence ne paraît pas une seule fois.

Le mot esprit paraît, presque toujours à la neuvième section, dans l’expression qui revient pour désigner l’état de l’esprit de la personne. Ce n’est pas une affirmation que la machine a un esprit : c’est une variable du calculateur humain, que le billet du troisième argument remplace bientôt. On lit souvent cet article à l’envers : une variable au sujet d’une personne est devenue une promesse au sujet d’une machine.

On y rencontre aussi le mot penser, au sens courant de « je pense » ou « on pourrait penser ». L’article ne demande pas si les machines peuvent penser.

Pendant les quatre-vingts années suivantes, il passe souvent pour le point de départ de cette question. Il en résout une autre : cette procédure existe-t-elle ? On s’est posé la question de 1900 à 1936, pendant trente-six ans. La réponse est non. Pour pouvoir la donner, il a fallu définir entièrement ce que c’était que calculer. Après la définition, la réponse négative tient en quelques pages. Ce qui est resté, c’est la définition.

Il manque encore un autre mot : machine de Turing. Turing parlait de machine à calculer, de machine automatique, de machine à choix et de machine à calculer universelle.

Le nom apparaît dans le compte rendu que Church consacra à l’article en mars 1937. C’est le collègue qui avait obtenu le même résultat deux mois avant lui qui lui donna ce nom, dans son compte rendu, l’année après la publication. Church y fait aussi une comparaison directe : avec la calculabilité de Turing, l’identité avec le sens ordinaire de « procédure effective » devient immédiatement claire. Celui qui le dit avait obtenu le résultat le premier, était un des rédacteurs fondateurs de la revue et allait diriger Turing pendant les deux années suivantes.

Les autres noms vinrent plus tard. Le logicien Stephen Kleene commença à parler de « thèse de Church » dans un manuel de métamathématiques en 1952. Le nom qui associe Church et Turing vient d’un livre de Kleene de 1967. Aucun des trois auteurs de 1936 ne parlait ainsi. Il fallut trente et un ans pour que les deux noms soient réunis, et l’un des deux hommes n’était alors plus là. Ce sont d’autres qui donnent le nom, en l’absence de l’intéressé. C’est la troisième fois que la chose arrive dans cette série.

Quant aux noms, Post avait laissé un avertissement à la dernière de ses trois pages.

Il disait de l’identification faite par Church entre la calculabilité effective et une certaine classe formelle qu’elle était une hypothèse de travail à vérifier encore. Il refusait qu’on dissimule cette identité sous le mot définition. La phrase se termine sur ce risque : nous rendre aveugles à la nécessité de la vérifier constamment.

C’est écrit en 1936, au moment où l’on vient de faire la chose. Post montre déjà que l’appeler définition revient à annoncer qu’elle n’a plus besoin d’être vérifiée.

Il ne tient pas seulement à une nuance technique. Une définition est une convention ; la convention n’a pas à répondre devant le monde. Une hypothèse avance quelque chose, et doit toujours pouvoir être démentie. Le nom sous lequel on range une même proposition décide si quelqu’un doit encore aller y voir. Voilà ce que Post veut préserver : qu’un nom ne vienne pas clore l’affaire à la place de tout le monde.

Or les noms qui finirent par s’imposer se relayèrent : définition, puis thèse. Lorsque Post écrivait, ces deux noms n’existaient pas encore.

VIII. Laquelle Gödel a-t-il retenue ?

Turing arriva à Princeton vers la fin de septembre 1936. Il y fit deux ans d’études supérieures sous la direction de Church et obtint son doctorat en 1938. En avril de cette année-là, von Neumann lui proposa de rester comme assistant. Il refusa et retourna à Cambridge.

Pendant ces deux années, Gödel ne se trouvait pas à Princeton. Il ne reste entre les deux hommes ni lettre, ni compte rendu de rencontre, ni article commun. Leurs noms sont souvent mis côte à côte par la suite, tant il paraît naturel de les rapprocher.

Avant Turing, Gödel n’était pas satisfait de la formulation de Church. Dans une lettre de novembre 1935, Church racontait que Gödel trouvait tout à fait insatisfaisant de définir la calculabilité effective par la définissabilité. À ce moment-là, il penchait plutôt pour commencer par des axiomes de la calculabilité effective.

En 1946, dans une conférence de mathématiques pour le bicentenaire de Princeton, Gödel déclara que l’importance du résultat tenait à ce qu’il donnait pour la première fois une définition absolue, indépendante de la notation choisie. Il insistait sur le caractère absolu de la notion : changez de système formel, la notion ne change pas. Il dit « pour la première fois ». À ses yeux, les essais antérieurs à 1936, y compris ses cours de Princeton en 1934, n’allaient pas jusque-là. Chacune des définitions précédentes restait attachée à une notation ; en changer obligeait à recommencer.

En 1963, il ajouta une note à l’article de 1931. Grâce en particulier au travail de Turing, écrivait-il, on pouvait désormais donner du concept général de système formel une définition précise et indiscutablement adéquate. La caractéristique d’un système formel au sens propre, ajoutait-il, est que le raisonnement y peut, en principe, être intégralement remplacé par un dispositif mécanique.

Une note écrite en 1963, placée à la suite d’un article de 1931. Trente-deux ans après, Gödel revient y ajouter ce qui faisait alors défaut : ce qu’est un système formel. Et ce qui comble le manque, c’est un modèle construit en 1936 pour une autre affaire.

En 1964, il écrivit un post-scriptum à ses notes de cours de 1934 : Turing avait analysé le concept de procédure mécanique. Dans le même post-scriptum, Gödel laissait une autre question ouverte. Existe-t-il des procédures finies qui ne soient pas mécaniques ?

Celui qui donnait son aval disait dans le même document qu’il n’avait pas étendu le résultat jusqu’à définir l’ensemble des processus de l’esprit humain. Il reconnaissait une chose précise : le concept de procédure mécanique avait été analysé. Quant à savoir s’il y a quelque chose en dehors de ces procédures, il inscrivit la question sans y répondre.

Dans des conversations plus tardives, il alla plus loin. Avant Turing, disait-il, on n’avait pas clairement vu ce qu’est une procédure mécanique ; Turing en avait donné la bonne conception. Et la définition qui passe par l’exécution sur une machine de Turing est, à ses yeux, juste et unique.

Ici, le reste a été laissé par celui même qui donnait son aval.

Gödel reconnaissait pleinement le modèle, allant jusqu’à le qualifier d’indiscutablement adéquat. Au même endroit, il inscrivait la question plus vaste sur une autre ligne, sans étendre le modèle jusque-là.

En 1947, le philosophe Ludwig Wittgenstein écrivit dans un manuscrit : les machines de Turing, ce sont les personnes qui calculent.

La phrase suivante dit que ce dont parle Turing peut aussi être exprimé sous forme de jeu. Wittgenstein écrit ensuite sa propre variante d’un raisonnement diagonal et examine les positions où une règle devient une consigne sans sens. On cite souvent sa phrase pour parler de l’humain et de la machine ; quand il l’écrivait, il travaillait sur un problème diagonal.

Les lecteurs qu’on peut nommer dans les trois premières années sont ceux-ci. Newman connaissait et avait discuté le travail avant son envoi. Church en fit le compte rendu. Bernays le lut assez bien pour trouver une erreur. En février 1937, Turing demanda aussi qu’on envoie un tiré à part à Wittgenstein.

Voilà pour la liste : un professeur, un concurrent, un lecteur qui trouve une erreur, et un tiré à part envoyé.

En 1948, Newman publia dans une revue de la Royal Society les « Principes généraux de conception des machines à calculer universelles », où il discutait la machine universelle de Turing. Construire un ordinateur électronique universel était alors une question d’ingénierie. Or celui qui écrivait l’article était celui qui, douze ans plus tôt, avait exposé la question à Turing. À l’époque, dans son cours, c’était un problème de logique. Douze ans après, il écrivait des indications pour les ingénieurs. Le problème n’avait pas changé ; ce qu’on en faisait avait changé. La même chose avait servi à prouver une impossibilité, puis à expliquer comment concevoir une machine. On avait prouvé qu’une chose n’existait pas ; l’outil construit pour le prouver avait continué d’exister, au point de devenir un objet matériel. Cela reviendra dans cette série. La forme sera différente, la démarche la même.

La liste complète des auditeurs de ces journées de septembre 1930 n’existe pas. Devant qui Gödel prononça-t-il sa phrase ce dimanche après-midi ? Qui l’entendit ou ne l’entendit pas ? Personne ne saurait aujourd’hui en faire la liste. C’est pourtant une liste inexistante qui soutient la scène racontée plus tard.

Au printemps 1936, un homme de vingt-trois ans acheva un manuscrit pour prouver qu’une chose était impossible. Il détacha une machine du travail d’une personne assise à une table, en train de calculer. La machine fut ensuite construite, reçut divers noms et servit à poser une question qu’il n’avait pas soulevée une seule fois dans son article.

Quant à cette question, il ne la posa lui-même que quatorze ans plus tard. Il avait alors une vraie machine à sa disposition. Mais la personne dont on avait détaché cette machine, celle qui, assise à sa table, calculait suivant les règles, ne s’appelait plus computer.

On construit encore des machines. Quant à savoir où passe la limite, chaque génération le dit à nouveau.