Je reprends et termine ici ma lecture de l’article de Turing « Théorie des nombres calculables, suivie d’une application au problème de la décision ».
Nous nous étions arrêtés la dernière fois sur la description que Turing fait de sa fameuse machine.

Théorie des machines

Turing définit ensuite les a-machines, et les c-machines, pour préciser qu’il ne s’intéressera qu’aux premières. Les a-machines sont des machines automatiques n’ayant donc nul besoin d’intervention extérieure d’un opérateur pour fonctionner. Les c-machines sont des machines à choix « dont le comportement ne dépend que partiellement de sa configuration […] un opérateur extérieur doit intervenir et faire un choix arbitraire pour que la machine puisse continuer son travail. »1

Au sein des a-machines, il y place les machines à calculer, et au sein de ces dernières, il définit enfin les machines cycliques et acycliques. Les machines cycliques sont les machines qui finissent en gros par tourner en rond, et ne sont pas en mesure de calculer un nombre réel dont les décimales sont infinies. « Une machine qui n’écrit jamais qu’un nombre fini de symboles de la première famille [cette première famille de symboles est constituée des 0 et des 1 et compose les chiffres du nombre réel à calculer] est dite cyclique. Dans le cas contraire, elle est dite acyclique. »2

Cette bipartition des machines, cycliques et acycliques, permet ainsi à Turing de redéfinir ce qu’il appelle une séquence calculable et un nombre calculable. « Une séquence est dite calculable s’il existe une machine acyclique qui la calcule. Un nombre est dit calculable s’il existe une machine acyclique qui calcule sa partie décimale. »3

Comme on l’a déjà écrit, Turing a proposé l’idée de « nombre calculable » en prenant effectivement comme champ de recherche les nombres réels. « Le point crucial était que tout ‘nombre calculable’ régi par une loi définie pouvait être calculé par une de ses machines. Ainsi il y aurait une machine capable de calculer l’expansion décimale de π, car cela ne requérait en fait qu’un ensemble de règles pour additionner, multiplier, recopier, etc.»4. Même si dans le cas de π la machine ne s’arrêtera pas, (nous sommes alors dans le cas d’une machine acyclique) étant donné que son nombre de décimale est infini. La machine peut cependant être parfaitement définie dans une table, avec un nombre fini de règles.

Turing continue son article en présentant des exemples de machines à calculer, c’est-à-dire en faisant « tourner » littéralement le fonctionnement des machines abstraites qu’il vient de nous présenter. Car d’une part, il ne faut pas oublier que la machine que Turing vient de concevoir n’est en rien une machine concrète, matérielle. C’est une machine « de papier » comme l’écrira Turing lui-même, avec une mémoire infinie, ce qui est d’ailleurs matériellement impossible. C’est finalement une « Machine mathématique dont l’aspect infini introduit à tout jamais une rupture par rapport aux machines matérielles finies comme celles dont nous avons pris l’habitude d’être environnés. »5

Nulle part dans l’article Turing ne précisera comment cette machine pourrait être construite, comment s’agenceraient matériellement les différentes pièces qui pourraient la composer. C’est une « boîte noire » appelée à transformer des symboles. « Une machine de Turing est en effet une machine qui transforme des symboles d’entrée en symboles de sortie en traversant une succession d’états discrets qui sont tous définissables à l’avance. »6

D’autre part, comme le souligne encore Jean Lassègue, Turing a bien conscience que si l’on veut saisir son concept, il faut en passer par l’expérience cette fois très concrète de faire fonctionner la machine, d’effectuer soi-même les différentes étapes, c’est-à-dire finalement d’être soi-même la machine pendant le temps du calcul. « Le passage de la notion informelle de calcul à une notion formelle ‘mécanique’ s’opère par un travail du lecteur sur lui-même qui doit adopter le ‘bon’ point de vue, celui du mécanisme, pour réussir à apprécier la portée du concept présenté. »7

Cela peut ressembler à l’argument du retrait de l’échelle présenté par Wittgenstein à la fin de son Tractatus Logicus-Philosophicus (Turing rencontrera d’ailleurs le philosophe un peu plus tard dans sa vie, à Cambridge). Il n’existe pas de métalangage pour la logique, il faut s’y exercer. Pour comprendre sa machine, il faut donc jouer avec. « En conséquence, l’aspect finitaire de la procédure de calcul est rapporté à un agent mécanique de la pensée et il n’y a pas d’autre moyen de vérification de l’aspect en question que l’effectuation de celle-ci. »8

Des machines particulières aux machines universelles ou de l’infini des calculs à la finitude de la machine

Une fois ses machines définies et présentées via des exemples, Turing peut ainsi poser l’équivalence entre une séquence calculable et la description d’une machine au travers de la description de sa table d’instructions. «En fait toute séquence calculable peut être décrite au moyen d’une table de ce genre.»9.  Cette étape lui permet d’introduire l’idée essentielle de machine universelle.

En effet, jusqu’à présent, pour chaque calcul, il fallait définir une machine particulière avec sa table d’instructions permettant d’effectuer ledit calcul. La machine universelle va permettre de « calculer n’importe quelle séquence calculable. »10.  En fait, cette machine universelle décrit mécaniquement le procédé qui permet au calculateur humain de trouver la bonne machine particulière relativement au calcul particulier à effectuer. Le concept de cette machine universelle permet ainsi à Turing de cerner un peu mieux le champ même du calculable, « dans la mesure où elles [les machines universelles] réduisent tout calcul à la construction de la table d’instruction d’une seule machine. Grâce à l’usage d’une machine universelle, il devient possible de réutiliser l’intégralité des tables d’instructions d’autres machines. »11  Turing va ensuite présenter la table de fonctionnement d’une machine universelle.12

On peut ainsi concevoir que les machines de Turing particulières sont les ancêtres des futurs programmes informatiques, tandis que les machines universelles seraient les précurseurs des futurs ordinateurs capables de faire tourner des programmes.
Et c’est là que l’on observer comment Turing retrouve la démarche gödelienne à travers le fait de coder les machines particulières en leur attribuant un entier naturel, un index en somme, qui permet ainsi de « combiner en une table d’instructions de plus en plus complexe des tables d’instructions effectuant des calculs plus simples en réduisant tout calcul à n’être qu’une partie d’un calcul plus vaste. »13  La machine universelle est alors chargée de retrouver à partir de l’index, la table correspondante contenant les instructions des machines particulières, puis d’exécuter ces dernières. « Ainsi non seulement chaque calcul, de longueur arbitraire, est-il réduit au point de vue du fini mais l’infinité des calculs elle-même est aussi réduite au point de vue du fini […] »14.

Calculabilité et problème de la décision, l’Entscheidungsproblem

Turing parvient ainsi à redéfinir la notion de calculabilité. Ce n’est pas le seul mathématicien qui le fait à cette époque. Comme on l’a vu Gödel, mais aussi Church, auront produit finalement tous les trois une définition de la calculabilité équivalente. Mais l’un des intérêts de la définition de Turing, est, comme le précise Cassou-Noguès, de garder un lien évident avec la notion intuitive de calcul.

Turing l’aura cependant fait d’une manière singulière (et c’est par ailleurs cette manière singulière qui autorisera toute une somme de réflexion sur les rapports entre l’esprit et la machine), en montrant que le travail qu’effectue un calculateur humain est une succession d’étapes, une composition d’éléments qui vont s’articuler pour devenir finalement un algorithme pris en charge par son concept de machine. Comme on l’a dit, Turing ne suit pas les canons d’un article théorique classique. A travers une sorte d’opération cartésienne de division du problème, Turing écrit que « le travail du calculateur est divisé en une suite d’’opérations élémentaires’, tellement simples qu’il serait difficile de les diviser encore. »15  Il a posé désormais les bases de son concept de machine à calculer.

Il décrit en effet à présent le travail qu’effectue un calculateur humain dans les termes même de son concept de machine. « […] c’est l’état mental du calculateur et les symboles qu’il observe qui déterminent l’opération à effectuer, et en particulier le nouvel état mental dans lequel il se retrouve après exécution de ladite opération. »16

Ainsi la description du travail effectué par l’humain devient fidèle à son concept de machine, dont nous avons parlé dans l’épisode 8. La machine est ce dispositif à deux propriétés principales : 1) une machine n’a effectivement qu’un nombre fini d’états qui lui sont propres. 2) ce qu’effectue la machine à l’instant T ne dépend que de l’état de la machine à l’instant T et des données qui lui parviennent via un dispositif quelconque. Le calculateur humain est ainsi devenu une machine universelle au sens de Turing.

Il lui reste à présent à s’atteler à la seconde partie de son article, contenue dans le titre « … l’application au problème de la décision ».
Comme nous l’avons précisé, une fois défini ces a-machines, Turing avait présenté les machines cycliques et les machines acycliques, ce qui lui avait permis de redéfinir la calculabilité en fonction des machines acycliques. Le problème de la décision autrement nommé, problème de l’arrêt, peut ainsi s’énoncer de cette manière : « peut-on savoir à l’avance si tout calcul aura ou non une fin ? »17

Et Turing va y répondre par la négative en démontrant qu’une fois que l’on aurait produit une liste infinie des machines acycliques capables de produire les séquences calculables, c’est-à-dire de calculer la partie (infinie) décimale des nombres réels, il faudrait supposer l’existence d’une autre machine capable cette fois de « décider » elle-même si elle doit s’arrêter ou non, ce qui apparaît impossible. Turing le démontre à l’aide du formalisme de sa machine qu’il vient d’inventer.

Vous pouvez trouver ici un cours très intéressant sur la calculabilité et la complexité qui présente le modèle de la démonstration de ce problème de l’arrêt dans l’informatique :

Quelques rudiments de calculabilité et de complexité, par Paul Gastin

Cette vidéo présente ainsi ce problème d’indécidabilité au travers des limites intrinsèques de la puissance de calcul des machines informatiques.
Turing va user de la méthode diagonale que Cantor avait utilisée dans un article datant de 1891 pour démontrer que l’ensemble des nombres réels était non dénombrable.18

Turing utilise le même procédé pour s’interroger cette fois sur le caractère dénombrable des nombres calculables qu’il a cette fois lui-même redéfinis à l’aide de son concept de machine.
« On peut définir sommairement les nombres ‘calculables’ comme étant les réels dont l’expression décimale est calculable avec des moyens finis. […] Selon ma définition, un nombre est calculable si sa représentation décimale peut être décrite par une machine. »19

Reprenant l’argument de Cantor, combiné avec son concept de machine, Turing montrait qu’il pouvait ainsi exister des nombres définis, mais non calculables. Une machine universelle est en effet censée tester chaque index correspondant à une machine particulière calculant une séquence calculable, ce qui revenait à mécaniser le procédé de Cantor. Mais Turing montrait finalement qu’il était impossible de déterminer mécaniquement si une table d’instructions particulière, une machine selon son concept, allait produire une suite infinie ou non, c’est-à-dire si telle machine particulière allait boucler ou non ; autrement dit par Turing, « […] ce problème d’énumération des séquences calculables est équivalent à celui qui consiste à déterminer si un nombre donné est le ND [le Nombre Descriptif, c’est-à-dire l’entier qui désigne une machine particulière via la méthode de Gödel] d’une machine acyclique, et il n’existe pas de procédure générale pour faire cela en un nombre fini d’étapes ».20

En somme, le procédé de Cantor, la méthode de la diagonale, ne peut être mécanisé.
Comme l’écrit Guillaume Watier : « Remarquons que le théorème de l’arrêt est à l’algorithmique ce que le théorème de Gödel est à la démonstration mathématique de théorème. »21
Après les résultats de Gödel, c’est donc un nouveau coup à l’optimisme d’Hilbert, Turing montrant d’une part qu’il ne peut exister de méthode pour décider si telle ou telle assertion de l’axiomatique peut être considérée comme vraie ou fausse, et d’autre part qu’il existe des problèmes insolubles. Gödel dira que les travaux de Turing donnait ainsi une véritable définition de ce qu’était finalement un système formel « dont la propriété est qu’en son sein, et en principe, le raisonnement peut être entièrement remplacé par des règles mécaniques. »22

Comme nous l’avons dit Turing redéfinit ainsi la notion de calculabilité, comme Church et Gödel. Mais l’un des intérêts de la définition de Turing, est, comme le précise Cassou-Noguès, de « garder un lien évident avec la notion intuitive. »  Sa définition de la calculabilité en passe en effet dans cet article par une sorte de « psychologie du calcul » lors de la comparaison calculateur mécanique et calculateur humain.

Enfin, Turing vient avec son article de distinguer deux choses : la démonstration et la vérité, car il montre combien « démontrer revenait à calculer et non pas à établir la vérité d’un théorème puisque démontrabilité et vérité se trouvaient au contraire dissociés. »

Le style, c’est l’homme…

Répétons-le, même si le déploiement futur des calculateurs numériques s’origine dans les trouvailles de Turing, le problème auquel il s’est attaqué ici était un problème de mathématique pure. Et pourtant, le style de cet article théorique qui complète les travaux de Gödel reste tout à fait surprenant. On a vu combien son biographe Hodges avait noté que Turing présentait depuis son enfance différents traits d’originalité dans ses conduites, notamment sociales. Cette fois, on peut dire que l’originalité de Turing se manifeste dans le contenu dans son article : il produit un concept novateur.

Mais l’originalité se manifeste également dans la forme, c’est-à-dire sa façon de conceptualiser et de résoudre ce problème mathématique, ce que Cassou-Noguès nomme « la psychologie du calcul » de Turing. En effet, ce dernier se met à analyser le travail d’un sujet humain qui calcule, ce qu’il nomme le « computer » dans le texte original que vous pouvez trouver ici :

ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM By A. M. TURING

On peut y remarquer qu »il y a en effet deux occurrences dans le texte original où Turing compare « l’homme-qui-calcule » à « la-machine-qui-calcule » : dans sa présentation de la machine à calculer23  et dans sa discussion sur la pertinence de la notion de calculabilité24.

C’est dans la seconde que Turing va d’ailleurs définir sa notion d’ « état mental ». Il la redéfinit cependant encore une fois à l’aide d’une analogie. « Notre calculateur peut toujours interrompre sa tâche, quitter son lieu de travail et oublier tout ce qui s’y rapporte, pour revenir plus tard et reprendre son calcul là où il l’avait laissé. Pour ce faire, il doit conserver une notice où se trouvent consignées (sous une forme canonique quelconque) un certain nombre d’instructions indiquant comment  reprendre son calcul. C’est cette notice qui remplace l’état mental dont nous parlions en (I). […] »25

Conséquences …

Avec cet article, nous avons certes comme le souligne Dupuy, « les prolégomènes d’une nouvelle science de l’esprit »26, même si Turing n’en avait pas conscience bien entendu. Mais il faut se rappeler un point important par rapport aux autres directions qui seront prises dans cette nouvelle science de l’esprit et qui favoriseront la naturalisation complète du concept d’esprit, ce qui n’est pas du tout le cas de Turing.

Comme le remarque la psychanalyste Christiane Alberti, Turing « prend donc appui sur la représentation que l’on peut se donner d’un être humain en train de calculer […] »27.

Tout comme Cassou-Noguès, Alberti souligne ainsi que Turing fonde ses résultats dans l’imaginaire, et que son assertion « Un homme en train de calculer la valeur d’un nombre réel peut être comparé à une machine susceptible de se trouver dans un nombre fini d’états q1, q2, …, qR, que nous appellerons ses m-configurations » fonctionne effectivement, non pas grâce à un réductionnisme (qui associerait un état mental à un état physique) dont Turing serait le thuriféraire, mais finalement grâce à la nature de l’acte de calculer lui-même situé sur un plan logique. Turing s’intéressera quelques années plus tard à la façon de rendre concrète sa machine, avec par exemple son projet de « construire un cerveau » à la fin de la seconde guerre mondiale. Mais comme l’écrit Hodges « Pour notre mathématicien, quoi que fasse un cerveau, il le faisait en vertu de sa structuration logique et non parce qu’il se trouvait à l’intérieur d’un crâne humain ou parce qu’il était constitué de manière spongieuse composée d’une espèce particulière de formation cellulaire biologique. Sa structure logique devait parfaitement être réplicable dans un autre milieu, matérialisée par une autre espèce de mécanisme physique. C’était une conception matérialiste, qui avait le mérite de ne pas confondre les systèmes logiques et les relations avec les substances physiques et les choses elles-mêmes, selon une erreur trop souvent commise. […] Lorsqu’il parlait de ‘construire un cerveau’, il ne pensait pas que les éléments de sa machine devaient ressembler à ceux du cerveau, ni que leurs connexions devaient en imiter les différentes régions.»28

Turing nous montre ainsi simplement en quoi une partie de notre activité mentale peut être mécanisable, car l’acte de calculer opéré par un être humain peut effectivement être externalisé dans une machine. La question de savoir si toute l’activité mentale d’un être humain est calcul est une toute autre question, et semble beaucoup plus compliquée à démontrer….

Au sujet de l’autonomie de la machine, Jean Lassègue est très clair. « Croire en l’autonomie de la machine et en conséquence, à sa supériorité , conduit à une anthropomorphisation regrettable du concept de machine. »29Selon lui, même si Turing réussit cette « mise en rapport du concept de machine universelle de Turing avec la notion d’esprit humain », la machine ne peut en aucun cas produire une décision, c’est à dire être « indépendante de la pensée humaine qui l’a produite. »30

Cassou-Noguès rappelle une boutade de Lacan qui résumerait selon lui la différence entre la machine et l’homme31 dans le sens où avec Turing (et ce que l’on vient de voir au sujet de la méthode de la diagonale et du problème de l’arrêt) on pourrait dire qu’une machine de Turing ne peut établir la liste de toutes les machines de Turing.
Lacan lors de son séminaire sur les quatre concepts fondamentaux de la psychanalyse, est en train d’introduire son concept d’inconscient via les apports de Levi-Strauss. Il parle de l’enfant qui compte le nombre de ses frères et qui s’y compte, avant de s’y reconnaître dans le comptage.

 » Je prends d’abord le concept de ‘l’inconscient’. […] pour l’illustrer par quelque chose qui est matérialisé assu¬rément sur un plan scientifique, je l’illustrerai par exemple par ce champ […] qu’explore, structure, élabore et qui se montre déjà infiniment riche, ce champ que Claude Lévi-Strauss avait épinglé du titre de Pensée sauvage. Avant toute expérience, toute déduction individuelle, avant même que s’y inscrivent les expériences collectives qui ne sont rapportables qu’aux besoins sociaux, quelque chose organise ce champ, en inscrit les lignes de force initiales, qui est cette fonction que Claude Lévi-Strauss, dans sa critique du totémisme, nous montre être sa vérité, et vérité qui en réduit l’apparence, de cette fonction du totémisme, à savoir une fonction classificatoire primaire : ce quelque chose qui fait [que], avant que les relations s’organisent, qui soient des relations proprement humaines, déjà s’est organisé ce rapport d’un monde, à un autre monde de certains rapports humains qui sont déterminés par une organisation, aux termes de cette organisation qui sont pris dans tout ce que la nature peut offrir comme support, qui s’or¬ganisent dans des thèmes d’opposition. La nature, pour dire le mot, fournit des signifiants, et ces signifiants organisent de façon inaugurale les rapports humains, en donnent les structures et les modèlent.

L’important est ceci, c’est que nous voyons là le niveau où, avant toute formation du sujet (d’un sujet qui pense, qui s’y situe), ça compte, c’est compté, et dans ce compté, le compte, déjà, y est! Il a ensuite à s’y recon¬naître, et à s’y reconnaître comme comptant. Disons que l’achoppement naïf où le mesureur de niveau mental s’esbaudit de saisir le petit homme, quand il lui propose l’interrogation : «J’ai trois frères, Paul, Ernest et moi, qu’est-ce que tu penses de ça ? » — Le petit n’en pense rien pour la bonne raison, c’est que c’est tout naturel! D’abord sont comptés les trois frères Paul, Ernest et moi, et tel je suis moi, au niveau de ce qu’on avance que j’ai à réfléchir : ce moi… c’est moi! et que c’est moi qui compte.

C’est cette structure, affirmée comme initiale de l’inconscient, aux temps historiques où nous sommes de formation d’une science, d’une science qu’on peut qualifier d’humaine, mais qu’il faut bien distinguer de toute psychosociologie. D’une science dont le modèle est le jeu combi¬natoire que la linguistique nous permet de saisir dans un certain champ, opérant dans sa spontanéité et tout seul, d’une façon présubjective, c’est ce champ-là qui donne, de nos jours, son statut à l’inconscient. C’est celui-là, en tout cas, qui nous assure qu’il y a quelque chose de quali¬fiable sous ce terme qui est assurément accessible d’une façon tout à fait objectivable. »

Le débat sur l’infériorité ou la supériorité de la machine est pour Lassègue une question qui n’a que peu d’importance. Mais par contre, il estime que le résultat de Turing, mais aussi celui de Gödel, en pointant les limitations internes de l’axiomatique formelle telle que la souhaitait Hilbert, engagerait un questionnement sur les rapports entre le conscient et l’inconscient (Il pense à une sorte d’inconscient mécanique en deça de l’intuition) dans la pensée humaine, du fait de leur mise en valeur de l’impossible recouvrement total du domaine de la pensée humain par la pensée algorithmique. « Chaque processus mental mis sous forme algorithmique manifeste la présence d’une générativité algorithmique de la pensée qui suit la générativité de l’intuition comme son ombre. »32

Cela rejoint il me semble l’objet du livre de Michel Bourdeau, Pensée symbolique et intuition33 qui cherche à élaborer une théorie de l’intuition, à partir d’un cheminement philosophique sur ce qu’est d’abord la pensée symbolique et ses succès (dont le programme de Hilbert est une sorte d’exacerbation ou de tentative de la rendre hégémonique), ceci afin de mieux en cerner les limites.

Dans une intervention au colloque « Le réel en mathématiques – Psychanalyse et mathématiques », la mathématicienne, Marie-Françoise Roy, spécialiste des algorithmes de la géométrie algébrique réelle, rappelle ce que nous avons dit lors de l’épisode précédent, à savoir qu’avec l’informatique, « l’histoire du calcul entre dans une phase radicalement nouvelle. »

Elle cite également Lacan, dans son séminaire sur le moi dans la théorie de Freud et dans la technique de la psychanalyse qui a beaucoup travaillé sur la cybernétique cette année-là, parlant souvent de la différence entre l’homme et la machine, tentant d’ouvrir des pistes, mais sans jamais fermer le débat. Lacan tente d’expliquer quelque chose au sujet de la répétition, concept par lequel il introduira à celui d’inconscient dans le séminaire que nous avons déjà cité, à savoir les quatre concepts fondamentaux de la psychanalyse. Il parle de Kierkegaard et de son écrit La répétition, puis il en vient à la machine à calculer.

« Mais à la suite de ça, il nous mène sur le chemin de notre problème, à savoir, comment et pourquoi tout ce qui est d’un progrès essentiel pour l’être humain doit passer par la voie d’une répétition obstinée.
J’en viens au modèle sur lequel je veux vous laisser aujourd’hui pour vous permettre d’entrevoir ce que veut dire chez l’homme le besoin de répétition. Tout est dans l’intrusion du registre symbolique. Seulement, je vais vous l’illustrer.
C’est très important, les modèles. Non pas que ça veuille dire quelque chose-ça ne veut rien dire. Mais nous sommes comme ça – c’est notre faiblesse animale -, nous avons besoin d’images. Et, faute d’images, il arrive que des symboles ne viennent pas au jour. En général, c’est plutôt la déficience symbolique qui est grave. L’image nous vient d’une créa¬tion essentiellement symbolique, c’est-à-dire d’une machine, la plus moderne des machines, beaucoup plus dangereuse pour l’homme que la bombe atomique, la machine à calculer. »

Marie-Françoise Roy se demande ainsi quel est la nature de ce danger ? Peut-être est-ce la croyance que tout le registre qualitatif pourrait être « transféré » dans le registre du quantitatif, ce qui est une des craintes actuelles ?

Son intervention est intéressante en ce qu’elle montre le mathématicien aux prises avec cet objet qu’est l’ordinateur, dans une relation étrange, où l’homme peut produire un algorithme, le maîtriser le visualiser de l’intérieur, et rester pourtant totalement surpris, agréablement ou désagréablement d’ailleurs, des résultats que cet algorithme peut produire. « Les mathématiques accèdent alors à un véritable statut de sciences expérimentale, l’ordinateur jouant le rôle de l’appareil expérimental en physique. »34 Mais elle cite également le mathématicien et informaticien Doron Zeilberger qui prévoit que l’informatique et les ordinateurs tiendront un rôle de plus en plus important dans la création et la recherche en mathématiques, jusqu’à supplanter complètement les sujets humains.

Comme le disait Lacan, idée que reprend M-F Roy, « Dans une machine, le symbolique fonctionne tout seul. » Avec cet article, Turing s’est installé au cœur de ce symbolique mécanique pour en montrer certains rouages, mais aussi, certains de ses aspects que l’on nomme indécidables. Cette révolution n’a pas fini de produire ses effets sur nous…

1. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 52
2. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 53
3. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 54
4. Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 94
5. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 73
6. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 75 et 76
7. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 75
8. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 75
9. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 63
10. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 66
11. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 81
12. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 68
13. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 81
14. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 81 et 82
15. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 78 et 79
16. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 80
17. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 82
18. Lire à ce sujet : Argument_de_la_diagonale_de_Cantor
19. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 49
20. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 73
21. Guillaume Watier, Le calcul confié aux machines, Ellipses, 2001, p.57
22. Gödel cité par Lassègue, Turing, Les Belles Lettres, 1998, p. 85
23. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 51
24. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p. 78 à 84
25. Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995, p.84
26. Jean-Pierre Dupuy, Aux origines des sciences cognitives, La découverte, 1999, p.22
27. Christiane Alberti, « Alan Turing et sa A-machine : le moment de la logique », in Le traumatisme de la langue – études cliniques, Association Himeros, 2007, p. 74
28. Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 248
29. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 88
30. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 88 et 89
31. Pierre Cassou-Noguès, Gödel, Les Belles Lettres, 1998, p. 90
32. Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 90
33. Michel Bourdeau, Pensée symbolique et intuition, PUF, 1999
34. Marie-Françoise Roy, « Le réel du calcul » in Le réel en mathématiques – Psychanalyse et mathématiques, Agalma, 2004, p. 200

Paris, le 9 avril 2011.

Aspects biographiques

Voici donc cette fois une sorte de résumé des premiers chapitres du livre d’ Hodges, qui relatent les premières années de la vie d’Alan Turing, jusqu’à ses premiers travaux importants en mathématiques.

Le père d’Alan Turing, Julius Mathison Turing, naquit le 9 novembre 1873. Son propre père, John Robert Turing, meurt lorsque ce dernier a dix ans, en 1883. Ce dernier, le grand-père paternel d’Alan Turing, semble avoir eu quelque potentiel dans le domaine des mathématiques. Il « fit des études de mathématiques au Trinity College de Cambridge, et fut classé onzième de la promotion de 1848 avant de renoncer aux mathématiques pour recevoir l’ordination et devenir pasteur à Cambridge. »[1]

Le père d’Alan vécut son enfance dans un contexte social plutôt modeste et « sa vie de jeune homme fut longtemps un modèle de réussite. »[2] Il entre rapidement sur concours à l’Indian Civil Service, qui est à l’époque des colonies de l’empire britannique, « le service d’administration des Indes britanniques », et progresse rapidement dans la hiérarchie. En 1907, après dix ans passés en Inde, il revient en Angleterre. Sur le chemin du retour, il va rencontrer sa future épouse, et future mère d’Alan, Ethel Sara Stoney, qui était d’ailleurs née à Madras le 18 novembre 1881. La famille Stoney jouissait quant à elle d’une certaine fortune, mais « les quatre enfants Stoney furent […] renvoyés en Irlande pour y faire leur études, payant ainsi, comme beaucoup d’autres en Inde britannique, le prix de l’Empire en années sans amour ».

Ceci explique peut-être en partie que les parents d’Alan reproduiront finalement une partie de leur propre enfance avec leurs deux fils, John et Alan, en les envoyant en pension, tout en ne pouvant les voir qu’épisodiquement. En effet, tandis que Julius Turing vivait avec sa femme et travaillait en Inde, leur deux fils vécurent finalement une grande partie de leur enfance sans leurs parents, dans des familles d’accueil, puis dans des internats.

Ethel Stoney fut dans sa jeunesse très attirée par les arts, et notamment la musique, qu’elle tenta même d’étudier à Paris, à la Sorbonne. Leur couple appartenait finalement à « cette petite bourgeoisie britannique qui cherchait à tout prix, et quels que fussent ses moyens, à se hisser au rang de l’aristocratie. »[3] Et l’Inde ne devait pas, à leurs yeux, permettre à leurs fils d’acquérir la formation attendue d’un gentleman de la high society, le but ultime étant que leurs enfants intègrent sur concours les fameux collèges privés britanniques, les public school.

Ainsi le frère d’Alan, prénommé John, naquit en Inde, en septembre 1908, dans la demeure des Stoney, à Coonoor (une ville située dans le sud de l’Inde). Tandis qu’Alan, lui, vit le jour le 23 juin 1912, à Paddington en Angleterre, lors d’un congé de son père qui permit à la famille Turing de rester en Angleterre, jusqu’en mars 1913. Puis Julius Turing repartit dans un premier temps seul pour l’Inde, et laissa sa femme en Angleterre avec ses deux enfants. Celle-ci le rejoignit en septembre 1913, et laissa alors les deux enfants en Angleterre. Julius Turing pensait que ses deux fils souffriraient trop de la chaleur de Madras. L’enfance en famille d’accueil de ces deux garçons va donc être ponctuée par les allers retours de leur père et de leur mère entre l’Angleterre et l’Inde.

Alan a donc finalement trois mois lorsque sa mère le laisse, avec son frère, qui lui a quatre ans, « en pension chez un couple de militaires à la retraite, le colonel Ward et sa femme. »[4]

C’est dans ce premier lieu de vie qu’Alan commença à montrer sa singularité, attirant par exemple l’attention par certains commentaires, mais d’un point de vue général, plutôt « réfractaire aux obligations de l’enfance ». Ce trait semble se retrouver régulièrement dans le reste de la vie d’Alan, tel qu’Hodges la dépeint, c’est-à-dire à chaque fois qu’il doit se soumettre aux règles d’un milieu. Cependant « les deux garçons Turing ne tardèrent pas à décevoir Mrs Ward : ils n’avaient ni l’un ni l’autre de goût pour la bagarre, les jouets guerriers ou les modèles réduits de cuirassés. Mrs. Ward finit même par écrire à Mrs. Turing pour se plaindre de ce que John ne levait pas le nez de ses livres […] »[5]

Le couple Turing revient régulièrement en Angleterre pour retrouver leurs fils. En 1916, Alan a alors quatre ans, et son père part pour trois ans (il ne reviendra qu’en 1919), tandis que sa femme reste en Angleterre pendant un temps. En 1917, son frère, John qui a maintenant 10 ans, fut envoyé dans une école préparatoire du Kent, et Alan, lui, fut envoyé, un peu plus tard, en 1918, dans une école privée, pour apprendre le latin, matière indispensable pour l’entrée dans une des public school. Sa mère resta donc seule avec Alan jusqu’en 1919, mais elle repartit avec son mari en décembre.

Alan apprit cependant tout seul à lire, « grâce à un manuel intitulé ‘La lecture sans larmes’. Les chiffres lui posèrent encore moins de problèmes […] »[6]. Il disait vouloir devenir médecin. Une de ses grandes passions était les cartes géographiques, qu’il s’amusera à établir lui-même quelques années plus tard. Mais seul, dans cette pension, son instruction prenait tout de même du retard, et autour de ces dix ans, il semble que son état, renfermé et un peu mélancolique, commença à inquiéter sa mère, lorsqu’elle revint en 1921. Elle s’occupa alors de son éducation elle-même pendant un moment, avant de finalement l’envoyer dans la même école que son frère John.

Cette étape dans l’instruction d’Alan fut un peu chaotique, « Alan ne tarda pas à considérer le programme de l’école comme une simple distraction »[7] mais également à le remettre en cause. Il découvrit la Science en 1922 à l’aide d’un livre qui le marqua, Les merveilles de la Nature que tout enfant devrait connaître, où l’auteur, Brewster, traite des liens entre sciences naturelles et sexualité, évacuant ainsi les notions d’âme et toute intervention divine, et comparant le corps humain à une machine. Ce livre fournira à Alan matière à pensées…

Lorsque le père d’Alan et de John démissionna de l’Indian Civil Service, il choisit de ne pas rentrer tout de suite en Angleterre afin de pouvoir continuer à profiter du privilège de ne pas payer d’impôts. Les Turing s’installèrent alors en France, à Dinard, ce qui permit à Alan d’apprendre le français. Le train de vie de la famille se réduisit alors considérablement. L’inactivité de Julius finit cependant par attaquer la vie de couple des Turing qui devint peu à peu particulièrement ennuyeuse. Tandis que Julius tentait de combler ses journées par la pêche et des parties de bridge, tout en méprisant les embryons d’aspiration à la science d’Alan, Ethel gardait certaines ambitions intellectuelles et artistiques qu’elle avait à cœur d’essayer de transmettre à Alan.

Alan se découvrit alors une véritable passion pour la chimie, qui se poursuivra longtemps dans sa vie d’étudiant par ailleurs. Il se montra alors particulièrement curieux et inventif lors d’expériences qu’il menait seul. Il écrivit un jour à ses parents : « […] Je suis en train de faire une série d’expériences dans l’ordre que je me suis fixé. J’ai l’impression de toujours vouloir faire des choses à partir de ce qu’il y a de plus commun dans la nature et avec la moindre perte d’énergie possible. »[8]

Mais une certaine inquiétude chez ses parents pesait fortement sur l’avenir de cet enfant peu sociable, et à l’allure atypique. Pourrait-il finalement entrer dans une de ces écoles privées ? Tandis que son père semblait être fixé sur cette étape qui lui apparaissait constituer la seule possible pour l’avenir de son fils, son frère et sa mère s’inquiétaient plutôt pour Alan lui-même quant à la manière dont il pourrait vivre cette étape. Après un concours d’entrée, Alan entra finalement dans le collège privé de Sherborne dans le Dorset (une des plus anciennes public schools d’Angleterre), en 1926, à quatorze ans, et il fut affecté à l’internat Wescott.

Une anecdote est racontée souvent pour montrer les capacités de cet enfant, tout en soulignant sa singularité. Alan profita d’une paralysie des transports due à une grève générale dans le pays, pour s’offrir une dernière parenthèse de liberté sur le chemin de cette école, en faisant le trajet jusqu’à l’école à vélo. Et comme il était allergique, il portait un masque à gaz pour se protéger. Une belle promenade en solitaire de deux jours, avec nuit dans un grand hôtel qu’il réussit à obtenir gratuitement en attendrissant ses hôtes, avant une descente aux enfers…

Car l’univers de Sherbrone, véritable « Grande-Bretagne en miniature et fossilisée, où maîtres et serviteurs connaissaient leur place respective »[9] Une tradition continuait par exemple d’être pratiquée, celle des prefets et des fags[10]. Les préfets sont des garçons plus âgés désignés pour faire régner la discipline sur les plus jeunes. Cet univers s’opposait donc de manière radicale aux habitudes du jeune Turing, et pire encore, excluait en pratique ses aspirations. Les objectifs de l’école étaient, selon le directeur, de « se familiariser avec les notions d’autorité, d’obéissance et de coopération, de loyauté et de s’habituer à placer son internat et son collège au-dessus de ses désirs personnels… »[11] Autant de règles qui paraîtront aussi stupides que des plus compliquées à intérioriser pour le jeune Turing, qui peu à peu se renfermera jusqu’à vivre de manière très solitaire.

Rapidement, « la pire crainte de Mrs. Turing se réalisait : Alan ne s’adaptait pas à la vie des public schools. […] Aucun des dix-sept enseignants qui se succédèrent au cours de cette première année à Sherbrone n’aima ni ne comprit ce garçon rêveur.»[12] Aussi, tandis que son frère embrassait une carrière de notaire, Alan ne comprenait pas trop pourquoi on l’obligeait à suivre cette formation qui lui paraissait bien trop coûteuse pour ce qu’il en retirait personnellement. Cependant, en 1927, Alan commença à montrer certaines aptitudes en mathématiques. Il réussit en effet à trouver seul et sans aucun manuel « la suite infinie de la fonction tangentielle inverse en partant de la formule trigonométrique de tg. 1/2x. »[13] Il me semble que c’est un résultat qu’avait démontré Leibniz, et que le jeune Turing avait réussi à retrouver tout seul.

C’est également au cours de cette année 1927, où Alan atteint l’âge de quinze ans, que les métamorphoses de la puberté commencèrent à devenir pour lui sources de questionnement plus impérieux sur son désir. Alan prit alors conscience, dans cet univers masculin des collèges privés, qu’il ne se sentait « attiré et séduit que par ceux de son propre sexe. »[14]

La scolarité d’Alan à Sherbrone ne sera donc qu’une lutte permanente contre ce qu’on tenta de lui inculquer. Et il passa de classe en classe, toujours sur un fil, en étant toujours classé parmi les derniers. Cependant, son goût pour les sciences physiques et les mathématiques ne cessèrent de s’affirmer. Il découvrit Einstein et la théorie de la relativité, qu’il étudia directement d’après les comptes rendus du physicien, et y apprécia un élément important que l’on retrouvera dans ses travaux ultérieurs : la possibilité de remettre les axiomes en question. Il écrivit même un petit carnet sur les articles d’Einstein qu’il remit à sa mère.

Je m’arrête là pour ce premier épisode, et nous retrouverons plus tard les aventures du jeune Turing et surtout de ses travaux en mathématiques, au regard des questions et des problèmes qui étaient sur le devant de la scène mathématique de son temps.

[1] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 15.

[2] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 15.

[3] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 19.

[4] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 18.

[5] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 18.

[6] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 19.

[7] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 21.

[8] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 28.

[9] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 31.

[10] « […] La tradition des préfets et des fags et celle des corrections infligés dans la salle de bain y régnaient déjà comme si elles étaient des lois de la nature. », p.31

[11] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 30.

[12] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 32.

[13] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 33.

[14] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 36.

Introduction

« Pourquoi Alan Turing n’est-il pas plus connu du grand public ? »[1], telle est la première question que pose Hervé Le Guyader dans sa préface au livre de Hodges, sur lequel par ailleurs je me baserai pour parler de la vie et de l’œuvre de ce personnage énigmatique et fascinant, dans cette série d’articles que je vais essayer d’écrire à partir de Turing, et que je voudrais voir dériver vers l’étude de  l’intelligence artificielle, y compris dans ses applications dans les jeux vidéo.

Cette question, « Pourquoi Alan Turing n’est-il pas plus connu du grand public ? », me poursuit également depuis une intervention que j’avais faite à dans le cadre du Réseau Adolescents du 93 en mars 2010, dont le thème était « Virtualités adolescentes ». J’avais évoqué Alan Turing, comme le père de l’informatique, et je me suis aperçu à la réaction de l’assistance qu’en fait, il semblait que peu de monde connaissait son existence. Aussi, j’ai donc décidé d’écrire sur ce destin de cet homme dont les travaux ont contribué à bouleverser l’univers scientifique et technique du vingtième siècle.

2012 sera également l’année du centenaire de sa naissance, ce qui apportera de nombreuses occasions pour parler de lui. Raison de plus pour commencer un peu en avance ! Mais je crois également que le discours empruntant des métaphores à l’informatique s’est imposé, évidemment dans les sciences cognitives (ce que je voudrais essayer d’explorer également), mais également dans notre langage courant. Les partis politiques doivent aujourd’hui « changer de logiciel » ! Expression, à mon sens, bien significative de nos représentations. Je pense que ce serait peut-être plutôt le hardware qui devrait être changé… Cette distinction entre hardware (le matériel informatique lui-même, l’ordinateur au sens physique) et sofware (le logiciel, les programmes qui vont tourner sur le matériel) n’est pas issu directement des travaux de Turing, mais de ceux d’un très grand mathématicien contemporain de Turing, à savoir Von Neumann. Nous y reviendrons plus tard.

Fils d’un fonctionnaire colonial britannique en poste en Inde, né en Angleterre en 1912, Alan Turing ne vécut jamais en Inde, mais resta en Angleterre dans des familles d’accueil puis dans des internats scolaires. Il fut toujours rebelle et atypique au regard des conventions sociales qui régnaient dans ces public school, ces établissements privés censées former la future élite britannique. Son homosexualité le conduisit à tomber sous le coup de la même loi qui avait fait condamner Oscar Wilde à deux ans de prison. Et face au « choix » qu’on lui laissa, l’emprisonnement ou la castration chimique, Turing choisit la seconde option, ce qui lui coûta a priori la vie (on suppose que son « traitement médicamenteux » entre en grande partie dans les raisons de son suicide). Terrible perte pour l’humanité. Il se suicida le 7 juin 1954, il avait seulement quarante et un ans. Son corps fut incinéré le 12 juin 1954 au crématorium de Woking.

Récemment, Gordon Brown, a publié en 2009 sur son site des excuses officielles pour la manière épouvantable » et « inhumaine » avec laquelle fut traité Alan Turing, en raison de son homosexualité. [2]

Dans le futur premier « épisode », (Je reprends ici, en forme de clin d’oeil, la méthode de narration de mon ami JC Dardart. S’il me lit, je le remercie pour cette idée !), je poursuivrai plus en détails ces aspects biographiques.

Tout d’abord pourquoi a-t-il bouleversé l’univers scientifique et technique du vingtième siècle ? Outre le fait qu’il fut un héros de la guerre pour ses travaux en cryptographie, et un grand mathématicien et logicien, les questions qu’il s’est posées au sujet de l’informatique, notamment dans le second article que l’on retient généralement de lui, écrit en 1950, « Les ordinateurs et l’intelligence »[3], sont, il me semble, encore d’actualité, et méritent d’être mieux connues. Le premier article étant « Théorie des nombres calculables, suivie d’une application au problème de la décision »[4], écrit cette fois en 1936.

Turing a été poursuivi sa vie durant par des questions autour des relations « corps-esprit ». Et j’aimerais également réussir, plus tard, à examiner comment ses recherches en logique mathématique visaient à essayer d’apporter des réponses à ses questions.

Aussi, dans un premier temps, nous allons nous attacher à retracer quelques éléments de la vie de Turing, tout au moins jusqu’à ses premiers travaux qui l’ont fait véritablement connaître, à savoir sa solution au problème de la calculabilité, en 1936.

Puis j’essaierai, dans les limites de mes compétences en mathématiques, de déplier quelques enjeux du contexte et des problèmes dans lequel il évoluait et qui l’ont mené à proposer sa solution en termes de machine logique. Il me faudra alors me pencher sur Hilbert, autre grand géant de l’histoire des mathématiques, afin d’essayer d’exposer ce que l’on a appelé « le programme formaliste », qui a abouti donc aux théorèmes d’incomplétude de Gödel, et aux « machines de Turing » sur lesquelles je reviendrai plus tard.

Alan Turing, sur les traces de l’IA : Episode 1

Alan Turing, sur les traces de l’IA : Episode 2

Alan Turing, sur les traces de l’IA : Episode 3

Alan Turing, sur les traces de l’IA : Episode 4

Alan Turing, sur les traces de l’IA : Episode 5

Alan Turing, sur les traces de l’IA : Episode 6

Alan Turing, sur les traces de l’IA : Episode 7

Alan Turing, sur les traces de l’IA : Episode 8 – la machine de Turing, première partie

Alan Turing, sur les traces de l’IA : Episode 9 : La révolution des mathématiques, Turing et la matière numérique

Alan Turing, sur les traces de l’IA : Episode 10 : la machine de Turing – seconde partie

Alan Turing, sur les traces de l’IA : Episode 11 : Turing en héros de la seconde guerre mondiale

Alan Turing, sur les traces de l’IA : Episode 12 – Turing et la course aux premiers ordinateurs

[1] Andrew Hodges, « Alan Turing ou l’énigme de l’intelligence », Payot, 1983, 1988, pour la traduction française.

[2] Lire : http://webarchive.nationalarchives.gov.uk/+/number10.gov.uk/news/latest-news/2009/09/treatment-of-alan-turing-was-appalling-pm-20571 ou l’article de Jérôme Fenoglio du monde paru le 15 septembre 2009 : sorryAlan.pdf

[3] Alan Turing, « Les ordinateurs et l’intelligence », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995.

[4] Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995.