Simulation d'une machine de Turing

Explications du principe de la machine ici

m1 : Ajouter un 1 à droite d’une séquence
m2 : Compter en binaire
m3 : Addition unaire 11(2) + 111(3) = 11111(5)
m4 : Doubler les éléments 111 –> 111111
m5 : Remplacer les 0 par des 1
m6 : Parité du nombre de 1 dans une chaîne (0=pair, 1=impair)
m7 : Conjecture de Syracuse (voir Programme)
m8 : Castor affairé (voir Wikipédia)

Dans cette machine simplifiée il n’y a que 6 états possibles (A à F), l’état F étant l’état final.
On peut lire ou écrire sur le ruban les caractères b (blanc), 0 , 1 et s

Vous pouvez tester le programme dans l’émulateur de cette page ou sur https://repl.it/languages/python3 en copiant/collant le code.

>>  turing(m5)
EXE # Appuyez sur la touche EXE pour passer à l'étape suivante
A bbb001101 0 d # Etat = A, tête de lecture = 0, action = déplacement à droite
A bbb001101 1 d # La tête est maintenant en 1, action = déplacement à droite
A bbb001101 2 d # La tête en 2
A bbb001101 3 B # Mettre l'état à B
B bbb001101 3 1d # Ecrire un "1" et se déplacer à droite
B bbb101101 4 1d # Ecrire un "1" et se déplacer à droite
B bbb111101 5 d
B bbb111101 6 d
B bbb111101 7 1d
B bbb111111 8 d
B bbb111111b 9 F # Fin du programme

Explications rapides du programme

prgm = {c[:2]:c[2:] for c in code.split(',') } : On récupère les données du programme sous la forme “état+caractère” : “choses à faire”, par exemples "Ab" : "1F"
try: c = rub[pos] : On tente de lire ce qu’il y a sur le ruban (problème si pos est négatif ou plus grand