Home -> Themen -> Turing-Maschine
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.
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.