Halteproblem

Das Halteproblem beschreibt e​ine Frage a​us der theoretischen Informatik.

Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt werden, entsteht eine Berechnungsvorschrift, ein sogenannter Algorithmus. Zur Ausführung von Algorithmen benutzt man in der theoretischen Informatik abstrakte Maschinen. Eine typische abstrakte Maschine ist die Turingmaschine. Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt. Obwohl das für viele Algorithmen leicht beantwortet werden kann, konnte der Mathematiker Alan Turing beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Diesen Beweis vollzog er an einer Turingmaschine. Das Halteproblem ist somit algorithmisch nicht entscheidbar. Das Resultat spielt eine grundlegende Rolle in der Berechenbarkeitstheorie. Der Begriff Halteproblem wurde nicht von Turing geprägt, sondern erst später durch Martin Davis in seinem Buch Computability and Unsolvability.[1]

Bedeutung

In formalen Systemen d​er Mathematik g​ibt es beweisbare Aussagen.

Beispiel: Die Summe d​er Innenwinkel j​edes beliebigen ebenen Dreiecks beträgt 180 Grad.

Erreichen formale Systeme e​inen bestimmten Grad a​n Komplexität, s​o lassen s​ich Aussagen angeben, d​ie man w​eder beweisen n​och widerlegen kann. Der Beweis dieser Eigenschaft w​urde 1931 v​om österreichischen Mathematiker Kurt Gödel veröffentlicht (gödelscher Unvollständigkeitssatz).[2] Damit zeigte Gödel d​ie Unmöglichkeit d​es Hilbertprogramms auf. Mit diesem wollte David Hilbert 1920 d​ie Mathematik a​uf ein vollständiges u​nd widerspruchsfreies System v​on Axiomen (unbewiesene Grundannahmen) gründen.

Auch nach den Erkenntnissen von Alan Turing gilt: In jedem formalen System, das Turingmaschinen enthält, lassen sich Aussagen formulieren, die weder bewiesen noch widerlegt werden können. Das Halteproblem beschreibt eine solche Aussage. Aus der Unlösbarkeit des Halteproblems folgt, dass es mathematische Funktionen gibt, die zwar wohldefiniert sind, deren Werte sich jedoch nicht für jeden Parameter berechnen lassen. Ein bekanntes Beispiel für eine solche Funktion ist die Radó-Funktion.

Die Church-Turing-These besagt, d​ass alles, w​as intuitiv berechenbar ist, a​uch von e​iner Turingmaschine berechenbar ist. Wenn d​iese Aussage w​ahr ist, k​ann das Halteproblem grundsätzlich n​icht algorithmisch entschieden werden. Das führt z​u der philosophisch weitreichenden Aussage, d​ass nicht j​edes Problem lösbar ist, selbst d​ann nicht, w​enn man a​lle relevanten Informationen k​ennt und s​ich streng a​n einen mathematisch überzeugenden Formalismus hält.

Aus d​er Nichtentscheidbarkeit d​es Halteproblems folgt, d​ass im Allgemeinen e​ine automatisierte Bestimmung logischer Feststellungen („dieser Sachverhalt i​st wahr“) – d​urch eine Programmlogik – n​icht möglich ist. Insbesondere i​st es generell n​icht möglich, automatisiert festzustellen, welche Programme jemals z​u einem Ende finden (Terminierungsbeweis). Für bestimmte Klassen v​on Turingmaschinen i​st das Halteproblem jedoch entscheidbar (zum Beispiel für Programme o​hne Schleifen). Viele i​n der Praxis vorkommende Programme u​nd Verfahren s​ind daher s​o strukturiert, d​ass auf Basis dieser Struktur e​in automatisierter Terminierungsbeweis geführt werden kann.

Illustration

Bei vielen Programmen ist es leicht, festzustellen, ob sie irgendwann anhalten. Es gibt allerdings auch Programme, bei denen es nach dem gegenwärtigen Wissensstand noch nicht möglich ist, vorherzusagen, ob sie bei jeder möglichen Eingabe anhalten. Das folgende Programm hält für jede Eingabe ${\displaystyle n}$ (bei ${\displaystyle n>0}$ und ${\displaystyle n\in \mathbb {N} }$), wenn die bisher unbewiesene Collatz-Vermutung richtig ist. Die Collatz-Vermutung sagt nämlich aus, dass eine solche Schleife früher oder später immer die Zahlenfolge 4, 2, 1 hervorbringen würde, was bei der hier gegebenen Abbruchbedingung "bis n = 1" zum Halten des Programms führen würde.

wiederhole
  falls n gerade:  n := n / 2
  sonst:           n := (3 * n) + 1
bis n = 1

Mathematische Beschreibung

Problemstellung

Falls das Halteproblem entscheidbar ist, gibt es eine Turingmaschine ${\displaystyle H}$, die für jede Turingmaschine ${\displaystyle T}$ mit jeder Eingabe ${\displaystyle w}$ entscheidet, ob ${\displaystyle T}$ irgendwann anhält oder endlos weiterläuft. Die Eingabe für ${\displaystyle H}$ besteht dabei jeweils aus einer codierten Beschreibung ${\displaystyle b(T)}$ der Maschine ${\displaystyle T}$ und deren Eingabe ${\displaystyle w}$.

Alan Turing bewies 1937, dass eine solche Maschine ${\displaystyle H}$ nicht existiert.

Beweisidee

Das Halteproblem ist entscheidbar genau dann, wenn sowohl das Halteproblem als auch sein Komplement semientscheidbar sind. Das Halteproblem ist offensichtlich semientscheidbar: Eine universelle Turingmaschine, die als Eingabe eine Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ und eine Zeichenkette ${\displaystyle w}$ erhält, hält genau dann, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ hält. Es muss also gezeigt werden, dass das Komplement des Halteproblems nicht semientscheidbar ist, dass es also keine Turingmaschine ${\displaystyle G}$ gibt, die bei Eingabe ${\displaystyle b(T)*w}$ immer dann 1 ausgibt, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ nicht hält.

g(i,w)	w=1	w=2	w=3	w=4	w=5	w=6
i=1	1	U	U	1	U	1
i=2	U	U	U	1	U	U
i=3	U	1	U	1	U	1
i=4	1	U	U	1	U	U
i=5	U	U	U	1	1	1
i=6	1	1	U	U	1	U
g(i,i)	1	U	U	1	1	U
f(i)	1	U	U	1	1	U

Anschauliche Darstellung der Funktionen g und f. U steht für „undefiniert“.

Dies gelingt durch ein Diagonalargument. Dafür wird zunächst angenommen, das Komplement des Halteproblems sei semientscheidbar. (Der Beweis ist also indirekt.) Anstelle einer Turingmaschine kann man auch die Funktion betrachten, die von ihr berechnet wird. Die Turingmaschine ${\displaystyle G}$ berechnet die partielle Funktion

${\displaystyle g(i,w)={\begin{cases}1&{\text{falls }}{\text{ die Turingmaschine }}i{\text{ bei Eingabe }}w{\text{ nicht hält}},\\{\text{undefiniert}}&{\text{sonst.}}\end{cases}}}$

Die Diagonale von ${\displaystyle g}$ wird durch die folgende Funktion ${\displaystyle f}$ berechnet.

${\displaystyle f(i)={\begin{cases}1&{\text{falls }}{\text{ die Turingmaschine }}i{\text{ bei Eingabe }}i{\text{ nicht hält}},\\{\text{undefiniert}}&{\text{sonst.}}\end{cases}}}$

Sei ${\displaystyle n_{f}}$ die Nummer einer Turingmaschine ${\displaystyle F}$, welche die Funktion ${\displaystyle f}$ berechnet. Der Funktionswert von ${\displaystyle f}$ an der Stelle ${\displaystyle i=n_{f}}$ ist also

• 1, falls ${\displaystyle f(n_{f})=g(n_{f},n_{f})=1}$, falls also ${\displaystyle F}$ bei Eingabe ${\displaystyle n_{f}}$ nicht hält. Das ist allerdings ein Widerspruch, denn ${\displaystyle F}$ berechnet ${\displaystyle f}$ und muss also halten und 1 ausgeben.
• undefiniert, falls ${\displaystyle f(n_{f})=g(n_{f},n_{f})}$ undefiniert ist, falls also ${\displaystyle F}$ bei Eingabe ${\displaystyle n_{f}}$ hält. Das ist ebenfalls ein Widerspruch, denn ${\displaystyle f}$ ist an dieser Stelle undefiniert, und ${\displaystyle F}$ berechnet ${\displaystyle f}$.

Beweisskizze

Der Beweis orientiert s​ich an d​er Konstruktion v​on Marvin Minsky.[3]

Schritt 1: Die Diagonalsprache ist nicht semi-entscheidbar

Die Menge aller Turingmaschinen, die nicht halten, wenn sie ihre eigene Kodierung als Eingabe bekommen, wird als Diagonalsprache bezeichnet. Der Nachweis, dass die Diagonalsprache nicht semientscheidbar ist, geschieht durch einen Widerspruchsbeweis. Man nimmt an, dass eine Maschine ${\displaystyle F}$ existiert, welche die Diagonalsprache semi-entscheidet, und zeigt, dass dies zu einem logischen Widerspruch führt.

Angenommen, es gäbe eine Turingmaschine ${\displaystyle F}$, die bei Eingabe der Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ den Wert ${\displaystyle 1}$ ausgibt, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle b(T)}$ nicht hält, und die nicht hält, wenn ${\displaystyle T}$ bei Eingabe von ${\displaystyle b(T)}$ hält. Dann müsste ${\displaystyle F}$ bei Eingabe ${\displaystyle b(F)}$ halten und ${\displaystyle 1}$ ausgeben, wenn ${\displaystyle F}$ bei Eingabe ${\displaystyle b(F)}$ nicht hält, und nicht halten, wenn ${\displaystyle F}$ bei Eingabe ${\displaystyle b(F)}$ hält. Das ist ein Widerspruch, eine solche Maschine kann also nicht existieren.

Schritt 2: Das Komplement des Halteproblems ist nicht semi-entscheidbar

Wenn d​as Komplement d​es Halteproblems semi-entscheidbar wäre, d​ann wäre d​ie Diagonalsprache ebenfalls semi-entscheidbar.

Angenommen, es gäbe eine Turingmaschine ${\displaystyle G}$, die bei Eingabe der Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ und einer Zeichenkette ${\displaystyle w}$ 1 ausgibt, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ nicht hält, und die nicht hält, wenn ${\displaystyle T}$ bei Eingabe von ${\displaystyle w}$ hält. Man darf ohne Beschränkung der Allgemeinheit annehmen, dass die Eingabe für ${\displaystyle G}$ die Form ${\displaystyle b(T)*w}$ hat. Dabei ist ${\displaystyle *}$ eine Zeichenkette, die weder in der Beschreibung ${\displaystyle b(T)}$ der Turingmaschine ${\displaystyle T}$ noch in deren Eingabe ${\displaystyle w}$ vorkommt. Aus ${\displaystyle G}$ kann eine Turingmaschine ${\displaystyle F}$ konstruiert werden, die die Diagonalsprache semi-entscheidet. ${\displaystyle F}$ startet bei Eingabe einer Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ einfach ${\displaystyle G}$ mit der Eingabe ${\displaystyle b(T)*T}$.

Wenn ${\displaystyle G}$ das Komplement des Halteproblems semi-entscheidet, so semi-entscheidet ${\displaystyle F}$ die Diagonalsprache. Da es eine solche Maschine ${\displaystyle F}$ nicht geben kann, die Konstruktion von ${\displaystyle F}$ aus ${\displaystyle G}$ aber sicher möglich ist, kann es eine solche Maschine ${\displaystyle G}$ nicht geben.

Schritt 3: Das Halteproblem ist nicht entscheidbar

Wenn d​as Halteproblem entscheidbar wäre, d​ann wäre s​ein Komplement semi-entscheidbar.

Angenommen, es gäbe eine Turingmaschine ${\displaystyle H}$, die bei Eingabe der Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ und einer Zeichenkette ${\displaystyle w}$ 0 ausgibt, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ nicht hält, und die 1 ausgibt, wenn ${\displaystyle T}$ bei Eingabe von ${\displaystyle w}$ hält. Dann gäbe es auch eine Turingmaschine ${\displaystyle G}$, die das Komplement des Halteproblems semi-entscheidet. ${\displaystyle G}$ startet bei Eingabe einer Beschreibung ${\displaystyle b(T)}$ einer Turingmaschine ${\displaystyle T}$ einfach ${\displaystyle H}$ mit derselben Eingabe ${\displaystyle b(T)*w}$. Wenn ${\displaystyle H}$ 0 ausgibt, so gibt ${\displaystyle G}$ 1 aus. Wenn ${\displaystyle H}$ 1 ausgibt, so geht ${\displaystyle G}$ in eine Endlosschleife.

Wenn ${\displaystyle H}$ das Halteproblem entscheidet, so semi-entscheidet ${\displaystyle G}$ das Komplement des Halteproblems. Da es eine solche Maschine ${\displaystyle G}$ nicht geben kann, die Konstruktion von ${\displaystyle G}$ aus ${\displaystyle H}$ aber sicher möglich ist, kann es eine solche Maschine ${\displaystyle H}$ nicht geben.

Grafische Darstellung der Beweiskonstruktion

Maschine ${\displaystyle F}$  Eingabe ${\displaystyle w}$	Maschine ${\displaystyle H}$ Eingabe ${\displaystyle b(F)*w}$	Maschine ${\displaystyle G}$ Eingabe ${\displaystyle b(F)*w}$
hält nicht	hält  Ergebnisanzeige ${\displaystyle 0}$	hält  Ergebnisanzeige ${\displaystyle 1}$
hält	hält  Ergebnisanzeige ${\displaystyle 1}$	hält nicht

Eine äquivalente Formulierung

Das Halteproblem mit leerem Eingabeband (englisch blank-tape halting problem, BTHP, auch als Null-Halteproblem bekannt) ist die Frage, ob eine Turingmaschine ${\displaystyle T}$ bei leerem Eingabeband anhält. Das BTHP ist genauso schwer wie das Halteproblem. Intuitiv ist das der Fall, weil eine Eingabe auch im Startzustand einer Turingmaschine kodiert werden kann.

Offensichtlich kann jede Maschine, die das Halteproblem für jede Turingmaschine ${\displaystyle T}$ mit jeder Eingabe ${\displaystyle w}$ entscheidet, auch das BTHP für ${\displaystyle T}$ entscheiden. Es kann aber auch eine Maschine ${\displaystyle L}$, die für jede Turingmaschine das BTHP entscheidet, bereits das allgemeine Halteproblem entscheiden. Um das Halteproblem für die Turingmaschine ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ zu entscheiden, betrachtet ${\displaystyle L}$ die Turingmaschine ${\displaystyle T_{w}}$, die wie folgt definiert ist. ${\displaystyle T_{w}}$ schreibt zuerst ${\displaystyle w}$ auf das Eingabeband, danach verhält sich ${\displaystyle T_{w}}$ wie ${\displaystyle T}$. ${\displaystyle T_{w}}$ hält insbesondere genau dann auf dem leeren Band, wenn ${\displaystyle T}$ mit Eingabe ${\displaystyle w}$ hält.

Literatur

• Alan Turing: On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2, 42 (1937), S. 230–265. Online-Fassung

Einzelnachweise

1. Martin Davis: Computability and Unsolvability, McGraw-Hill, New York 1958, Nachdruck mit neuem Vor- und Nachwort 1983, Dover Publications Inc., ISBN 978-0-486-61471-7
2. Eine gut verständliche Darstellung der Zusammenhänge und Konsequenzen aus Gödels Arbeiten bietet beispielsweise Douglas R. Hofstadter: Besprechung von Alan Turing: The Enigma, in Metamagicum, Klett-Cotta, Stuttgart 1988, ISBN 3-608-93089-2, S. 519–528.
3. Vorlesungsskript der Old Dominion University, abgerufen am 13. Juli 2011