Eine Turingmaschine besteht aus einem Band, das in Zellen unterteilt ist und in beide Richtungen unbegrenzt ist, und einem Schreib-Lese-Kopf. Dieser befindet sich in jedem Schritt auf einer Zelle. Wie auch der endliche Automat oder der Kellerautomat hat die Turingmaschine einen internen Zustand. In jedem Schritt liest die Maschine das Zeichen, das sich in der aktuellen Zelle des Bandes befindet (dort, wo der Kopf steht). Abhängig vom gelesenen Zeichen $s$ und dem internen Zustand $q$ schreibt die Turingmaschine ein neues Symbol $s'$ in die Zelle, wechselt in einen neuen Zustand $q'$ und bewegt den Kopf um maximal eine Zelle, also nach link, rechts, oder gar nicht.

Sie können sich das Band auch als Magnetband vorstellen, das nach vorn oder nach hinten gespult wird, anstatt dass der Kopf sich bewegt. Am Anfang steht auf dem Band das Eingabewort und der Kopf auf dem ersten Symbol dieses Wortes. Die Turingmaschine wendet nun ihre Regeln an, bis Sie einen Endzustand erreicht. Bei Entscheidungsproblemen, wo uns nur eine Ja/Nein-Antwort interessiert, wird die Antwort durch den Entzustand angegeben: der Zustand $\qaccept$ entspricht einem Ja, der Zustand $\qreject$ entspricht einem Nein. Diese zwei Endzustände reichen im Allgemeinen aus. Wenn wir von der Maschine eine komplexere Ausgabe als Ja/Nein erwarten, so betrachten wir als Ausgabe der Turingmaschine den Inhalt des Bandes zu dem Zeitpunkt, da die Maschine den Zustand $\qaccept$ erreicht. Was brauchen wir also, um so eine Turingmaschine und ihre Arbeitsweise zu beschreiben?

Für die Turingmaschine in dem obigen Beispiel haben wir zwei Regeln gesehen:

Was macht eine Turingmaschine?

Sie haben nun wohl bereits eine vage Vorstellung, was eine Turingmaschine macht. Versuchen wir, es noch weiter zu formalisieren. Um den Gesamtzustand der Turingmaschine zu beschreiben, also eine vollständige Momentaufnahme, reicht nicht der aktuelle innere Zustand $q$; wir brauchen auch den Bandinhalt und insbesondere die Position, an der sich der Kopf befindet. Das alles zusammen nennt man die Konfiguration der Turingmaschine. Wir wollen sie mit uns bereits bekannten mathematischen Begriffen beschreiben.

Wenn also das Eingabewort $w \in \Sigma^*$ und $\qstart$ der Startzustand ist, dann ist

die Startkonfiguration.

Die Rolle des $\square$-Symbols. Das Band der Turingmaschine ist ja unendlich. Um eine Momentaufnahme dennoch als endliches Objekt beschreiben zu können, lassen wir die $\square$ -Symbole links und rechts vom "eigentlichen" Bandinhalt weg. Bei einer Konfiguration $uqv$ stehen also links vom $u$ und rechts vom $v$ unendlich viele $\square$ -Symbole auf dem Band. Nach der formalen Definition $uqv \in \Gamma^* \times Q \times \Gamma^*$ ist es nicht verboten, dass $u$ auch mit einem $\square$-Symbol beginnt oder $v$ mit einem aufhört. Allerdings wären die Konfiguration $\square u q v$ und $u q v \square$ genauso gut mit $u q v$ beschrieben. Wir können uns also auf die Konvention einigen, dass $\square$ nie am Rande einer Konfiguration $uqv$ steht. Beachten Sie auch, dass die Zellen nicht "numeriert" sind. Die beiden folgenden Momentaufnahmen

können also beide mit der Konfiguration $aAAaq\#ba$ beschrieben werden, obwohl die Zellen nun andere Inhalte haben, weil die Turingmaschine es irgendwie geschafft hat, den ganzen Bandinhalt um eins nach rechts zu kopieren. Es sollte klar sein, dass die Turingmaschine keine Möglichkeit hat, die obere von der unteren Situation zu unterscheiden, und dass es somit nur recht und billig ist, beide als eine identische Konfiguration aufzufassen. All diese Schwierigkeiten verschwinden, wenn wir uns den Speicher einer Turingmaschine nicht als unendliches Band vorstellen, sondern als zwei Stapel, einer links vom Kopf und einer rechts vom Kopf. Allerdings hat sich die Vorstellung vom Band irgendwie als Standard durchgesetzt. Hier sehen Sie die gleiche Konfiguration in dem Modell mit zwei Stapeln:

Alternativ können wir auch der Turingmaschine verbieten, das Blank-Symbol $\Box$ jemals zu schreiben. Dann wäre also $\delta: Q \times \Gamma \rightarrow Q \times (\Gamma \setminus \{\Box\}) \times \lsr$. All diese Betrachtungsweisen unterscheiden sich nicht wesentlich. Wir bleiben bei unserem "alten" $\delta$, erlauben also, $\Box$ zu schreiben, und leben damit, dass $uqv$ und $\Box \Box u q v \Box$ formal zwei verschiedene Konfigurationen sind, auch wenn beide irgendwie das selbe beschreiben.

Formal definiert $\delta$ nun auch eine Funktion auf der Menge der Konfigurationen:

Unsere obige Turingmaschine hat beispielsweise die Regeln $\delta(q_2,b) = (q_3, a,R)$ und $\delta(q_3, \#) = (q_4, b, \texttt{L})$, und somit würden

gelten. Sie sehen: Die Definition von $\hat{\delta}$ ist nichts wirklich Tiefgründiges, sondern einfach eine Implementierung der Turingmaschinen-Momentaufnahme mit uns bereits geläufigen mathematischen "Datenstrukturen" (hier: der Menge $\Gamma^* \times Q \times \Gamma^*$). Stellen Sie sich einfach vor, Sie müssten eine Turingmaschine in Java implementieren. Dann würden Sie es wahrscheilich irgendwie so ähnlich machen.

Ausgabekonfiguration einer Turingmaschine

Die Funktion $\hat{\delta}$ bildet aus einer Konfiguration die Folgekonfiguration. Wir definieren nun

also die Konfiguration, die die Turingmaschine nach $i$ Rechenschritten erreicht hat. Weiterhin definieren wir $\hat{\delta}^* (C)$ als die Endkonfiguration, die bei wiederholter Anwendung von $\hat{\delta}$ schlussendlich erreicht wird. Hier taucht ein Problem auf: es ist nicht gesagt, dass die Turingmaschine, von Konfiguration $C$ beginnend, überhaupt irgendwann in einer Endkonfiguration landen wird. Daher kann $\hat{\delta}^*$ auch undefined sein:

Nochmal zur Verdeutlichung: wenn $\delta^{(i)}(C)$ eine Endkonfiguration ist, dann ist auch $\delta^{(j)}(C)$ eine, für jedes $j \geq i$, weil wir $\hat{\delta}(C') = C'$ für jede Endkonfiguration $C'$ definiert haben. Es spielt also in der obigen Formulierung wenn es ein $i$ gibt keine Rolle, welches solche $i$ wir wählen. Für ein Eingabewort $x \in \Sigma^*$ können wir nun das Ergebnis der Berechnung von Turingmaschine $M$ auf $x = x_1 \dots x_n$ definieren:

Wir beginnen also mit der Startkonfiguration und lassen die Turingmaschine dann laufen, bis sie einen Endzustand erreicht. Die erreichte Konfiguration bezeichnen wir mit $\hat{M}(x)$. Falls nie ein Endzustand erreicht wird (die Turingmaschine also endlos läuft), ist $\hat{M}(x)$ undefined.

Sprachen entscheiden

Ein Entscheidungsproblem ist eine Funktion $P : \Sigma^* \rightarrow \{\texttt{true}, \texttt{false}\}$, beispielsweise: gegeben ein Wort, stellt dieses Wort ein korrektes Java-Programm dar? oder gegeben eine Zahl in Dezimalschreibweise, ist dies eine Primzahl? Eine äquivalente Sichtweise ist die eines Entscheidungsproblems als Sprache $L \subseteq \Sigma^*$. Wir identifizieren $L$ hier mit der Menge aller Wörter $x$ mit $P(x) = \texttt{true}$. Wenn wir es mit einem Entscheidungsproblem zu tun haben und dieses mit einer Turingmaschine lösen wollen, so interessiert uns am Endergebnis $\hat{M}(x)$ (also der erreichten Endkonfiguration) nicht der Bandinhalt, sondern nur, ob der Zustand accept oderreject ist. Wir definieren daher

In beiden Definition verlangen wir natürlich, dass $\Sigma$ das Eingabealphabet der Turingmaschine ist.

Funktionen berechnen

Oft wollen wir nicht nur eine Sprache $L \subseteq \Sigma^*$ entscheiden, sondern eine Funktion $g: \Sigma_1^* \rightarrow \Sigma_2^*$ berechnen. Mit einer Turingmaschine heißt das einfach, dass bei Eingabe $x \in \Sigma_1^*$ die Turingmaschine in einer akzeptierenden Endkonfiguration $C$ landet, und in $C$ steht dann $g(x)$ auf dem Band. Formal müssen wir noch klären, was $g(x)$ steht auf dem Band bedeutet.

Turingmaschinen und formale Grammatiken