digital / tiny turing machine

Petite machine de Turing où l’information écrite dans les cases du “ruban” (20 cases) est codée par l’état d’une led :
– 0 : led clignotante
– 1 : led allumée
– vide : led éteinte

Conformément au principe d’une machine de Turing, la logique de contrôle est assurée par l’exploitation d’une table de transitions traduisant le graphe des états possibles du système et évoluant en fonction des informations lues et transmises par la tête de lecture/écriture. La logique de contrôle opère les quatre fonctions suivantes :
– lecture de l’information inscrite dans la case au dessus de laquelle se trouve la tête ;
– écriture d’une information dans la case au dessus de laquelle se trouve la tête ;
– demande de déplacement de la tête d’une case à droite ou à gauche ;
– mise à jour de l’état courant du système à partir de la table de transitions et mémorisation.

Des graphes d’états pour la reconnaissance de palindromes, l’addition, la soustraction et la multiplication de nombres binaires ont été produits.

Exemple du graphe d’états pour l’addition de 2 nombres binaires :

Les deux nombres sont écrits l’un à la suite de l’autre séparés par une case vide. La tête de lecture/écriture est initialement positionnée à gauche du premier caractère. Le calcul consiste ici à incrémenter le premier nombre autant de fois qu’il est possible de décrémenter le second jusqu’à ce que ce dernier soit nul. Le résultat final prend donc la place du premier nombre.
Exemple pour le calcul de 5 + 3 :
Etat initial du ruban : 101 11
Etat final du ruban : 1000 00