The Turing machine (computability)

Par Nadia El-Masri

En 1936, un mathématicien de Cambridge de vingt-quatre ans demanda ce que signifiait pour quelque chose d'être calculable, et répondit par une machine imaginaire. L'article d'Alan Turing, « On Computable Numbers », décrivait un dispositif à ruban infini, tête de lecture-écriture et table de règles, et prouvait que ce modeste engin pouvait simuler tout processus de calcul concevable. La machine de Turing ne fut pas construite ; elle n'avait pas besoin de l'être. Elle définit les limites du calcul lui-même, prouvant que certains problèmes ne pourraient jamais être résolus par aucune machine, et elle donna à l'ère numérique son théorème fondateur : une seule machine universelle peut accomplir tout calcul qu'une autre machine peut accomplir. Né à Londres en 1912, Turing était un garçon maladroit et brillant qui apprit seul la relativité et courait de longues distances pour réfléchir. Quand vint la guerre, il rejoignit Bletchley Park, où les messages allemands chiffrés par Enigma étranglaient l'effort de guerre britannique. Turing conçut la Bombe, machine électromécanique qui testait les réglages des rotors d'Enigma à une vitesse inhumaine, transformant la cryptanalyse d'un artisanat conjectural en processus industriel ; les historiens estiment que les travaux de Bletchley, auxquels ses conceptions furent centrales, raccourcirent la guerre en Europe de près de deux ans. Après la guerre, il dessina les premiers ordinateurs, écrivit le premier programme d'échecs et publia en 1950 « Computing Machinery and Intelligence », qui proposa le célèbre test : si une machine converse de sorte qu'on ne puisse la distinguer d'un humain, on peut dire qu'elle pense. En 1952, il fut poursuivi pour homosexualité, alors un crime en Grande-Bretagne, soumis à la castration chimique et déchu de son habilitation. Il mourut en 1954, à quarante et un ans, d'un empoisonnement au cyanure, une pomme près de son lit. Le verdict officiel fut le suicide. La Grande-Bretagne présenta des excuses en 2009 ; la Reine accorda une grâce royale en 2013. Son visage figure aujourd'hui sur le billet de cinquante livres. La Bombe ne fut que la plus célèbre des machines de guerre de Turing. Au Hut 8 de Bletchley Park, qu'il dirigeait, il cassa aussi l'Enigma navale allemande, la variante la plus complexe, un travail qui protégea directement les convois de l'Atlantique nourrissant la Grande-Bretagne. Sa méthode statistique, qu'il nomma Banburismus, transforma le décryptage d'une intuition en mathématiques, et son collègue Gordon Welchman améliora la Bombe avec le tableau diagonal qui la rendit spectaculairement plus rapide. Après la guerre, Turing conçut l'ACE, l'Automatic Computing Engine, au National Physical Laboratory, l'un des premiers projets détaillés d'ordinateur à programme enregistré, même si les lenteurs bureaucratiques permirent à d'autres de construire le leur avant. À Manchester, il travailla sur le Mark 1, écrivit le premier vrai programme d'échecs, puis stupéfia la biologie avec son article de 1952 sur la morphogenèse, montrant comment de simples réactions chimiques pouvaient engendrer les motifs des taches du léopard et la disposition des feuilles, l'article fondateur de la biologie mathématique. Les poursuites de 1952, pour « outrage public à la pudeur » avec un autre homme, lui valurent un an d'injections d'œstrogènes, la castration chimique ordonnée par le tribunal comme alternative à la prison. Il perdit son habilitation et, avec elle, le travail cryptographique qu'il aimait. La pomme, à moitié croquée près de son lit, devint le détail le plus mythifié de sa mort ; qu'elle ait porté le cyanure reste débattu, mais l'enquête conclut au suicide. En 2017, la Grande-Bretagne adopta la « loi Alan Turing », graciant à titre posthume des milliers de condamnés sous le même statut.

Impact sur la civilisation

Turing donna à la civilisation deux choses dont elle ignorait avoir besoin : la théorie et la pratique de l'informatique. La machine de Turing demeure la définition de la calculabilité enseignée à chaque étudiant en informatique de la planète ; c'est grâce à elle que nous savons, mathématiquement, ce que les ordinateurs peuvent et ne peuvent pas faire, et la machine universelle qu'il imagina est l'ancêtre directe de l'ordinateur à programme enregistré. La Bombe fit de la cryptanalyse une science industrielle et modifia sans doute l'issue de la Seconde Guerre mondiale. Son article de 1950 fonda l'intelligence artificielle comme champ d'investigation avant que le domaine eût un nom. La trajectoire de sa vie, un génie détruit par l'État pour sa vie privée, puis honoré à titre posthume sur la monnaie nationale, est aussi l'un des bilans moraux les plus saisissants du XXe siècle : une civilisation qui faillit jeter l'esprit qui l'avait sauvée. L'article de Turing de 1952 sur la morphogenèse est encore cité par les biologistes modélisant la formation des motifs, un rappel que son génie ne se confinait pas à l'informatique. Le mouvement de grâce qu'il inspira changea la loi britannique pour les vivants, pas seulement pour les morts.