Turingmaschine (TM)
Eine Turingmaschine besteht aus einem Arbeitsband, auf welchem Symbole durch einen Schreib- und Lesekopf (kurz: SL-Kopf genannt) gelesen und nach festen Regeln geschrieben werden. Diese Regeln nennen wir Übergangsregeln.
Man unterscheidet zwischen deterministischen und nicht-deterministischen Turingmaschinen. Letztere ist nicht mehr eindeutig festgelegt, sodass es mehrere Möglichkeiten für potentielle Übergänge gibt (siehe unten). Wir wollen uns zunächst auf deterministische Turingmaschinen beschränken.
Das Konzept wird hier nur theoretisch behandelt. Es kann auch in der Praxis nachgebaut werden. Mittlerweile gibt es jedoch weitaus effizientere Möglichkeiten zur Realisierung von Computern.
Aufbau einer Turingmaschine
Im Folgenden ist der schematische Aufbau einer Turingmaschine dargestellt. Die einzelnen Komponenten werden weiter unten einzeln erläutert.
Arbeitsband
Das Arbeitsband kann man sich als eine unendliche Aneinanderreihung von sogenannten Zellen vorstellen. Eine Zelle ist dabei eine Box, in die man einen Buchstaben schreiben und wieder auslesen kann. Ist die Zelle leer, schreibt man ein sogenanntes Blank-Symbol (oft auch leeres Symbol oder Leerzeichen genannt): \(\square\).
Auf das Arbeitsband wird i.d.R. ein Wort (Aneinanderreihung von Zeichen) eingelesen, welches mit Hilfe der Übergangsregeln bearbeitet wird.
Schreib- und Lesekopf
Der Schreib- und Lesekopf zeigt zu jeder Zeit auf genau eine Zelle des Arbeitsbands. Er kann das in dieser Zelle befindliche Zeichen lesen und entsprechend bestimmten Regeln wieder beschreiben.
Außerdem ist er in der Lage, Kopfbewegungen durchzuführen. Er kann sich entweder nach rechts (R), nach links (L) oder gar nicht (N, neutral) bewegen.
Zustand
Eine Turingmaschine befindet sich stets in einem bestimmten Zustand. Dieser Zustand kann sich ändern, während die Maschine ausgeführt wird. Der Startzustand muss jedoch stets angegeben werden.
Übergangsfunktion
Die Übergangsfunktion sucht sich aus einer Liste von möglichen Übergängen den passenden heraus und führt ihn aus. An dieser Stelle sei erwähnt, dass es bei nicht-deterministischen Turingmaschinen statt einer Übergangsfunktion eine sogenannte Übergangsrelation gibt.
Einen Übergang kann man sich als Vorschrift vorstellen. Ausgehend vom aktuellen Zustand des Systems sowie dem aktuell gelesenen Zeichen wird in einen Zustand übergegangen, sowie ein neues Zeichen geschrieben (der Zustand und oder das Zeichen können dabei jedoch auch dasselbe bleiben). Anschließend wird noch eine Kopfbewegung (L, N, R) ausgeführt.
Formale Definition einer Turingmaschine
Eine Turingmaschine ist ein Tupel der Form:1\[ TM = (Z, \Sigma, \Gamma, \delta, z_0, \square, E) \](Die Reihenfolge kann je nach Konvention leicht abweichen)Die einzelnen Komponenten in 1
sind:
- Zustandsmenge \(Z\) - in der Menge kann jeder Zustand gefunden werden, den das System potenziell annehmen kann.
- Eingabealphabet \(\Sigma\) - darunter versteht man all jene Zeichen, welche als Eingaben auf das Arbeitsband geschrieben werden können exklusive den Arbeitssymbolen wie dem Blank.
- Arbeitsalphabet \(\Gamma\) - besteht aus dem Eingabealphabet sowie dem Blank Symbol. Oft sind auch Symbole wie # vertreten, welche zur Trennung genutzt werden. Somit umfasst es alle Zeichen, welche jemals auf eine Zelle des Arbeitsbands geschrieben werden können. In der Mengenlehre schreibt man dies wie folgt: \(\Sigma \subset \Gamma\).
- Startzustand \(z_0\) - bezeichnet denjenigen Zustand, welcher zu Beginn eingenommen wird, mit \(z_0 \in Z\).
- Blank-Symbol \(\square\) - ist dasjenige Symbol, welches in jeder Zelle steht, sofern kein anders Zeichen dort zu finden ist. In der Informatik sagt man, dass jede Zelle mit dem Blank Symbol initialisiert wird.
- Menge der Endzustände \(E\) - ist eine Teilmenge der Zustandsmenge: \(E \subseteq Z\). Sie bezeichnet jene Zustände, bei denen sich das System in einem sogenannten akzeptierenden Zustand befindet. Werden keine weiteren Übergänge gefunden und das System befindet sich in einem Endzustand, so wird das eingelesene Wort akzeptiert.
Übergangsfunktion
Die Übergangsfunktion führt, wie oben bereits beschrieben Übergänge aus. Es wird dabei zwischen deterministischen und nicht-deterministischen Turingmaschinen unterschieden. Formal schreibt man dabei:Im Gegensatz zu deterministischen Turingmaschinen ist bei nichtdeterministischen Turingmaschinen nicht nur ein Verlauf möglich. Ausgehend von der aktuellen Konfiguration der Maschine sind mittels der Übergangsrelation nun mehrere mögliche Abläufe möglich. Der Ablauf ist nun nicht mehr deterministisch (festgelegt).
Erklärungen:
- \(Z = \{z_a, z_1, z_e\}\) bezeichnet die Menge aller Zustände die das System annehmen kann.
- \(\Sigma = \{a, b\}\) ist das Eingabealphabet. Es können somit nur die Zeichen \(a\) und \(b\) auf das Arbeitsband eingelesen werden.
- \(\Gamma = \{a, b, \#, \square\}\) ist das Arbeitsalphabet. Es ist die Erweiterung des Eingabealphabets durch das Trennzeichen \(\#\) sowie das leere Symbol \(\square\).
- Übergangsfunktion \(\delta\):\[ z_a a \rightarrow z_1 b R \\ z_a b \rightarrow z_1 a R \\ z_1 a \rightarrow z_1 b R \\ z_1 b \rightarrow z_1 a R \\ z_1 \# \rightarrow z_e \# N \\ z_a \# \rightarrow z_e \# N \\ \]
- \(z_a\) bezeichnet den Anfangszustand, also jenen, in dem sich das System zu Beginn befindet.
- \(\square\) ist auch hier das leere Symbol. Es ist theoretisch denkbar, hierfür auch ein anderes Symbol zu notieren, daher muss es in der Definition auftauchen.
- \(E = \{z_e\}\) ist die Menge der Endzustände. Hierbei ist nur der Zustand \(z_e\) ein Endzustand. Da grundsätzlich mehrere Zustände mögliche Endzustände sind, wird hier eine Menge angegeben.
Zustandsdiagramm der Turingmaschine
Die Turingmaschine kann im Rahmen der sogenannten Automatentheorie auch als Diagramm dargestellt. Dabei sind die möglichen Übergänge in jedem Zustand mit Pfeilen gekennzeichnet.
Syntax: gelesenes Zeichen; geschriebenes Zeichen; Kopfbewegung
Ausblick
Formale Sprachen
In der theoretischen Informatik werden die Begriffe der Grammatik und Sprache formal definiert. Dabei nimmt man eine von Noam Chomsky formulierte Hierarchie als Grundlage. Diese besteht aus vier verschiedenen Klassen von Grammatiken, welche je eine Sprache erzeugen. Turingmaschinen beschreiben die allgemeinste der vier Klassen, die Typ 0 Sprachen.Definition
Eine Sprache \(L\) ist vom Typ 0 genau dann, wenn es eine Turingmaschine \(M\) gibt mit \(L(M)\).Definition: akzeptieren einen Worts
Ein Wort \(w\) wird akzeptiert, wenn sich die Turingmaschine \(M\) nach dem Lesen des letzten Zeichens in einem Endzustand befindet. Dann befindet sich das Wort in der von der M erzeugten Sprache und man schreibt: \(w \in L(M)\)
Mehrbandmaschinen
Das Konzept der Turingmaschine kann auch auf beliebig viele Bänder (Anzahl k) erweitert werden. Dabei befindet sich auf jedem der k Bänder ein eigener Kopf. Übergänge der Mehrband-Turingmaschine hängen somit nicht nur von dem aktuellen Zustand ab, sondern auch von den gelesenen Zeichen auf den k Bändern ab. Die Übergangsfunktion ändert sich zu:
Zu jeder k-Band-Turingmaschine \(M\) lässt sich eine 1-Band-Turingmaschine \(M'\) konstruieren, sodass gilt: \(L(M) = L(M')\). Dies bedeutet, dass beide Maschinen dieselbe Sprache akzeptieren.
Berechenbarkeit
Turingmaschinen spielen auch bei der Prüfung der Berechenbarkeit einer Funktion eine fundamentale Rolle. Eine Funktion \(f\) gilt als berechenbar, sofern es einen Algorithmus gibt, der f berechnet, also nach endlich vielen Schritten mithält.
