Machine de Turing

Car c’est bien une machine abstraite qu’Alan Turing a inventée pour expliquer la notion de « procédure mécanique » : on parle d’algorithme. Cette machine est la plus élémentaire possible destinée à mettre en œuvre ces mécanismes de calcul, numériques ou symboliques, comme le font notamment les ordinateurs. Ne perdons pas de vue que lorsqu’Alan Turing décrit sa machine dans un article en 1936, les ordinateurs n’existent pas encore !

Essayons de la découvrir… en l’utilisant

La machine imaginée par Turing comporte un ruban divisé en cases, dans lesquelles elle peut écrire des symboles. La machine ne peut lire qu’une seule case à la fois, de même elle écrit dans une seule case et décale le ruban d’une seule case vers la gauche ou vers la droite. Les symboles sont en nombre fini. Pour que sa machine fonctionne comme une machine à calculer en binaire, Turing envisage le cas particulier où les symboles utilisés sont 0 et 1. C’est une telle machine que nous vous proposons de tester sur l’applet suivante. Vous pourrez y suivre l’exécution de cinq « programmes ».

L’entrée du programme est une liste de symboles binaires, écrits sur le ruban blanc. Une fois le calcul effectué, c’est sur ce ruban que sera écrit le résultat du calcul, la sortie du programme. À chaque instant, le ruban mémorise l’état du calcul. Voilà la forme la plus simple de mémoire mécanique !

À chaque programme correspond une description sous forme de table. Chacune des lignes de cette table est associée à un état et spécifie les actions à effectuer quand la machine est dans cet état, en fonction du symbole présent sous la tête de lecture. Ces actions peuvent être l’écriture d’un symbole (ici un 0 ou un 1) et le déplacement du ruban d’une case à droite ou à gauche. La ligne spécifie également le nouvel état après l’exécution des actions.

Une représentation équivalente de cette table est un graphe dont chaque sommet décrit un état. En fonction du symbole sous la tête de lecture, des actions sont exécutées et un nouvel état est atteint. C’est ce graphe, avec ses sommets numérotés comme les états, et ses transitions, qui apparaît sous la tête de lecture du ruban. Les actions conditionnées par le caractère présent sous la tête de lecture apparaissent au fur et à mesure dans la boîte de messages en bas.

La machine s’arrête quand un état marqué comme final est atteint.

Turing a également prévu que les programmes, tels qu’ils sont décrits par la table ou sur le graphe, puissent eux aussi être codés en binaire et inscrits sur un deuxième ruban. Chaque code correspond alors à une instruction possible. Le calcul se déroule automatiquement en passant d’une instruction à une autre. Comme il est possible d’inscrire sur ce deuxième ruban toutes sortes de programmes et de les exécuter, ce mécanisme va pouvoir faire (avec beaucoup de patience !) tout ce qu’un ordinateur peut faire. On parle de machine de Turing universelle.

À vous ! Choisissez d’abord un « programme » parmi les cinq que nous vous proposons ici :

1. ajouter 1 à un nombre binaire
2. soustraire 1 à un nombre binaire
3. multiplier par 2 un nombre binaire
4. inverser les 0 et les 1 formant un nombre binaire et recommencer indéfiniment
5. doubler la longueur d’une suite de 1

Entrez un nombre, puis en utilisant les touches « Début » ou « Pas-à-Pas », regardez s’exécuter le programme.

Ces programmes sont rudimentaires mais très instructifs : ils montrent que l’on peut faire des opérations numériques (les 0 et les 1 correspondent au codage binaire de nombres) ou symboliques (les 0 ou les 1 codent des symboles).

Ouf ! Pas facile de suivre à la fois le calcul pas à pas et de se représenter en même temps globalement ce qui est calculé ! Nous voilà, en quelque sorte, à l’échelle « atomique » du calcul, devant les briques de base de ce qui compose tous les algorithmes.

En effet, en combinant ces briques de base, ce sont tous les algorithmes qui peuvent s’implémenter. Par exemple, en ajoutant plusieurs fois 1, nous pouvons additionner plusieurs nombres, puis en combinant les additions faire des multiplications, et de proche en proche tous les calculs numériques, tandis que des procédés similaires s’appliquent aux calculs symboliques.

De fait, nous pourrions très bien reproduire aussi ces calculs avec un ruban de papier, un crayon et une gomme. Car peu importe le support utilisé : les mécanismes algorithmiques s’incarnent dans un grand nombre de dispositifs physiques, qui peuvent ainsi être considérés comme équivalents.

Enfin, n’oublions pas non plus que c’est nous qui, en lisant le résultat d’un calcul, lui donnons un sens…