Alan Turing : du concept à la machine

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