Alan Turing : du concept à la machine

Alan Turing a contribué à l’informatique à la fois sur un plan conceptuel, avec la fameuse « machine de Turing », puis, quelques années plus tard, en participant concrètement à la réalisation des premiers ordinateurs. Retour sur un itinéraire, de la théorie à la pratique.

En 1936, Alan Turing décrit une machine abstraite pour donner un support formel aux notions d’algorithme et de calcul effectif. Aujourd’hui, on reconnaît la « machine de Turing » comme un modèle abstrait de l’ordinateur, bien que les concepteurs des premiers calculateurs aient ignoré les travaux de Turing.

La machine modèle

© A. Couty, CRDP de l’académie de Versailles.

Rappelons brièvement qu’une machine de Turing est un automate imaginaire muni d’un programme (sous la forme d’une table de transition entre états) et pouvant lire et écrire des caractères sur un ruban de longueur illimitée. Tout algorithme (procédé systématique de calcul) peut être réalisé par une machine de Turing : c’est la « thèse de Church-Turing », du nom des deux mathématiciens Alonzo Church et Alan Turing. Cette thèse est indémontrable par essence en l’absence précisément d’une définition formelle d’un algorithme, mais elle n’est pas contredite à ce jour.

Une machine de Turing est un instrument purement conceptuel. Si elle était réalisée physiquement, elle serait monstrueusement inefficace, car le niveau très élémentaire de ses opérations entraîne une expression extrêmement longue des algorithmes les plus simples. Une contribution cruciale d’Alan Turing est la preuve de l’existence d’une machine de Turing dite « universelle ». Si on fournit à cette dernière la table de transition d’une machine de Turing particulière, autrement dit le programme d’un algorithme, elle est capable de reproduire le fonctionnement de cette machine, donc d’exécuter le programme en question.

La possibilité d'un ordinateur

On reconnaît ici l’idée d’un ordinateur universel, apte à exécuter tout programme qu’on lui fournit. Mais une autre notion centrale, moins évidente a priori, s’y trouve en germe. Le programme d’une machine de Turing particulière, représenté par sa table de transition, est fourni comme donnée à la machine universelle, codé sur le ruban que va lire celle-ci. On voit donc que :

  • programmes et données sont représentés de la même façon sur un support unique, ici le ruban ; la différence n’est qu’une question de codage, donc de convention ;
  • un programme peut servir de donnée à un autre programme. En filigrane se dessinent les « interprètes », « compilateurs », « analyseurs »… qui sont familiers en informatique aujourd’hui.

Il n’est pas sûr que toutes les implications de ces propriétés aient été perçues à l’époque. Il fallut attendre l’expérience des calculateurs réels pour reconnaître tout le potentiel du modèle de la machine de Turing universelle. Pour un ordinateur, un critère de puissance expressive est d’avoir une capacité équivalente à celle d’une machine de Turing universelle (aux limites physiques près). L’ordinateur est alors dit « Turing-complet ».

Comment s’est faite la jonction entre les idées de Turing et la conception des ordinateurs ? Retraçons brièvement l’histoire de ce qu’on appelait alors les calculateurs.

Les premiers calculateurs

À partir de la fin des années trente, des inventeurs réalisent indépendamment des machines électroniques ou électromécaniques pouvant exécuter des calculs complexes à grande vitesse. Ces précurseurs ignorent les travaux théoriques d’Alonzo Church, Stephen Cole Kleene ou Alan Turing car ce sont en général des ingénieurs électroniciens qui évoluent dans un monde différent de celui des mathématiciens.

Citons les projets les plus notables :

  • En 1937, au Iowa State College, John Atanasoff et son étudiant Clifford Berry conçoivent le premier calculateur utilisant des tubes à vide électroniques. Cette machine (non Turing-complète) est spécialisée pour la résolution de systèmes linéaires. Un prototype fonctionne en 1941.
  • En 1941, Konrad Zuse réalise à Berlin le Zuse Z3, un calculateur électromécanique ; c’est la première machine Turing-complète.
  • En 1943, Presper Eckert et John Mauchly lancent un grand projet de calculateur à l’université de Pennsylvanie.

Soutenu par le département de la Défense, il aboutira en 1946 à la réalisation de l’Electronic Numerical Integrator and Computer (l’Eniac), premier calculateur électronique Turing-complet. Cependant, l’Eniac a un défaut majeur : il est programmé par câblage d’un tableau de connexion, un processus complexe, fastidieux et sujet aux erreurs. Presper Eckert et John Mauchly, conscients de cette faiblesse, œuvrent dès 1944 à la conception du successeur de l’Eniac, l’Electronic Discrete Variable Automatic Computer (l’Edvac).

L’ordinateur à « programme enregistré »

C’est ici qu’entre en scène John von Neumann, un autre « père » de l’informatique. Il avait rencontré Alan Turing et connaissait ses travaux. En 1945, alors qu’il participait à la conception de l’Edvac, il publie sous son seul nom un rapport où il définit le modèle de l’ordinateur à « programme enregistré ». La mémoire de cet ordinateur contient à la fois les programmes et les données, comme dans la machine de Turing universelle ! Cette architecture virtuelle pose les principes de l’organisation des ordinateurs et régit toujours leur fonctionnement aujourd’hui. Notons au passage que l’appellation « architecture de von Neumann », consacrée par l’usage, ne rend pas justice au travail de Presper Eckert et de John Mauchly ni à l’influence des idées d’Alan Turing. Les premières machines à programme enregistré furent construites en Angleterre en 1949 : l’Electronic Delay Storage Automatic Calculator (l’Edsac) à Cambridge et le Mark 1 à Manchester. Turing participa à ce dernier projet.

Alan Turing et les premiers ordinateurs

Le prototype du calculateur électronique universel à programme enregistré, l’Automatic Computing Engine, l’Ace, en 1950. Cette machine, mise en service en 1950, était l’ordinateur le plus rapide de l’époque. D’après les journaux de l'époque, c’était un « cerveau électronique » qui effectuait le travail d’un mois – surtout des calculs scientifiques – en une minute ! En 1955, une trentaine d’exemplaires furent construits et commercialisés.
© Photographie reproduite avec l’autorisation du National Physical Laboratory, NPL (Angleterre).
 
 

Turing était au départ un théoricien, mais au cours de sa brève carrière, il s’est aussi impliqué dans des projets concrets de conception d’ordinateurs : Colossus, Ace, Manchester Mark 1.

Colossus

Au cours de la seconde guerre mondiale, Alan Turing travaillait à Bletchley Park, centre dédié au décryptage des codes secrets utilisés par l’armée allemande. Il obtint un premier succès en 1940 en décryptant le code de la machine Enigma. Le décodage était assisté par des machines spécialisées, appelées « Bombes », réalisées d’après ses plans. Mais les Allemands mirent en service un système de chiffrement plus complexe, le code Lorenz. Celui-ci fut également décrypté en 1942 ; toutefois le processus manuel de transcription était trop long pour un usage opérationnel. Aussi une nouvelle machine, le Colossus, fut conçue et réalisée par une équipe dirigée par Thomas Flowers pour un décryptage rapide du code Lorenz. Le premier Colossus, construit en onze mois, fut mis en service en janvier 1944 et dix exemplaires fonctionnaient à la fin de la guerre.

Le principe de conception du Colossus et l’existence même de cette machine furent déclarés secret militaire. Les dix machines furent détruites en 1945. Le secret ne fut que partiellement levé en 1975. Grâce aux plans conservés (illégalement) par des ingénieurs travaillant sur le projet, un exemplaire du Colossus a pu être reconstitué et a fonctionné pour la première fois en 1996.

Comment se situait le Colossus parmi les machines contemporaines et quel a été le rôle de Turing dans ce projet ? Le Colossus, conçu pour un usage spécifique, n’était pas Turing-complet. C’était un calculateur électronique programmable au moyen d’un tableau de connexion comme l’Eniac qu’il précédait de deux ans. Dans sa dernière version, il comportait 2400 tubes à vide (à comparer aux 18 000 de l’Eniac).

Alan Turing n’a pas directement participé à la conception du Colossus, mais il avait fait venir Thomas Flowers à Bletchley Park et avait travaillé avec lui sur une machine électromécanique antérieure au Colossus, le Heath Robinson. La personnalité d’Alan Turing exerçait un fort rayonnement à Bletchley Park et ses travaux sur la machine universelle étaient connus des mathématiciens du centre, notamment de Max Newman, le chef de la section qui abritait le Colossus.

Ace

Dès la fin de la guerre, Alan Turing, qui avait été engagé au National Physical Laboratory (NPL), voulut construire un calculateur électronique universel à programme enregistré. Il produisit un document de spécification fin 1945, et le projet, nommé Automatic Computing Engine (Ace), démarra en 1946. L’expérience du Colossus avait convaincu Alan Turing de la faisabilité de son projet, mais le secret militaire lui interdisait d’en faire état. Sa proposition fut jugée trop ambitieuse et une version plus modeste fut adoptée. Le projet fut retardé en raison de problèmes de management et d’organisation. Découragé, le mathématicien quitta le NPL en 1947 pour Cambridge et rejoignit en 1948 l’équipe du Mark 1 à Manchester. Le projet Ace finit par aboutir en 1950. À cette époque, l’Ace était le calculateur le plus rapide existant, avec une fréquence d’horloge de 1 MHz.

Manchester Mark 1

Alan Turing inspectant la console du Ferranti Mark 1. C’est en 1951 qu’est vendu le premier ordinateur commercial à programme enregistré, le Ferranti Mark 1. Neuf machines seront vendues dans le monde. Alan Turing a participé à la création du logiciel de base et a rédigé le manuel de programmation.
Photographie reproduite avec l’autorisation de l’université de Manchester, School of Computer Science (Angleterre).

Max Newman créa en 1945 un laboratoire d’informatique à l’université de Manchester. Frederic Williams et Thomas Kilburn y réalisèrent une mémoire utilisant l’écran d’un tube cathodique pour le stockage de bits (technique dont Alan Turing avait anticipé l’avènement dès 1945). En 1948, ils réussirent à exécuter un programme ainsi enregistré. Un calculateur complet fondé sur ce principe, le Mark 1, fonctionnait dès mi-1949 et servit de base au premier ordinateur commercial, le Ferranti Mark 1. Alan Turing, arrivé à Manchester en septembre 1948, participa au développement du logiciel de base du Mark 1 et rédigea son premier manuel de programmation. Il utilisa plus tard le Mark 1 pour ses recherches sur la morphogenèse.

L’histoire des contributions de Turing à la naissance de l’ordinateur montre que l’influence de ses idées a été déterminante. La reconnaissance en a été tardive car cette influence ne s’est pas manifestée de manière directe. Mais à peine plus de dix ans ont suffi pour passer d’un modèle mathématique abstrait à des machines possédant, aux performances près, les caractéristiques des ordinateurs actuels.

Pour en savoir plus.

Cet article est paru dans la revue DocSciences n°14 Alan Turing : La pensée informatique, éditée par le CRDP de l'Académie de Versailles en partenariat avec Inria.

Tags

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).