Fehlender Status für Turingmaschine?

Question

Glaube hier fehlt ein Status für die Turingmaschine, bzw. ein Denkfehler in der Lösung. Der Status "s0" wandelt bereits geschriebene "e" und "n" während des Lesens wieder um, das dürfte jedoch erst am Schluss gesehen.

Bevor ich lange Worte verliere, hier anhand der Eingabe "001"

001|

n01|

n01|n

101|n

1n1|n

1n1|nn

nn1|nn

nn1|nnn

 

usw., das wäre jedoch falsch oder habe ich da was überlesen?

 

Answer 1

Ich habe die Konfigurationsfolge für das Wort 101 mal überprüft und bei mir hat alles geklappt. Du musst irgendwo zwischen deinem 3. und 4. Schritt einen Fehler gemacht haben, das n am Anfang des Wortes muss bis zum Ende stehen bleiben bis du nur noch n und e im Wort hast und dann wird alles ersetzt. Schaue am besten mal ab Schritt 3 nach warum bei dir da das n zu einer 1 wird, das sollte so nicht sein.

Viele Grüße

Patrick (Tutor)

 

Comments

Ich meinte das Wort "001". In der Konfigurationsabfolge hab ich mich dann leider zwischendrin mal vertippt. Hier nochmal richtig:

Für "001":


001|
n01|
n01|n
001|n
0n1|nn
nn1|nn
nn1|nnn

Auch für dein Wort "101" habe ich es mal überprüft und komme zu folgendem Ergebnis:

Für 101:

101|
e01|
e01|e
101|e
1n1|e
1n1|en
en1|en
en1|ene
10e|ene
10e|enee

usw.

---

Sorry, habe mich vertippt, ich habe schon dein Wort 001 getestet.

Also ich komme auf die Ableitung in deiner Schreibweise:

001|
n01|
n01|n
nn1|n

Wenn du in deinem 3. Schritt hinter das Wort ein n geschrieben hast, bist du danach in Zustand s2. Es kommt eine 1, dann wird in Zustand s3 gewechselt und die 1 bleibt stehen. In s3 kommt jetzt eine 0, Maschine bleibt in s3 und lässt auch die 0 stehen. Wenn dann im Zustand s3 das n ganz links gelesen wird, wechselt die TM in Zustand s0 und läuft wieder nach rechts. Die Maschine bleibt in s3, es kommt eine 0, sie schreibt ein n, geht in s1 und läuft nach rechts weiter.

Hier musst du glaube ich irgendwo einen Fehler gemacht haben, ich hoffe du findest ihn mit der Beschreibung.

Viele Grüße
Patrick (Tutor)