Interstices


  Découvrir

Comment fonctionne une machine de Turing ?

Essayons de faire quelque chose de paradoxal : montrer concrètement comment marche une machine abstraite !

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'animation interactive suivante. Vous pourrez y suivre l'exécution de six « programmes ».

Animation HTML5/JS réalisée par Hugo Lehmann, librement adaptée d'une applet Java écrite par Hamdi Ben Abdallah.
Accéder aux sources.

 

L'entrée du programme est une liste de symboles binaires, écrits sur le ruban, matérialisé par les cases successives (en bas de l'animation). 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 (à droite de l'animation). 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.

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, 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 six que nous vous proposons ici :

  1. ajouter 1 à un nombre binaire - description détaillée
  2. soustraire 1 à un nombre binaire - description détaillée
  3. multiplier par 2 un nombre binaire - description détaillée
  4. inverser les 0 et les 1 formant un nombre binaire et recommencer indéfiniment - description détaillée
  5. doubler la longueur d'une suite de 1 - description détaillée
  6. détecter des palindromes - description détaillée

Entrez un nombre binaire, puis en utilisant les touches « Commencer » 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...