Verständnis des Schritts (s2, 0):(sN, 1, N/R)

Question

Wie ist die Lösung genau zu verstehen

bei (s2, 0 ) steht (sN, 1, N/R) heißt das, dass die TM entweder den Kopf nicht bewegt und somit auf 0 stehen bleibt für N oder für R den Kopf um eins nach rechts bewegt?

Was hat das N dann für einen Sinn? Wenn die TM in s2 eine 0 liest, muss doch das gesamte Wort mit 0 überschrieben werden und die TM kann doch nicht einfach auf 0 stehen bleiben?

 

Answer 1

Hallo,

so wie ich das sehe sind die Übergänge von denen Sie sprechen nur zur Erkennung da, ob ein Wort in der Sprache liegt. Es wird bei diesen Übergängen jeweils in einen Zustand gewechselt, welcher dann die nötigen Übergänge zum überschreiben sowieso hat. Es ist also in dem Fall egal, ob vor dem Zustandswechsel bereits das erste Zeichen überschrieben wird und weiter nach rechts gegangen wird, oder erst einen Schritt später.

Ich hoffe das hilft Ihnen zum Verständis.

Viele Grüße,

Janina (Tutorin)