Bestandteile und Arbeitsweise
Wir haben gesehen, dass ein Endlicher Automat in seiner Leistungsfähigkeit beschränkt ist. Dies ist darauf zurückzuführen, dass er sich Zwischenergebnisse bei seiner Arbeit nur in seinen Zuständen speichern kann. Deren Anzahl ist endlich. Der Automat hat also nur eine endliche „Merkfähigkeit“.
Ein Kellerautomat erweitert das „Gedächtnis“ nur in der Art und Weise, dass das letzte abgelegte Zeichen auf einem theoretisch unendlich großen Kellerspeicher gelesen werden kann. Damit konnten nun auch kontextfreie Grammatiken bearbeitet werden. Allerdings haben wir Grammatiken kennengelernt, deren produzierte Worte auch von Kellerautomaten nicht erkannt werden konnten.
Um Automaten, die kontextsensitive Grammatiken bearbeiten können, zu erstellen, erweitert man den Kellerautomaten um einen weiteren Stack. Verschmilzt man diese beiden Stacks an ihrem Kellerboden, so erhält man ein nach beiden Seiten unbegrenztes Arbeitsband, auf dem ein Lese-/Schreibkopf nach links und nach rechts bewegt werden kann. Dieses Arbeitsband ist in jedem Feld beschriftet, zumindest mit einem Leerzeichen. Die Maschine befindet sich zu jedem Zeitpunkt in in genau einem von endlich vielen Zuständen.
Ein Arbeitsschritt besteht aus Folgendem: In Abhängigkeit vom aktuellen Zustand z und dem Zeichen, welches der LS-Kopf gerade liest (Eingabezeichen), beschriftet sie das Arbeitsfeld mit einem Zeichen (Ausgabezeichen). Anschließend vollzieht sie eine Kopfbewegung, d. h. sie bewegt sich ein Feld nach links oder nach rechts (oder hält an) und geht in einen neuen Zustand über. Zur Beschreibung der Arbeitsweise ist eine Funktion erforderlich, die einem Paar (Zustand, gelesenes Zeichen) als Arbeitsvorschrift ein Tripel (zu schreibendes Zeichen, Bewegung des Lese-/Schreibkopfs, Folgezustand) zuordnet.
Definition einer Turingmaschine
Wir definieren das Modell der Turingmaschine, das von Alan M. Turing (engl. Logiker und Mathematiker; 1912 – 1954) im Jahr 1936 entworfen wurde und nach ihm benannt ist:
Definition: Turingmaschine
Eine Turing-Maschine ist ein 7-Tupel: T = (X,B,Z,\delta,b,z_0,Z_E), wobei gilt:
– X ist eine nichtleere, endliche Menge, das Eingabealphabet,
– B \supset Xist eine nichtleere, endliche Menge, das Bandalphabet,
– Z ist eine nichtleere, endliche Menge, die Zustandsmenge,
– \delta : (Z \setminus Z_E) \times B \to \{ L,R,N \} \times Z ist eine Funktion, die Überführungsfunktion, welche jedem Paar (Zustand, gelesenes Zeichen) ein Tripel (zu schreibendes Zeichen, Kopfbewegung, Folgezustand) zuordnet,
– b ist das Leerzeichen (oder Bandvorbelegungszeichen) mit b \in B \setminus X,
– ist der Anfangszustand,
– ist die Menge der Endzustände.
Hinweis: B enthält zumindest ein Zeichen mehr als X, nämlich das Leerzeichen b. Sicher können sich noch beliebig viele weitere Zeichen auf dem Band befinden (, die nichts mit der zu konstruierenden Turingmaschine zu tun haben), aber es interessieren nur die für die Turingmaschine notwendigen Zeichen.
Turing-Emulation am Rechner
Die Turing-Maschine selbst ist eine unendlich mächtige Maschine. Da jedoch die Turing-Maschine normalerweise auf dem Rechner emuliert wird, treten physikalische Begrenzungen auf. Diese physikalische Begrenzung kann jedoch während der Implementierung ignoriert werden. (Siehe Beispiel: Suche eines Zeichens auf dem Band)
Darstellung von Turingmaschinen
Eine Turingmaschine kann ähnlich wie Endliche Automaten und Kellerautomaten dargestellt werden. Betrachten wir die Turingmaschine T = (X,B,Z,\delta,b,z_0,Z_E) mit dem Eingabealphabet X = {0, 1}, dem Bandalphabet B = {0, 1, #}, der Zustandsmenge Z = {z0, z1, z2}, dem Leerzeichen *, dem Anfangszustand z0 und der Endzustandsmenge ZE = {z2}. Die Überführungsfunktion \delta soll hier auf drei verschiedene Arten dargestellt werden: als Tabelle, als Tafel und als Graph.
Tabelle
Hierbei sind in der linken Spalte alle Zustände eingetragen, die nicht Endzustände sind, in der obersten Zeile alle Zeichen des Bandalphabets. Die Tabelleneinträge selbst geben für den betreffenden Zustand und das gerade gelesene Bandzeichen als Arbeitsvorschrift das zu schreibende Zeichen, die Kopfbewegung des Lese-/Schreibkopfs und den Folgezustand in Form eines Tripels an.
Tafel
Hierbei wird die Überführungsfunktion als Folge von 5 Tupeln angegeben mit der Reihenfolge (Zustand, gelesenes Zeichen, zu schreibendes Zeichen, Kopfbewegung und Folgezustand).
z0 0 0 R z0
z0 1 1 R z0
z0 # # L z1
z1 0 1 N z2
z1 1 0 L z1
z1 # 1 N z2Graph
Hier sind die Zustände als Kreise dargestellt, der Anfangszustand ist durch einen hinführenden Pfeil gekennzeichnet, der Endzustand durch einen Doppelkreis. Die Zustandsübergänge sind als Pfeile dargestellt und beschriftet mit dem Tripel, bestehend aus gelesenem Zeichen, zu schreibendem Zeichen und Kopfbewegung.
Was macht eigentlich diese Turingmaschine?
… ein Grund mal darüber nachzudenken …
Beispiele
Addierer
Wir wollen einen Addierer mit einer Turingmaschine erstellen, der ein Eingabeband der Form
...###||||||+|||###...abarbeiten kann. Dabei steht ein | für eine eins, || für eine zwei, usw. Der Zustandsgraph sieht dann so aus:
Kopierer
Die Eingabezeichen (nur |) sollen auf einen hinteren Bereich auf dem Band kopiert werden:
...###|||||||###########...
->
...###|||||||#|||||||###...Realisierung in einen Turing-Simulator eingeben und dessen Korrektheit überprüfen (Tabelle):
