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
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"