Halteproblem: Unentscheidbarkeit verstehen

Ein Algorithmus ist eine Berechnungsvorschrift: mehrere Rechenschritte nach festen Regeln. In der theoretischen Informatik führt man Algorithmen auf abstrakten Maschinen aus. Eine typische abstrakte Maschine ist die Turingmaschine.

Das Halteproblem fragt, ob die Ausführung eines Algorithmus zu einem Ende gelangt. Genauer: Eine Maschine H soll für jede Maschine T mit jeder Eingabe w entscheiden, ob T irgendwann anhält oder endlos weiterläuft. Das ist eine Ja-Nein-Frage. H bekäme dafür eine codierte Beschreibung b(T) von T und die Eingabe w. Formal ist das Halteproblem eine Eigenschaft von Paaren aus Algorithmus und Eingabe: Der Algorithmus terminiert für die Eingabe, er rechnet also nur endlich lange.

Bei vielen Programmen ist leicht zu sehen, ob sie irgendwann anhalten. Es gibt aber auch Programme, bei denen das nach dem gegenwärtigen Wissensstand noch nicht vorhergesagt werden kann. Ein Beispiel ist das Collatz-Programm unten.

Eine Eigenschaft heißt entscheidbar, wenn es ein Entscheidungsverfahren für sie gibt. Das ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht. Gibt es kein solches Verfahren, heißt die Eigenschaft unentscheidbar. Beispiele für entscheidbare Mengen sind alle endlichen Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen. Zu jeder entscheidbaren Menge ist auch ihr Komplement entscheidbar.

Bei einer semi-entscheidbaren Menge wird nur für „ja“ gefordert, dass die Berechnung in endlicher Zeit anhält. Für „nein“ darf der Algorithmus ewig weiterlaufen. Semi-entscheidbare Mengen heißen auch rekursiv aufzählbar und bilden eine allgemeinere Klasse als die entscheidbaren Mengen.

Das Komplement des Halteproblems ist die Gegenfrage: Hält T mit w nicht an? Eine Maschine G, die diese Gegenfrage semi-entscheiden soll, gibt 1 aus, wenn T mit w nicht hält. Hält T mit w, dann hält G selbst nicht.

Das Halteproblem ist semi-entscheidbar, weil die Antwort „ja“ immer durch Laufenlassen des Programms gegeben werden kann. Sein Komplement ist jedoch nicht semi-entscheidbar. Und es gilt: Ist sowohl eine Menge als auch ihr Komplement semi-entscheidbar, dann ist die Menge entscheidbar. Beim Halteproblem fehlt eine der beiden Hälften.

Alan Turing bewies, dass eine Maschine H, die das Halteproblem für alle Maschinen und Eingaben entscheidet, nicht existieren kann. Der Beweis wurde für Turingmaschinen geführt. Er ist indirekt: Man nimmt zuerst das Gegenteil an und führt es zu einem Widerspruch.

Schritt 1: Selbstanwendung und Umkehrung. Die Diagonalsprache ist die Menge aller Turingmaschinen, die nicht halten, wenn sie ihre eigene Kodierung als Eingabe bekommen. Das ist die Selbstanwendung: Eine Maschine bekommt ihre eigene Beschreibung als Eingabe. Angenommen, es gäbe eine Maschine F, die bei Eingabe b(T) eine 1 ausgibt, wenn T mit b(T) nicht hält, und selbst nicht hält, wenn T mit b(T) hält. Setzt du für T die Maschine F selbst ein, kehrt sich die Aussage um: F müsste bei b(F) halten, wenn F bei b(F) nicht hält, und nicht halten, wenn F bei b(F) hält. Das ist ein Widerspruch. Eine solche Maschine F kann nicht existieren.

Schritt 2: Angenommen, es gäbe eine Maschine G, die das Komplement des Halteproblems semi-entscheidet. Daraus ließe sich F bauen: F startet G einfach mit der Beschreibung b(T) doppelt hintereinander, getrennt durch ein Trennzeichen. Diese Konstruktion ist sicher möglich. F gibt es aber nicht, also kann es auch G nicht geben.

Schritt 3: Angenommen, es gäbe eine Maschine H, die 0 ausgibt, wenn T mit w nicht hält (0 = hält nicht), und 1, wenn T mit w hält (1 = hält). Daraus baut man G: Gibt H eine 0 aus, gibt G eine 1 aus. Gibt H eine 1 aus, geht G in eine Endlosschleife. Diese Konstruktion ist sicher möglich. G gibt es nicht, also kann es auch H nicht geben.

Das Halteproblem ist für alle möglichen Algorithmen und beliebige Eingaben zusammen nicht entscheidbar. Es gibt keinen Algorithmus, der diese Frage für alle beantwortet. Für viele einzelne Algorithmen ist die Frage aber leicht zu beantworten. Auch das gleichmäßige Halteproblem ist unentscheidbar: Hält ein Algorithmus für jede Eingabe?

Das hat eine Folge: Es ist generell nicht möglich, automatisiert festzustellen, welche Programme jemals zu einem Ende finden (Terminierungsbeweis). Für bestimmte Klassen von Turingmaschinen ist das Halteproblem jedoch entscheidbar, zum Beispiel für Programme ohne Schleifen. Das gilt auch für viele schwächere Berechnungsmodelle, etwa linear beschränkte Turingmaschinen. Viele Programme in der Praxis sind außerdem so gebaut, dass man ihre Terminierung automatisch beweisen kann.

Bewiesen ist die Unentscheidbarkeit für Turingmaschinen. Mit „Algorithmus“ ist, wenn nichts anderes gesagt wird, die Turingmaschine oder ein gleichwertiges Modell gemeint. Dass sie für jeden intuitiv denkbaren Algorithmus gilt, folgt nur, wenn die Church-Turing-These wahr ist.

Unentscheidbarkeit besagt nur, dass eine Eigenschaft nicht durch einen Algorithmus berechnet werden kann. Sie darf nicht verwechselt werden mit der praktischen oder fundamentalen Unmöglichkeit, einer Aussage einen Wahrheitswert zuzuordnen. Eine einzelne Aussage ist immer entscheidbar, auch wenn ihr Wahrheitswert noch ungeklärt ist. Auch andere Fragen sind im Allgemeinen unentscheidbar, etwa ob zwei Programme dieselbe Funktion berechnen. Das folgt nach dem Satz von Rice.