Verständnis Turing Maschinen - was passiert?

Question

Für was stehen die einzelnen Zustände und was passiert? Wie ist die Vorgehensweise?

Answer 1

Hallo ugeil!

Bitte versuche in Zukunft deine Frage  genauer zu stellen, d.h. deinen bisherigen Lösungsweg zu beschreiben und zu erklären, wo genau dein Verständnisproblem liegt.

Ich versuche dennoch dir kurz die Vorgehensweise der Turingmaschine (im Folgenden mit TM abgekürzt)  zu erläutern:

Zustand s0: Die TM liest das Wort von links nach rechts und übergeht alle 0. Falls sie auf eine 1 stößt (nehmen wir o.B.d.A. an, dass dies an einer geraden Stelle im Wort geschieht), dann überschreibt sie diese 1 mit einer 0 und geht in den Zustand s1.

Zustand s1 (und s2): Da sich die TM vor dem Wechsel in Zustand s1 an einer geraden Stelle im Wort befand, befindet sich der Lesekopf nun auf einer ungeraden Stelle. Die 0 werden wieder einfach übergangen, wobei die TM nun zwischen Zustand s1 und Zustand s2 wechselt, damit sie weiß, ob sie gerade eine Zahl an einer ungeraden Stelle (=Zustand s1) oder an einer gerade Stelle (=Zustand s2) des Wortes liest.

• Falls sie im Zustand s1, also an einer ungeraden Stelle auf eine weitere 1 stößt, dann überschreibt sie diese 1 mit einer 0, denn sie hat nun zu der in Zustand s0 gefundenen 1 (an gerader Stelle) eine 1 an ungerader Stelle gefunden. Außerdem geht sie TM in Zustand s3 über, durch welchen sie mit dem Lesekopf wieder ganz nach links im Wort wandert und das ganze Spiel von vorne beginnt.
• Falls sie im Zustand s2, also wieder an einer geraden Stelle, auf eine weitere 1 stößt, so übergeht sie diese 1 zunächst (sie wird später bearbeitet) und sucht stattdessen weiter nach einer 1 an ungerader Stelle.

Zustand s3: Ist wie eben erwähnt zum Zurücklaufen nach links nötig

Zustand se: Endzustand, in den die TM gelangt, wenn entweder gar keine Einsen auf dem Band enthalten waren bzw. die TM durch das oben beschriebene Vorgehen in der Lage war, immer Paare von 1 an geraden und ungeraden Stellen zu finden und sie jeweils mit 0 zu überschreiben.

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)