turing.py

Created by schraf

Created on October 24, 2022

1 KB

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,"Ab1F,A0d,A1d"]
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
  prgm = {c[:2]:c[2:] for c in code.split(',') }
  while True:
    if pos < 0: 
     rub = "b"+rub
     pos = 0
    try: c = rub[pos]
    except:
     c = "b"
     rub += "b"
    if etat+c in prgm:
      faire = list(prgm[etat+c])
      print(etat,rub,pos,prgm[etat+c],end=' ')
      q = input("EXE")
      for a in faire:
        if a in "b01s": rub = rub[:pos] + a + rub[pos+1:]
        if a in "gd": pos += (a == "d") - (a == "g")
        if a in "ABCDEFG": etat = a
    else: return "FIN"