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.

Visier mich an!Illustration bekommen

Schematischer Aufbau einer Turingmaschine.

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:

Übergangsfunktion für deterministische Turingmaschinen:2\[\delta: Z \times \Gamma \rightarrow Z \times \Gamma \times \{L, N, R\}\]

Übergangsfunktion für nichtdeterministische Turingmaschinen:3\[\delta: Z \times \Gamma \rightarrow \mathbb{P}(Z \times \Gamma \times \{L, N, R\})\]

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).

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:

Übergangsrelation \(\delta \) bei nichtdeterministischen Turingmaschinen\[ \delta: Z \times \Gamma^k \rightarrow Z \times \Gamma^k \times \{L, R, N\}^k \]

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.