4.6 Turingmaschinen, Haltproblem und Unentscheidbarkeit

Im vorherigen Teilkapitel haben wir die universelle Turingmaschine $U$ konstruiert, die eine andere Turingmaschine, deren Codierung und Inputwort sie als Input gegeben hat, simulieren kann. Technisch gesprochen: $U$ akzeptiert die Sprache

\begin{align} \{ c w \ | \ c = \enc(M) \textnormal{ und $M$ akzeptiert $w$} \} \ . \label{halting-language-old-encoding} \end{align}

Allerdings: wenn $M$ auf $x$ nicht terminiert, dann terminiert $U$ auf $\enc(M)x$ auch nicht. $U$ akzeptiert die Sprache also, entscheidet sie aber nicht. Wäre es nicht schön, eine Turingmaschine zu haben, die diese Sprache entscheidet? Dann könnten wir jede Turingmaschine simulieren und gleichzeitig Endlosschleifen und eventuell ganz allgemein "Programmierfehler" vorhersagen und abfangen. Wir werden zeigen, dass dies leider nicht möglich ist. In der Literatur ist dies als die Unentscheidbarkeit des Halteproblems (englisch undecidability of the Halting problem bekannt).

Als vorbereitenden Schritt schauen wir uns kurz die Codierungsfunktion nochmal genauer an. Wir bezeichnen mit $\tm_{\Sigma}$ die Menge aller Turingmaschinen mit Inputalphabet $\Sigma$. Wir hatten die Codierungsfunktion $\enc: \tm_{\Sigma} \rightarrow \Lambda^*$ definiert, für das Codierungsalphabet $\Lambda := \writelambda$. In diesem Teilkapitel wird es nötig sein, die Turingmaschine über dem Alphabet $\Sigma$ selbst zu codieren. Dies ist nicht besonders schwierig, solange $\Sigma$ mindestens zwei Zeichen hat. Wenn z.B. $\Sigma$ die Zeichen $0$ und $1$ enthält, dann können wir alle Zeichen in $\Lambda$ wiederum als Strings in $\Sigma^*$ codieren. Wir müssen hier nur vorsichtig sein, dass der Code präfixfrei ist. Wenn wir zum Beispiel naiv $1$ als $1$ und $0$ als $0$ und $\texttt{#}$ als $01$ codieren, dann wissen wir nicht mehr, was mit dem Codewort $01$ gemeint ist. Am einfachsten geht das mit einem Blockcode, in dem alle Codewörter die gleiche Länge $k$ haben, also $\Lambda \rightarrow \{0,1\}^k$. Mit $k = \ceil{\log_2 |\Lambda|}$ ist das kein Problem. Unsere "neue" Codierungsfunktion $\enc$ ist nun also $\enc: \tm_{\Sigma} \rightarrow \Sigma^*$. Wir definieren nun die Haltesprache $\halt \in \Sigma^*$:

\begin{align*} \halt := \{ \enc(M) w \ | \ w \in \Sigma^* \textnormal{ und } M \textnormal{ akzeptiert } w\} \ . \end{align*}

Da $\enc$ präfixfrei ist, können wir erkennen, wo $\enc(\texttt{;})$ steht, wo also $\enc(M)$ aufhört und $w$ beginnt. Wir können die universelle Turingmaschine $U$ leicht abwandeln, dass sie $\halt$ akzeptiert; wir müssen nur einen Decodierungsschritt vorausschicken, der die neue Codierung $\enc(M) \in \Sigma^*$ in unsere "alte" in $\Lambda^*$ übersetzt.

Wir zeigen nun, dass $\halt$ unentscheidbar ist, dass es also keine Möglichkeit gibt, das Nichtterminieren einer Maschine $M$ auf Eingabe $x$ vorauszusehen und abzufangen.

Theorem (Unentscheidbarkeit des Halteproblems). Die Sprache $\halt$ ist unentscheidbar.

Ich gebe erst einmal einen kurzen und knappen Widerspruchsbeweis. Falls das ihnen zu schnell ging, lesen Sie den zweiten Beweis, in dem ich mir mehr Zeit nehme.

Kurzer Beweis per Wiederspruch. Nehmen wir an, es gäbe eine Maschine $H$, die $\halt$ entscheidet. Dann wäre auch die Sprache

\begin{align*} \diag := \{\enc(M) \ | \ \textnormal{$M$ akzeptiert $\enc(M)$} \} \end{align*}

entscheidbar. Warum? Wir können einfach schauen, ob das Eingabewort $c$ die Form $\enc(M)$ hat und in diesem Fall das Wort $\enc(M) \enc(M)$ der Maschine $H$ übergeben. Die Sprache $\diag$ ist, salopp ausgedrückt, die Menge aller Turingmaschinen, die ihre eigene Codierung als Inputwort akzeptieren. Ebenso wäre auch

\begin{align*} \negdiag := \{\enc(M) \ | \ \textnormal{$M$ akzeptiert $\enc(M)$ nicht}\} \end{align*}

entscheidbar; wir müssen ja nur $\diag$ entscheiden und dann das Ergebnis negieren. $\negdiag$ ist sozusagen die Menge aller Turingmaschinen, die nicht ihre eigene Codierung als Inputwort akzeptieren. Da $\negdiag$ nach Annahme entscheidbar ist, gibt es eine Maschine $D$, die $\negdiag$ entscheidet.

Wir fragen uns jetzt: gehört $\enc(D)$ selbst zu $\negdiag$?

\begin{align*} \enc(D) \in \negdiag & \Longleftrightarrow \textnormal{$D$ akzeptiert $\enc(D)$ nicht} \tag{nach Definition von $\negdiag$} \\ & \Longleftrightarrow \textnormal{$\enc(D) \not \in L(D)$} \tag{Bedeutung der Notation $L(D)$} \\ & \Longleftrightarrow \enc(D) \not \in \negdiag \tag{nach Annahme $L(D) = \negdiag$} \end{align*}

Also $\enc(D) \in \negdiag \Longleftrightarrow \enc(M) \not \in \negdiag$, ein Widerspruch. Unsere Annahme, dass $\halt$ entscheidbar sei, ist also falsch. $\square$

Ausführlicher Beweis. Ich finde Beweise durch Widerspruch immer etwas unintuitiv, weil man die ganze Zeit im Konjunktiv argumentieren muss. Daher hier ein Beweis ohne Widerspruch. Wir zeigen, dass $\halt$ unentscheidbar ist, indem wir für eine beliebige Turingmaschine $M$ zeigen, dass sie $\halt$ nicht entscheidet, indem wir nämlich ein Eingabewort $z \in \Sigma^*$ konstruieren, auf dem $M$ scheitert, also entweder

$f_H(z) = \texttt{accept}$ aber $z \not \in \halt$, oder
$f_H(z) = \texttt{reject}$ aber $z \in \halt$ , oder
$f_H(z) = \texttt{undefined}$, d.h. $H$ terminiert auf Eingabewort $z$ nicht.

Wir setzen nun $y := \enc(D)$ und $z := yy$, wobei $D$ eine neue Turingmaschine ist, die wir auf Basis von $H$ konstruieren werden. Also noch einmal. Für eine beliebige, uns gegebene Turingmaschine $H$, werden wir eine neue Turingmaschine $D$ bauen und sie codieren als $y := \enc(D)$, so dass entweder

$f_H(yy) = \texttt{accept}$ aber $yy \not \in \halt$, oder
$f_H(yy) = \texttt{reject}$ aber $yy \in \halt$, oder
$f_H(yy) = \texttt{undefined}$.

Wenn uns dies gelingt, so haben wir gezeigt, dass $H$ nicht die Sprache $\halt$ entscheidet: im Fall 3 terminiert $H$ ja nicht einmal; in Fall 1 und 2 liefert $H$ zwar eine Antwort, aber die falsche. Der Code für $D$ ist sehr einfach:

def D(x):
    if H(xx) == accept then 
        reject 
    else 
        accept

Zur Erinnerung: $y := \enc(D)$. Wir unterscheiden drei Fälle.

$H(yy) = \texttt{reject}$. Dann geht der Aufruf von $D(y)$ also in den else-Teil in den Zeilen 4-5 und $D(y) = \texttt{accept}$, somit $yy = \enc(D)y \in \halt$ Wir befinden uns in Fall 1: $y y \in \halt$ aber $H(yy)= \texttt{reject}$. Die Maschine $H$ hat eine falsche Antwort für $\halt$ geliefert.
$H(yy) = \texttt{accept}$. Dann geht der Aufruf von $D(y)$ in Zeile 3, und $D(y) = \texttt{reject}$, somit $yy = \enc(D) y \not \in \halt$. Wir befinden uns in Fall 2: $yy \not \in \halt$ und $H(yy) = \texttt{accept}$. Die Maschine $H$ hat abermals eine falsche Antwort geliefert.
$H(yy)$ terminiert nicht. Dann befinden wir uns in Fall 3: $H$ kann $\halt$ nicht entscheiden, denn Mindestbedingung hierfür wäre ja, auf jedem Eingabewort zu terminieren.

In jedem Fall sehen wir, dass $H$ auf dem Eingabewort $yy$ einen Fehler macht und somit $\halt$ nicht entscheidet. Da das für jede Turingmaschine geht, schließen wir: keine Turingmaschine kann die Sprache $\halt$ entscheiden; sie ist unentscheidbar. $\square$

Ein Student hat am 26. Juni 2024 angemerkt, dass die Sprache

\begin{align*} \negdiag = \{\enc(M) \ | \ \textnormal{$M$ akzeptiert $\enc(M)$ nicht}\} \end{align*}

ja eine extrem konstruierte, nicht wirklich relevante Sprache sei (da hatte er Recht). Insofern sei es auch nicht relevant, dass $\negdiag$ unentscheidbar ist. Das ist allerdings auch nicht, was uns interessiert: unser Ziel war, zu zeigen, dass $\halt$ unentscheidbar ist, und die Unentscheidbarkeit von $\negdiag$ war ein Schritt auf diesem Weg. Dass $\halt$ unentscheidbar ist, ist in der Tat relevant, denn daraus folgt (nicht direkt, aber mit ein paar technischen Tricks), dass im Prinzip jede nichttriviale Frage über das Verhalten eines Programmcodes unentscheidbar ist. Also sind auch Fragen wie "Kann das Programm abstürzen?" oder "Kann ein unautorisierter Nutzer Zugang zu XYZ erhalten?" unentscheidbar.

Das Wort Unentscheidbarkeit verwenden wir hier in seiner technischen Bedeutung, die wir definiert haben: es gibt keine Turingmaschine, die das Problem entscheidet, also auf jeder Eingabeinstanz terminiert und die richtige Antwort liefert. Es gibt also in der Tat Raum für Algorithmen, die Software untersuchen und diese gegebenenfalls verifizieren oder Fehler / Sicherheitslücken finden. Dies ist im Prinzip das sehr real existierende Forschungsfeld der Programmverifikation. Die Unentscheidbarkeit des Halteproblems impliziert nicht, dass man auf dem Feld der Programmverifikation keine Fortschritte erzielen kann; sie impliziert nur, dass es keinen ultimaten Programmverifikator bzw. Bugfinder gibt.