Les Newsletters Interstices
© A. Couty, CRDP de l’académie de Versailles
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    Alan Turing : du concept à la machine

    Histoire du numérique
    Algorithmes
    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

    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).

    La première version de la machine Automatic Computing Engine (Ace) fut réalisée au Laboratoire national de physique britannique (National Physical Laboratory, NPL) et mise en service en 1950. Version réduite (dite « pilote ») d’un projet plus ambitieux proposé en 1945-1946 par Alan Turing, c’était à l’époque l’ordinateur le plus rapide existant, avec une fréquence d’horloge de 1 MHz. Les journaux de l’époque annonçaient alors la mise en service d’un « cerveau électronique » capable de faire en une minute le travail d’un mois. Cette machine resta en service pendant cinq ans ; elle fut surtout utilisée pour le calcul scientifique et inspira d’autres projets d’ordinateurs. En 1955, la société English Electric réalisa à partir de la version pilote d’Ace un ordinateur commercial, le Deuce, dont une trentaine d’exemplaires furent construits. Le NPL réalisa une machine Ace complète en 1957. Conçue sur des bases techniques dépassées, cette version eut moins de succès que la version initiale.

    Pour aller plus loin :
    mini site du National Physical Laboratory consacré à Alan Turing.

    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).

    Alan Turing se tient debout à côté de deux collaborateurs assis en face de l’ordinateur Ferranti Mark 1, à Manchester. Il s’agit du premier ordinateur commercial de l’histoire : il sortit en février 1951, devançant de quelques mois l’Univac-1 de Remington Rand. Neuf machines furent vendues en tout : la première à l’université de Manchester, la deuxième à l’université de Toronto. Une machine partit en Hollande, une autre en Italie… Le Ferranti Mark 1 était issu de l’ordinateur expérimental Mark 1 conçu à l’université de Manchester par Frederic Williams et Thomas Kilburn. Mis en service en juin 1949, le Manchester Mark 1 était avec l’Edsac de Cambridge l’un des tout premiers ordinateurs à programme enregistré. Il avait une mémoire à tubes cathodiques, contrairement aux autres machines de l’époque qui utilisaient des lignes à retard. Alan Turing, arrivé à Manchester en septembre 1948, participa à la réalisation du logiciel de base du Mark 1 et rédigea son premier manuel de programmation.

    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.

    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.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

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

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

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Sacha Krakowiak

    Professeur émérite d'informatique à l'Université Joseph Fourier.
    Voir le profil

    Découvrez le(s) dossier(s) associé(s) à cet article :

    Dossier

    Ressources en sciences numériques pour le lycée

    DossierCulture & Société

    DocSciences