Quelle était la machine imaginaire décrite par Alan Turing en 1936 ?

Alan Turing a imaginé une machine qui n'existe que sur le papier, et elle est devenue le modèle de référence de ce que fait un ordinateur. En 1936, il décrit ce qu'il appelle une «  a-machine » (machine automatique) : un appareil qui lit et écrit des symboles sur un ruban sans fin, case par case, en suivant une simple table de règles. Aussi basique que cela paraisse, le modèle de Turing est capable de mettre en œuvre n'importe quel algorithme informatique : avec elle, Turing a formalisé les notions mêmes d'algorithme et de calcul.

La machine elle-même n'a presque aucune pièce mobile au sens habituel. Elle dispose d'un ruban de cases, chacune contenant un symbole, d'une tête qui lit et écrit une case à la fois, et d'un état choisi parmi une liste finie. À chaque étape, elle lit le symbole sous la tête, puis, selon ce symbole et son état courant, elle écrit un nouveau symbole, déplace la tête d'une case vers la gauche ou la droite, ou s'arrête. C'est tout le mécanisme, et il suffit pour exécuter n'importe quel algorithme informatique.

Turing est allé plus loin : il a montré qu'une seule machine pouvait en simuler n'importe quelle autre, à condition de lui fournir la bonne description sur le ruban. Cette «  machine universelle » est considérée par certains comme la percée théorique fondamentale derrière l'idée de l'ordinateur à programme enregistré, où une même machine exécute le programme qu'on lui donne au lieu d'être reconstruite pour chaque tâche.

Turing ne s'est pas contenté de théoriser. Pendant la Seconde Guerre mondiale, son travail de décryptage a aidé les Alliés à déchiffrer les messages allemands chiffrés par la machine Enigma, et il a ensuite conçu l'Automatic Computing Engine, l'un des premiers ordinateurs à programme enregistré, transformant sa machine à ruban abstraite en matériel bien réel. Mais la Grande-Bretagne l'a mal récompensé : en 1952, après avoir reconnu une relation avec un autre homme, il a été poursuivi pour outrage aux mœurs et condamné à une mise à l'épreuve assortie d'une castration chimique. Il est mort en 1954, à 41 ans ; l'enquête a conclu à un suicide. Après une campagne en 2009, le Premier ministre a présenté des excuses officielles, et une grâce royale a suivi en 2013.