Berechenbarkeit und Kreativität

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 wir eine Boolesche Antwort aus $\{0,1\}$ erwarten, wird die Antwort durch den Endzustand angegeben: der Zustand $\qaccept$ entspricht einer 1, der Zustand $\qreject$ entspricht einer 0. 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?

Definition(Turingmaschine). Eine Turingmaschine besteht aus folgenden Elementen:

Einem endlichen Eingabe-Alphabet $\Sigma$. Dies sind die Symbole, die für das Eingabewort in Frage kommen.
Einem endlichen Bandalphabet $\Gamma$; das sind die Symbole, die auf dem Band stehen dürfen. Offensichtlich muss $\Sigma \subseteq \Gamma$ gelten. Jede Zelle kann genau ein Zeichen aus $\Gamma$ enthalten. Darüberhinaus gibt es noch das sogenannte Blanksymbol $\square \in \Gamma \setminus \Sigma$. Dies zeigt an, dass die Zelle im Moment leer ist. Im obigen Beispiel ist die Zelle links vom ersten $a$ beispielsweise leer. Am Anfang steht auf dem Band also ein Eingabewort $w \in \Sigma^*$ und rechts und links davon unendlich viele $\square$-Symbole.
Einer endliche Menge $Q$ an inneren Zuständen. Dies entspricht in etwa den Prozessor-Registern eines Computers. Ein Zustand $\texttt{start} \in Q$ ist der Startzustand, in welchem sich die Maschine zu Beginn befindet.
Einer Zustandsübergangsfunktion $\delta$, die sagt, was die Turingmaschine tun soll, wenn Sie im Zustand $q$ ist und Zeichen $s$ liest. Formal: \begin{align*} \delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \lsr \ , \end{align*} wobei L für gehe eine Zelle nach links steht, R für rechts und S für stay, also die Anweisung, den Kopf nicht zu bewegen.
Zwei besonderen Zuständen $\qaccept$ und $\qreject$.

Für die Turingmaschine in dem obigen Beispiel haben wir zwei Regeln gesehen: \begin{align*} \delta(q_2, b) & = (q_3, a, \texttt{R}) \\ \delta(q_3, \#) & = (q_4, b, \texttt{L}) \end{align*}

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.

Definition

Die Konfiguration einer Turingmaschine ist ein Element in $\Gamma^* \times Q \times \Gamma^*$, also \begin{align*} C = u q v \end{align*} wobei $uv \in \Gamma^*$ der Bandinhalt ist, der Schreib-Lese-Kopf auf dem ersten Zeichen von $v$ steht und $q$ der innere Zustand der Turingmaschine ist. Das $q$ in $C$ kennzeichnet also sowohl die Position des Schreib-Lese-Kopfes auf dem Band sowie den inneren Zustand Die Menge aller Konfigurationen ist \begin{align*} \mathcal{C} := \Gamma^* \times Q \times \Gamma^* \end{align*} Der Zustand einer Konfiguration $C = uqv$ ist $q$, also der innere Zustand, in dem sich die Maschine gerade befindet. Wir bezeichnen mit $\state(C)$. Formal: \begin{align*} \state: \mathcal{C} & \rightarrow Q \\ uqv & \mapsto q \ . \end{align*} Eine Konfiguration $C$ ist eine akzeptierende Endkonfiguration wenn $\state(C) = \qaccept$ ist; eine ablehnende Endkonfiguration , wenn $\state(C) = \qreject$ ist. In beiden Fällen ist $C$ eine Endkonfiguration.

Wenn also das Eingabewort $w \in \Sigma^*$ und $\qstart$ der Startzustand ist, dann ist \begin{align*} C_{\rm start} = \qstart{} w \end{align*} die Startkonfiguration.

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

Definition (erweiterte Zustandsübergangsfunktion) Die erweiterte Zustandsübergangsfunktion einer Turingmaschine ist \begin{align*} \hat{\delta} : \mathcal{C} \rightarrow \mathcal{C} \ \end{align*} Sie beschreibt für eine Konfiguration $C$, welches die Konfiguration im nächsten Schritt ist. Per Konvention legen wir fest, dass $\hat{\delta}(C) = C$ gilt, wenn $C$ eine Endkonfiguration ist.

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 \begin{align*} \hat{\delta}(aaAq_2b\#ba) & = aaAaq_3\#ba \\ \hat{\delta}(aaAaq_3\#ba) & = aaAq_4abba \\ \hat{\delta}(abAq_2bba\#) & = abAaq_3ba\# \\ \end{align*} 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 \begin{align*} \hat{\delta}^{(i)} (C) := \underbrace{\hat{\delta}(\hat{\delta}(\dots (\hat{\delta}}_{i \textnormal{ mal}} (C) \dots))) \end{align*} 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: \begin{align*} \hat{\delta}^* (C) := \begin{cases} \hat{\delta}^{(i)} (C) & \textnormal{ wenn es ein $i$ gibt, so dass $\hat{\delta}^{(i)} (C)$ eine Endkonfiguration ist} \\ \texttt{undefined} & \textnormal{sonst.} \end{cases} \end{align*}

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: \begin{align*} \hat{M}(x) := \hat{\delta}^* (\qstart{} x_1 x_2 x_3 \dots x_n) \ . \end{align*} 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 oder reject ist. Wir definieren daher \begin{align*} f_M(x) = \begin{cases} 1 & \textnormal{ falls $\state(\hat{M}(x)) = \qaccept$, wenn also $\hat{M}(x)$ eine akzeptierende Endkonfiguration ist, }\\ 0 & \textnormal{ falls $\state(\hat{M}(x)) = \qreject$ ,}\\ \texttt{undefined} & \textnormal{ falls $\hat{M}(x) = \texttt{undefined}$ } \end{cases} \end{align*}

Der Bequemlichkeit halber werden wir oft $M(x)$ statt $f_M(x)$ schreiben. So wie wir ja auch für einen Schaltkreis $C$ nicht $f_C(x)$ sondern einfach $C(x)$ schreiben, um den Ausdruck "der Wert des Ausgabegatters von $C$ bei Eingabe $x$" zu notieren.

Definition (Turingmaschine entscheidet eine Sprache) Eine Turingmaschine $M$ entscheidet die Sprache $L \subseteq \Sigma^*$ wenn

$M(x) = 1$ für alle $x \in L$,
$M(x) = 0$ für alle $x \in \Sigma^* \setminus L$.

Insbesondere heißt das, dass $M$ auf jedem Eingabewort terminiert. Falls wir $L \subseteq \Sigma^*$ als Funktion $f: \Sigma^* \rightarrow \{0,1\}$ betrachten, dann besagt die Definition einfach, dass $M(x) = f(x)$ für alle $x \in \Sigma^*$ gilt.

Eine Sprache $L$ heißt entscheidbar, wenn es eine Turingmaschine gibt, die sie entscheidet.

Definition (Turingmaschine akzeptiert eine Sprache) Eine Turingmaschine $M$ akzeptiert die Sprache $L \subseteq \Sigma^*$ wenn \begin{align*} x \in L \Longleftrightarrow M(x) = 1 \end{align*} für alle $x \in \Sigma^*$ gilt. Das heißt, dass $M$ für $x \not \in \Sigma^*$ entweder irgendwann den Endzustand $\qreject$ erreicht oder nie einen Endzustand erreicht.

Eine Sprache $L \subseteq \Sigma^*$ heißt semi-entscheidbar, wenn es eine Turingmaschine $M$ gibt, die $L$ akzeptiert.

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.

Definition (Turingmaschine berechnet eine Funktion) Seien $\Sigma_1, \Sigma_2$ zwei endliche Alphabete und \begin{align*} g : \Sigma_1^* \rightarrow \Sigma_2^* \end{align*} eine Funktion. Eine Turingmaschine $M$ berechnet die Funktion $g$, wenn

$\Sigma_1$ das Eingabealphabet von $M$ ist,
$\Sigma_1 \cup \Sigma_2 \subseteq \Gamma$ gilt und $\square \in \Gamma \setminus (\Sigma_1 \cup \Sigma_2)$; das Blank-Symbol ist also weder Teil das Eingabealphabets noch des Ausgabealphabets.
$M$ terminiert für jedes $x \in \Sigma^*$.
In der Endkonfiguration $\hat{M}(x)$ steht auf dem Arbeitsband das Wort $g(x) \in \Sigma_2^*$ und der Kopf steht ganz links, also $\hat{M}(x) = \qaccept{} g(x)$.

Beispiele

Wir betrachten die Sprache über $\Sigma = \{0,1,c\}$ mit

\begin{align*} L := \{ wcw \ | \ w \in \{0,1\}^*\} \end{align*}

die also zum Beispiel $0100c0100$ enthält, aber nicht $0100c010$. Wir beschreiben eine Turingmaschine, die $L$ entscheidet.

Lies das aktuelle Zeichen und speichere es (im Zustand). Markiere es als gelesen, also ersetze es durch ein $X$.
Geh nach rechts, bis Du $c$ liest.
Finde das erste Zeichen in $\{0,1\}$, vergleiche es mit dem gespeicherten. Wenn ungleich, lehne ab; wenn gleich, markiere es als gelesen (ersetze es durch ein $Y$).
Gehe wieder zurück bis zum ersten $X$, dann eins nach rechts.
Fange nun wieder bei Schritt 1 an. Falls das aktuelle Zeichen $c$ ist, haben wir das Wort links von $c$ zu Ende gelesen.
Überprüfe nun, ob rechts vom $c$ alles weg ist, also nur noch $Y$ stehen bis zum ersten $\Box$.

Auf der Webseite turingmachinesimulator.com können Sie Ihre Turingmaschine eingeben und simulieren. Den Text für die gerade beschriebene finden in word-c-word.txt. Generell können Sie Regeln der Form \begin{align*} \delta(q,a) = (r, b, D) \end{align*} auf turingmachinesimulator.com als

q, a 
r, b, D

angeben, wobei die Richtung $D$ mit den Symbolen <, -, > codiert wird.