Halteproblem: Unentscheidbarkeit verstehen

Stell dir ein Prüfprogramm vor. Es erhält zwei Dinge:

• den Code eines beliebigen Programms $P$,
• eine konkrete Eingabe $w$ für dieses Programm.

Das Prüfprogramm soll immer nach endlich vielen Schritten eine korrekte Antwort geben:

• Ja: $P$ hält bei der Eingabe $w$.
• Nein: $P$ läuft bei dieser Eingabe unbegrenzt weiter.

Für Turingmaschinen kann die zugehörige Haltesprache so beschrieben werden:

$$K=\{b(T)*w\mid T\text{ hält bei Eingabe }w\}$$

Dabei bezeichnet $b(T)$ eine codierte Beschreibung der Turingmaschine $T$. Das Zeichen $*$ trennt die Maschinenbeschreibung von der Eingabe $w$.

Man kann $P$ mit der Eingabe $w$ Schritt für Schritt simulieren. Hält $P$, beobachtet die Simulation dies nach endlich vielen Schritten. Der positive Fall ist damit allgemein erkennbar.

Läuft $P$ dagegen unbegrenzt, läuft auch die Simulation möglicherweise unbegrenzt. Zu keinem endlichen Zeitpunkt folgt allein aus dem bisherigen Verlauf, dass das Programm niemals mehr halten wird.

Auch das Speichern schon beobachteter Zustände löst die allgemeine Aufgabe nicht. Wiederholt sich eine vollständige Konfiguration, wurde eine Schleife nachgewiesen. Zu einer Konfiguration gehören der Bandinhalt, die Position des Schreib-Lese-Kopfs und der Zustand der Turingmaschine.

Eine Turingmaschine kann jedoch immer neue Bandbereiche beschreiben. Sie kann daher unendlich laufen, ohne eine vollständige Konfiguration zu wiederholen.

Der zentrale Beweis beginnt mit einer Annahme: Es gebe einen universellen Entscheider HALT(P, w). Er antworte immer korrekt und halte selbst stets an.

Aus diesem angeblichen Entscheider bauen wir ein Gegenprogramm GEGEN(P):

1. GEGEN fragt HALT, ob das Programm $P$ bei Eingabe seines eigenen Codes $P$ hält.
2. Antwortet HALT mit Nein, beendet sich GEGEN.
3. Antwortet HALT mit Ja, läuft GEGEN absichtlich endlos.

Damit kehrt GEGEN die Vorhersage des Entscheiders um:

$$GEGEN(P)\text{ hält}\iff P(P)\text{ hält nicht}$$

Nun erhält GEGEN seinen eigenen Code als Eingabe. Wir betrachten also GEGEN(GEGEN).

Die Aussage betrifft den allgemeinen Fall. Sie bedeutet nicht, dass man bei keinem Programm etwas über die Terminierung sagen kann.

Für einzelne Programme oder eingeschränkte Programmklassen sind Terminierungsnachweise möglich. Ein Programm ohne Schleifen kann beispielsweise zu einer Klasse gehören, deren Halteverhalten entscheidbar ist. Auch eine erkannte Wiederholung einer vollständigen Konfiguration beweist eine konkrete Endlosschleife.

Compiler können außerdem syntaktische Fehler erkennen. Daraus folgt jedoch nicht, dass sie für jedes syntaktisch korrekte Programm entscheiden könnten, ob es bei jeder Eingabe hält.

Vertiefung: Halten auf leerem Band

Beim Null-Halteproblem startet eine Turingmaschine mit einem leeren Band. Diese Variante ist hinsichtlich der Entscheidbarkeit genauso schwer wie das allgemeine Halteproblem.

Zu einer Maschine $T$ und einer Eingabe $w$ lässt sich eine neue Maschine $T_w$ konstruieren:

1. $T_w$ schreibt zuerst $w$ auf das leere Band.
2. Danach verhält sich $T_w$ genauso wie $T$ bei der Eingabe $w$.

Daher gilt:

$$T_w\text{ hält auf leerem Band}\iff T\text{ hält bei Eingabe }w$$

Könnte man das Halten auf leerem Band allgemein entscheiden, könnte man damit auch das allgemeine Halteproblem entscheiden. Weil das unmöglich ist, ist auch das Null-Halteproblem unentscheidbar.

Du hast das Lernziel erreicht, wenn du nicht nur sagen kannst, dass das Halteproblem unentscheidbar ist, sondern auch die Annahme, Selbstanwendung, Umkehrung und den entstehenden Widerspruch in eigenen Worten verbindest.