Puis Turing vint...

Alan Turing est peu connu du grand public. Pourtant, il apporta une contribution décisive à la naissance de l’ordinateur en plus de jouer un rôle essentiel dans le décryptage du fameux code Enigma développé par les Allemands autour de la Deuxième Guerre mondiale.

Un excellent film présente actuellement la vie du mathématicien sur nos écrans : Le jeu de l’imitation. Bien que romancée, comme il sied à ce genre de production, cette fresque, qui s’attarde en priorité sur trois périodes de sa vie, nous donne malgré tout une bonne idée de l’homme et de ses travaux. Elle offre aussi l’occasion de se pencher sur un sujet difficile : les débuts de l’informatique théorique¹.

L’ordinateur naît au début des années 1940. Il est difficile d’en identifier le créateur, car plusieurs machines peuvent prétendre au titre d’ancêtre, qu’il s’agisse du Z3 allemand, du Colossus britannique ou encore des Mark I et ENIAC américains. Mais ce qui est sûr, c’est qu’il fallait d’abord concevoir l’idée d’une machine universelle; ce fut l’œuvre de Turing. Pour comprendre dans quel contexte il réalisa ce tour de force, il faut revenir en arrière et toucher un mot de la célèbre crise des fondements en mathématiques.  

Validité n’égale pas toujours vérité

On sait que le XIX^e siècle fut marqué par la naissance des géométries non euclidiennes. Ces axiomatiques concurrentes entraînèrent une crise importante en mathématiques, le domaine par excellence de la certitude pendant des siècles. En effet, à partir de systèmes géométriques incompatibles, il était maintenant possible d’obtenir des théorèmes contradictoires, tous rigoureusement démontrés, et tous dérivés d’axiomes apparemment sans faille. Les postulats de départ de ces systèmes étaient différents, soit, mais comment diable une telle chose était-elle possible?

En attendant de trouver une solution à cette situation paradoxale, il fallut se résoudre à découpler vérité et validité : une axiomatique canonique pouvait être parfaitement ordonnée, épouser en outre notre intuition traditionnelle de l’espace, et n’être pas « vraie » pour autant, c’est-à-dire ne pas correspondre à la réalité. En d’autres termes, la légalité de la géométrie euclidienne devenait soudain problématique. Certes, la démonstration demeurait la norme pour éprouver la validité des nouveaux théorèmes, mais on ne pouvait plus tabler sur l’évidence des axiomes.

C’est pour apporter une solution définitive à ces troublants développements que Cantor (1845-1916) élabora sa fameuse théorie des ensembles. Grâce à son travail novateur, qui assoyait l’édifice mathématique tout entier sur de nouvelles bases, le ciel semblait s’éclaircir à nouveau. Hélas, on identifia bientôt des paradoxes dans la théorie cantorienne elle-même.

Logicisme, intuitionnisme et formalisme

Trois écoles mathématiques concurrentes virent alors le jour, toutes trois déterminées à tirer les conséquences de cette crise et à y apporter les correctifs nécessaires. En quoi consistent-elles?

Soit on tente de rabattre les mathématiques sur la logique, les faisant profiter de sa rigueur. C’est l’immense programme qu’entreprit de réaliser le philosophe et mathématicien britannique Russell (1872-1970), en collaboration avec son ancien professeur Whitehead (1861-1947). On appelle cette première avenue le logicisme parce que, pour elle, la nature du nombre est dérivée.

Soit encore on rejette certains types classiques de raisonnement parce qu’ils mènent à des contradictions lorsqu’on les applique à des ensembles infinis, une des marques de commerce de la théorie de Cantor. C’est ainsi que le mathématicien néerlandais Brouwer (1881-1966) et son disciple, le logicien Heyting (1898-1980), en viennent à écarter le raisonnement par l'absurde et le tiers exclu comme principes universellement valides. Cette deuxième approche est appelée intuitionniste, parce que ses deux promoteurs appuyaient les mathématiques sur l’arithmétique, qu’ils considéraient comme une production de l'esprit humain reposant elle-même sur la liberté créatrice et une intuition primitive du temps². Cette avenue a d’ailleurs ouvert la voie aux diverses variétés de constructivisme, une position actuellement assez répandue chez les mathématiciens et les philosophes des mathématiques.

La troisième et dernière solution considère aussi les mathématiques comme une construction de l’esprit, mais à la différence de l’intuitionnisme, elle fait son deuil de la vérité. Pour le formalisme, en effet, les mathématiques constituent une sorte de jeu intellectuel, et dans la série d’opérations qu’il développe, le mathématicien ne doit pas se préoccuper de la nature des symboles ou des signes qu’il manipule : seules lui importent la non-contradiction de ses propositions et la cohérence de ses démonstrations. Il n’a donc pas à se demander si ses axiomes de départ sont vrais ou faux, mais seulement si son axiomatique est consistante et si elle est complète. Cette position a été élaborée par le mathématicien allemand David Hilbert (1862-1943).

Le problème de la décision

C’est ici que le Britannique Alan Turing (1912-1954) entre en scène. Formé en mathématiques et versé en logique, il pense d’abord s’attaquer à la question très débattue des fondements. Mais il rejette à la fois le logicisme et l’intuitionnisme. Le logicisme parce que, selon lui, le nombre est une donnée primitive qu’on ne peut réduire à des caractéristiques ensemblistes. Sur ce point, il abonde donc dans le sens de l’intuitionnisme, sauf qu’il ne peut cependant accepter l’amputation que cette école impose à l’univers mathématique. Au début, Turing va donc emprunter l’avenue ouverte par Hilbert. C’est dans cet esprit qu’il s’inscrit, au printemps 1935, à l’âge de 22 ans, au cours donné à Cambridge par Max Newman, un adepte du formalisme. Cependant, il doit très vite déchanter. En effet, il subit alors un choc qui va orienter toute sa future vie professionnelle et intellectuelle : c’est le fameux Entscheidungsproblem, le problème de la décision. Ici, un mot d’explication s’impose.

Pour réaliser son ambitieux programme, Hilbert devait présumer l’existence d’un algorithme, une procédure universelle permettant de déterminer avec certitude quels théorèmes on peut déduire d’un système d’axiomes quelconques, bref, permettant à coup sûr l’entscheidung, la décision (1928). Prenant ce programme à la lettre, Kurt Gödel (1906-1978), un jeune logicien autrichien, décide de le tester. Or il se rend compte que tout système formel suffisamment puissant pour inclure l’arithmétique des entiers naturels comportera au moins une proposition qui n’est pas décidable, c’est-à-dire qui n’est ni démontrable, ni réfutable à l’intérieur du système. En outre, il prouve qu’une axiomatique, quel que soit par ailleurs le nombre de théorèmes qu’on en peut dériver, ne saurait faire la démonstration de sa propre cohérence. Ce sont les célèbres théorèmes d'incomplétude (1931). L’espoir de produire un système formel à la fois cohérent et complet s’évanouissait soudain, et cette limite entraînait en même temps la chute du rêve hilbertien.

Proposition décidable et nombre calculable

Perplexe, Turing décide alors d’aborder autrement la question. Fort originale, son optique marquera l’histoire. S’il existe, raisonne-t-il, l’algorithme recherché par Hilbert doit être purement mécanique et, par conséquent, une machine idéale serait en mesure de le mettre en application. Dans un article intitulé On computable numbers, with an application to the Entscheidungs problem, il établit d’abord un lien logique entre proposition décidable et nombre calculable. Ensuite, il imagine ce qu’on appelle, depuis lors, une machine de Turing, c’est-à-dire le modèle abstrait d’une machine universelle de calcul. C’est ce cerveau mécanique, capable en principe de traiter toute fonction mathématique, pourvu évidemment qu’elle soit calculable (computable, comme disent les anglophones), que matérialisera plus tard l’ordinateur, le computer. C’est pourquoi, aujourd’hui, on considère ce travail comme une étape décisive dans la naissance de l’informatique théorique.

Cependant, pour la petite histoire, notons que le texte de Turing, prêt en 1936, paraît seulement début 1937. Or, manque de pot, c’est justement en 1936 que le mathématicien et logicien américain Alonzo Church (1903-1995), qui correspondait depuis quelque temps avec Gödel, publie un article où il parvient à la même conclusion que Turing. Le contenu de son texte présentant ce qu’on appelle le lambda-calcul (λ-calcul) est assez technique, mais certaines de ses conséquences sont claires : non seulement on peut définir des procédures mécaniques de calcul, mais on peut même formaliser le concept de calculabilité. Cependant, malgré cette élaboration probante de l’algorithmique, il n’existe pas, comme l’avait déjà montré Gödel, de solution universelle pour l’Entscheidungsproblem.

Après avoir pris connaissance de cet important résultat, le jeune Turing, bon prince, ne fait ni une ni deux et, pour travailler avec Church, effectue un voyage décisif pour l’orientation de sa carrière. Ainsi, c’est aux États-Unis, sous la direction du chercheur américain lui-même, qu’il soutiendra un doctorat en logique mathématique. Après vingt-deux mois bien remplis, il est de retour au pays (juillet 1938), mais il retournera deux fois en Amérique, la première au plus fort du conflit afin de contribuer à l’effort de guerre commun (fin 1942-début 1943), la deuxième pour participer à un important colloque à Harvard (1947). Il rentrera ensuite en Angleterre pour ne plus la quitter avant sa mort, survenue sept ans plus tard, dans des circonstances dramatiques.

L’inimitable Turing

Le jeu de l’imitation n’aborde pas ces différents aspects, et s’articule plutôt autour de l’adolescence de Turing, de son travail de décryptage durant la guerre et de sa mort. C’est dommage, bien sûr, mais peut-être était-ce trop demander à une fiction grand public que de se pencher sur le fondement des mathématiques et la théorie de la calculabilité, même si ces deux axes de recherche ont été déterminants dans la vie de Turing et la préhistoire de l’informatique.

Mais revenons à notre question initiale : quelle machine peut prétendre au titre de premier ordinateur? On l’a dit, il n’y a pas de réponse évidente à une telle question. Si, par contre, l’on demande qui a joué un rôle crucial dans la naissance de l’informatique théorique et qui a entrevu le principe du futur ordinateur, la réponse va de soi : il s’agit de Turing³. En ce sens, le film atteint bien son objectif, puisqu’il permet au néophyte de prendre connaissance d’une partie de son travail et de mesurer l’énorme apport de cet authentique génie. Il a en outre le mérite d’attirer l’attention sur l’une des grandes aventures intellectuelles du XX^e siècle, la création de l’intelligence artificielle. À une époque où l’ordinateur est devenu incontournable dans la plupart des secteurs de notre vie, c’est une réalisation digne de mention. 

Notes :

• 1. J’aimerais remercier mon ancien collègue Lucien Roy, professeur retraité d’informatique au Cégep de Rimouski, dont les suggestions judicieuses ont permis d’améliorer une première version de ce petit texte sans prétention. 
• 2. Sur ce point, Brouwer reconnaissait volontiers sa dette envers le philosophe idéaliste allemand Kant (1724-1804) et sa célèbre théorie du temps et de l’espace comme formes a priori de la sensibilité.
• 3. En toute justice, il faut mentionner ici au moins un autre théoricien ayant pesé sur la naissance de l’ordinateur, le mathématicien hongrois John von Neumann (1903-1957), qui en a plus tard proposé l'architecture physique, c’est-à-dire une mémoire interne stockant données et programmes, associée à des périphériques. L'ordinateur actuel épouse encore cette conception.