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

m1 = ["A","111000",0,"A0d,A1d,Ab1F"]
m2 = ["A","s000",0,"A0g,A1g,AsdB,B10d,B01gA,BbF"]
m3 = ["A","11b111",0,"A11d,Ab1Bd,B1d,BbgC,C1bF"]
m4 = ["A","111",2,"A0g,A10dB,AbdC,B0d,Bb0gA,C01d,CbF"]
m5 = ["A","bbb001101",0,"Abd,A0B,A1B,B01d,B1d,BbF"]
m6 = ["A","010110",0,"A0d,A1dB,AbdC,B0d,B1dA,BbdD,Cb0F,Db1F"]
m7 = ["A","111",2,"A0bG,A1gB,BbF,B0dD,B1dD,C0g,C1gD,CbdG,D01gC,Db1dG,D10gE,E1g,Eb0gD,E0gD,G0d,G1d,GbgA"]
m8 = ["A","",0,"Ab1dB,A1gB,Bb1gA,B1bgC,C1gD,Cb1dF,Db1d,D1bdA"]

def turing(pg):
    etat, rub, pos, code = pg
    
    # Ajouter une marge initiale
    rub = "bbb" + rub + "bbb"
    pos += 3

    prgm = {c[:2]: c[2:] for c in code.split(',')}

    while True:
        # ✅ Sécuriser la position AVANT lecture
        if pos < 0:
            rub = "b" + rub
            pos = 0
        elif pos >= len(rub):
            rub = rub + "b"

        c = rub[pos]

        if etat + c in prgm:
            actions = prgm[etat + c]

            input("{} {} pos={} action={}".format(etat,rub,pos,actions))

            for a in actions:
                if a in "b01s":  # écriture
                    rub = rub[:pos] + a + rub[pos+1:]

                elif a == "d":  # droite
                    pos += 1

                elif a == "g":  # gauche
                    pos -= 1

                elif a in "ABCDEFG":  # état
                    etat = a

            # ✅ IMPORTANT : re-sécuriser après déplacement
            if pos < 0:
                rub = "b" + rub
                pos = 0
            elif pos >= len(rub):
                rub = rub + "b"

            if etat == "F":
                print("FIN :", rub.strip("b"))
                return

        else:
            print("FIN (aucune règle) :", rub.strip("b"))
            return