Lektion 3.3

Das Halteproblem und Unentscheidbarkeit

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • das Halteproblem formal als Sprache HH aufschreiben,

  • den Diagonalbeweis für die Unentscheidbarkeit von HH vollständig führen,

  • zeigen, dass HH semi-entscheidbar ist und H‾\overline{H} nicht,

  • den Satz "LL entscheidbar genau dann, wenn LL und L‾\overline{L} semi-entscheidbar sind" beweisen und anwenden,

  • typische Fehlschlüsse über das Halteproblem erkennen und richtigstellen.

Vorausgesetzt: Turingmaschinen, Berechenbarkeit und die Church-Turing-These

Das folgende Programm sucht ein Gegenbeispiel zur Goldbach-Vermutung, die seit 1742 offen ist. Sie besagt, dass jede gerade Zahl größer als 22 die Summe zweier Primzahlen ist.

ZeileEinrückungAnweisung
10n := 4\texttt{n := 4}
20WHILE n ist Summe zweier Primzahlen DO\texttt{WHILE n ist Summe zweier Primzahlen DO}
31n := n + 2\texttt{n := n + 2}
40END\texttt{END}
50HALT\texttt{HALT}

Die Bedingung in Zeile 2 lässt sich leicht ausrechnen: Probiere alle Zerlegungen n=p+(n−p)n = p + (n - p) mit p≤n/2p \le n/2 durch und prüfe, ob beide Summanden Primzahlen sind. Das Programm hält genau dann, wenn die Vermutung falsch ist. Hätte man ein Werkzeug, das für jedes Programm sagt, ob es hält, wäre die Goldbach-Vermutung mit einem Knopfdruck entschieden, und mit ihr viele andere offene Fragen der Mathematik.

So ein Werkzeug wäre auch im Alltag nützlich: Ein Compiler könnte vor jeder Endlosschleife warnen. Diese Lektion zeigt, dass es ein solches Werkzeug nicht geben kann, und sie zeigt es mit demselben Diagonalprinzip, das Cantor für die Sprachen benutzt hat.

Vermute zuerst

Ein Prüfwerkzeug soll für jede Turingmaschine MM und jedes Wort ww nach endlicher Zeit richtig sagen, ob MM auf ww hält. Wie könnte es arbeiten?

Definition

Halteproblem

Über dem Alphabet {0,1,#}\{0, 1, \#\} ist das Halteproblem die Sprache

H={x#w:x,w∈{0,1}∗ und Mx ha¨lt auf w}H = \{x\#w : x, w \in \{0,1\}^* \text{ und } M_x \text{ hält auf } w\}.

Dabei ist MxM_x die Maschine mit Kodierung xx aus der letzten Lektion (ungültige Wörter gehören zu einer festen Maschine, die sofort verwirft). "Hält" heißt: Sie erreicht qjaq_\text{ja} oder qneinq_\text{nein}, das Ergebnis ist egal. Wörter, die nicht die Form x#wx\#w haben, liegen nicht in HH.

Ist x=⟨M⟩x = \langle M \rangle, schreiben wir auch ⟨M⟩#w\langle M \rangle \# w.

Beispiel

Wer liegt in HH?

Sei M′M' die Maschine mit δ(q0,0)=(q0,0,N)\delta(q_0, 0) = (q_0, 0, N), δ(q0,1)=(qja,1,N)\delta(q_0, 1) = (q_\text{ja}, 1, N) und δ(q0,□)=(qnein,□,N)\delta(q_0, \square) = (q_\text{nein}, \square, N). Sie akzeptiert Wörter, die mit 11 beginnen, verwirft das leere Wort und bleibt bei einer führenden 00 für immer stehen.

  • ⟨M′⟩#10∈H\langle M' \rangle \# 10 \in H, denn M′M' akzeptiert nach einem Schritt.
  • ⟨M′⟩#01∉H\langle M' \rangle \# 01 \notin H, denn M′M' bleibt auf der 00 stehen.
  • ⟨M′⟩#∈H\langle M' \rangle \# \in H (also w=εw = \varepsilon), denn M′M' verwirft, und Verwerfen ist Halten.

Für diese eine Maschine ist die Frage leicht, weil man ihr Verhalten vollständig überblickt. Das Halteproblem fragt nach einem Verfahren, das für alle x#wx\#w zugleich funktioniert.

Satz

Das Halteproblem ist semi-entscheidbar

Es gibt eine Turingmaschine MHM_H mit L(MH)=HL(M_H) = H.

Satz

Das Halteproblem ist unentscheidbar

Es gibt keine Turingmaschine, die auf jeder Eingabe hält und genau die Wörter aus HH akzeptiert.

Beispiel

Der Beweis als Diagonale

Schreibe in eine Tabelle, ob MwnM_{w_n} auf dem Wort wmw_m hält ("hält") oder nicht ("läuft"). Die Einträge unten sind ausgedacht, nur die Konstruktion zählt.

w0w_0w1w_1w2w_2w3w_3
Mw0M_{w_0}hältläufthälthält
Mw1M_{w_1}läuftläufthältläuft
Mw2M_{w_2}hälthälthältläuft
Mw3M_{w_3}läufthältläuftläuft
DDläufthältläufthält

Die Zeile von DD ist die umgekehrte Diagonale: DD verhält sich auf wnw_n anders als MwnM_{w_n}.

Also unterscheidet sich DD von jeder Zeile der Tabelle an mindestens einer Stelle. Aber DD ist eine Turingmaschine und muss daher selbst eine Zeile sein, nämlich die mit wn=⟨D⟩w_n = \langle D \rangle. An der Diagonalstelle dieser Zeile müsste der Eintrag zugleich "hält" und "läuft" sein. Das ist Cantors Argument aus der letzten Lektion, mit Maschinen statt Sprachen.

Kurz geprüft

Warum ist die Maschine DD aus dem Beweis nur unter der Annahme baubar, dass HH entscheidbar ist?

Satz

Entscheidbar heißt: von beiden Seiten semi-entscheidbar

Eine Sprache L⊆Σ∗L \subseteq \Sigma^* ist genau dann entscheidbar, wenn LL und L‾=Σ∗∖L\overline{L} = \Sigma^* \setminus L beide semi-entscheidbar sind.

Kurz geprüft

Im Beweis von "⇐\Leftarrow" läuft M1M_1 auf ww ewig, und M2M_2 akzeptiert ww in seinem 5. Schritt. AA beginnt mit einem Schritt von M1M_1 und wechselt dann ab. Nach wie vielen simulierten Schritten insgesamt verwirft AA?

Satz

Das Komplement des Halteproblems

H‾={0,1,#}∗∖H\overline{H} = \{0, 1, \#\}^* \setminus H ist nicht semi-entscheidbar.

Beispiel

Praktische Folgen

Nach der Church-Turing-These gilt der Satz für jede Programmiersprache, die Turingmaschinen simulieren kann, also für Python, Java und C. Es gibt kein Programm, das für jedes Programm und jede Eingabe richtig sagt, ob es hält. Was es gibt:

  • Vorsichtige Analysen. Werkzeuge zum Terminierungsnachweis antworten "hält", "hält nicht" oder "weiß nicht". Sie sind nützlich, solange sie nie falsch antworten; das "weiß nicht" lässt sich nicht für alle Programme vermeiden.
  • Eingeschränkte Sprachen. In manchen Beweisassistenten muss jede Funktion nachweislich terminieren. Dann ist Halten trivial, aber man kann nicht mehr jede berechenbare Funktion hinschreiben.
  • Zeitlimits. Ein Testsystem bricht nach 10 Sekunden ab. Es unterscheidet aber nicht zwischen "rechnet ewig" und "braucht 11 Sekunden".

Ein echter Rechner hat nur endlich viel Speicher und damit endlich viele Zustände; in diesem Modell ist Halten im Prinzip entscheidbar, weil sich ein Speicherzustand wiederholen muss, wenn das Programm nicht hält. Bei 2362^{36} Bit Speicher (8 Gibibyte) sind das aber 22362^{2^{36}} mögliche Speicherinhalte, mehr als jede denkbare Rechenzeit durchprobieren kann. Das Turingmodell mit unbegrenztem Speicher beschreibt die Lage treffender.

Häufige Fehler

Man kann es doch für dieses Programm entscheiden

"Für mein Programm sehe ich sofort, dass es hält. Also ist das Halteproblem doch entscheidbar, man muss nur genau hinschauen." Oder: "Unentscheidbar heißt, dass man bei keinem Programm wissen kann, ob es hält."

Richtig ist

Unentscheidbar ist eine Aussage über ein einziges Verfahren für alle Eingaben. Für ein festes Paar (M,w)(M, w) ist die Frage sogar trivial entscheidbar: Entweder die Maschine, die immer "ja" sagt, oder die, die immer "nein" sagt, antwortet richtig; man weiß nur vielleicht nicht, welche. Beim Goldbach-Programm kennt bis heute niemand die richtige. Für sehr viele einzelne Programme kann man das Halten beweisen; nur gibt es kein Verfahren, das jeden Fall erledigt.

Häufige Fehler

Lange genug laufen lassen

"Wenn ein Programm nach einer Milliarde Schritten nicht gehalten hat, hält es nie."

Richtig ist

Eine Maschine, die bis 109+110^9 + 1 zählt und dann hält, widerlegt das. Es gibt sogar keine berechenbare Schranke: Gäbe es eine berechenbare Funktion ss, sodass jede Maschine MxM_x, die auf ww überhaupt hält, nach höchstens s(x#w)s(x\#w) Schritten hält, dann könnte man HH entscheiden: s(x#w)s(x\#w) ausrechnen, so viele Schritte simulieren und antworten. Das widerspricht dem Satz.

Zusammenfassung

  • H={x#w:Mx ha¨lt auf w}H = \{x\#w : M_x \text{ hält auf } w\} ist das Halteproblem.

  • HH ist semi-entscheidbar: Man simuliert MxM_x auf ww mit der universellen Maschine und akzeptiert, wenn sie hält.

  • HH ist unentscheidbar: Ein Entscheider AA ergäbe eine Maschine DD, die auf ⟨D⟩\langle D \rangle genau dann hält, wenn sie nicht hält.

  • LL ist genau dann entscheidbar, wenn LL und L‾\overline{L} semi-entscheidbar sind; der Entscheider simuliert beide abwechselnd.

  • Daraus folgt: H‾\overline{H} ist nicht semi-entscheidbar.

  • Praktisch gibt es keinen perfekten Endlosschleifen-Finder, wohl aber vorsichtige Analysen mit der Antwort "weiß nicht".

  • Unentscheidbar heißt: kein einziges Verfahren für alle Eingaben. Einzelne Fälle können leicht sein.

Übungen

Aufgabe 1Multiple Choice

Sei M′M' die Maschine aus dem Beispiel (bei führender 00 bleibt sie stehen, bei führender 11 akzeptiert sie, das leere Wort verwirft sie). Welches Wort liegt in HH?

Aufgabe 2Numerisch

Der Entscheider aus dem Satz über LL und L‾\overline{L} simuliert abwechselnd, beginnend mit M1M_1. Auf einem Wort ww akzeptiert M1M_1 in ihrem 7. Schritt, M2M_2 hält nie. Wie viele Schritte hat der Entscheider insgesamt simuliert, wenn er akzeptiert?

Aufgabe 3Multiple Choice

Welche Aussage ist richtig?

Aufgabe 4Multiple Choice

Sei GG eine Turingmaschine, die wie das Goldbach-Programm genau dann auf ε\varepsilon hält, wenn die Goldbach-Vermutung falsch ist. Was folgt aus der Unentscheidbarkeit von HH für GG?

Aufgabe 5Freitext

Jemand behauptet, ein Programm geschrieben zu haben, das für jedes Python-Programm ohne Eingabe mit höchstens 1000 Zeichen richtig "hält" oder "hält nicht" ausgibt. Widerspricht das der Unentscheidbarkeit des Halteproblems? Begründe.

Aufgabe 6Freitext

Sei K={x∈{0,1}∗:Mx ha¨lt auf x}K = \{x \in \{0,1\}^* : M_x \text{ hält auf } x\}. Zeige direkt mit einem Diagonalargument, ohne den Satz über LL und L‾\overline{L}, dass K‾={x:Mx ha¨lt nicht auf x}\overline{K} = \{x : M_x \text{ hält nicht auf } x\} nicht semi-entscheidbar ist.