Turing-Werkstatt

Theoretische Informatik am PC

Turing-Maschine
Alan M. Turing hat 1936 in seiner Arbeit "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM" ein einfaches Rechnermodell vorgestellt, dass in der Informatik bis heute als mächtigstes Hilfsmittel gilt, um Algorithmen auszuführen. Alles, was algorithmisch machbar ist, lässt sich mit einer Turing-Maschine bewerkstelligen (Church-Turing-These).
Beispiele aus Turings Artikel : Turing1.tm, Turing2.tm
Turing-Maschinen können sehr unterschiedlich definiert werden Bei aller Unterschiedlichkeit gilt : Alle diese Typen sind gleich mächtig. D.h. zu jeder Maschine, die eine bestimmte Aufgabe erledigt, gibt es Maschinen jedes anderen Typs, die dasselbe leisten können. Allerdings kann sich der Zeitaufwand je nach Typ erheblich unterscheiden.

Download aller Beispiele

Turing-Maschinen mit mehreren Bändern

Eine Turing-Maschine mit 2 Bändern

Turing-Maschinen können mehrere Bänder enthalten. Jedes Band ist in beide Richtungen in unendlich viele Zellen unterteilt. Jede Zelle kann genau ein Zeichen aus einem Eingabealphabet aufnehmen. Für jedes Band besitzt die Maschine einen Schreib-Lese-Kopf, der den Inhalt genau einer Zelle lesen kann. Die S/L-Köpfe sind mit dem Steuerwerk verbunden. Das Steuerwerk kann eine bestimmte Anzahl von Zuständen einnehmen. Die Arbeitsweise der Maschine ist durch eine endliche Liste von Befehlen festgelegt. Ein Befehl gibt an, was in einer gegebenen Situation ( aktueller Zustand, gelesenes Zeichen) die S/L-Köpfe tun sollen und welchen Folgezustand das Steuerwerk einnehmen soll. Die S/L-Köpfe können auf einen Befehl hin ein Zeichen schreiben und dann eine Bewegung des Typs R (rechts), L (links), N (keine Bewegung), S (keine Bewegung und Stop der Maschine) ausführen.
Ein Befehl für die Maschine aus obigem Bild könnte lauten :
( Z2 I b : I a LR Z5 )
Wenn im Zustand Z2 auf Band1 ein I gelesen wird und auf Band2 ein b, dann schreibe ein I auf Band1 und gehe nach links, schreibe ein a auf Band2 und gehe nach rechts. Nimm abschließend den Zustand Z5 ein.

Arbeitsweise einer deterministischen Turing-Maschine
Vor dem Start müssen die Bänder mit den nötigen Eingaben belegt und ein Anfangszustand eingestellt werden.
Startet man die Maschine, so führt sie das folgende Programm aus :
Wiederhole
   Lies die Zeichen unter den S/L-Köpfen.
   Suche einen Befehl, der zum aktuellen Zustand und den gelesenen Zeichen passt.
   Wenn ein passender Befehl gefunden wurde, so führe den Befehl aus.
bis kein Befehl gefunden wurde oder der letzte Befehl ein Stop 'S' als Bewegung hatte.

Nicht-deterministische Turing-Maschinen
Nicht-deterministische Turing-Maschinen können für eine Situation mehrere Befehle in der Befehlstafel haben Die Maschine wendet dann alle passenden Befehle an und erhält unterschiedliche Konfigurationen, die sie in den nächsten Schritten parallel verarbeitet. Wenn eine der erreichten Konfigurationen eine Endkonfiguration ist, hält die Maschine.
Turing-Werkstatt.exe kann nichtdeterministische Turing-Maschinen mit einem Band nur durch zusätzliche Maßnahmen simulieren.