Das Halteproblem und Unentscheidbarkeit
Lesen anpassen
Nach dieser Lektion kannst du
das Halteproblem formal als Sprache aufschreiben,
den Diagonalbeweis für die Unentscheidbarkeit von vollständig führen,
zeigen, dass semi-entscheidbar ist und nicht,
den Satz " entscheidbar genau dann, wenn und 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 die Summe zweier Primzahlen ist.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 0 | |
| 3 | 1 | |
| 4 | 0 | |
| 5 | 0 |
Die Bedingung in Zeile 2 lässt sich leicht ausrechnen: Probiere alle Zerlegungen mit 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.
Ein Prüfwerkzeug soll für jede Turingmaschine und jedes Wort nach endlicher Zeit richtig sagen, ob auf hält. Wie könnte es arbeiten?
Halteproblem
Über dem Alphabet ist das Halteproblem die Sprache
.
Dabei ist die Maschine mit Kodierung aus der letzten Lektion (ungültige Wörter gehören zu einer festen Maschine, die sofort verwirft). "Hält" heißt: Sie erreicht oder , das Ergebnis ist egal. Wörter, die nicht die Form haben, liegen nicht in .
Ist , schreiben wir auch .
Wer liegt in ?
Wer liegt in ?
Sei die Maschine mit , und . Sie akzeptiert Wörter, die mit beginnen, verwirft das leere Wort und bleibt bei einer führenden für immer stehen.
- , denn akzeptiert nach einem Schritt.
- , denn bleibt auf der stehen.
- (also ), denn 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 zugleich funktioniert.
Das Halteproblem ist semi-entscheidbar
Es gibt eine Turingmaschine mit .
prüft zuerst, ob die Eingabe die Form mit hat, und verwirft sonst. Dann simuliert sie mit der universellen Maschine die Maschine auf (ein ungültiges behandelt sie wie die feste Maschine, die sofort verwirft). Hält die Simulation, egal in welchem Haltezustand, akzeptiert .
Ist , hält auf nach endlich vielen Schritten, und akzeptiert. Ist , hält die Simulation nie, und akzeptiert nicht. Also .
Das Halteproblem ist unentscheidbar
Es gibt keine Turingmaschine, die auf jeder Eingabe hält und genau die Wörter aus akzeptiert.
Beweisidee: Aus einem angeblichen Entscheider baut man eine Maschine, die sich auf ihrer eigenen Kodierung genau umgekehrt verhält, wie der Entscheider vorhersagt.
Angenommen, ist ein Entscheider für . Konstruiere die Maschine , die auf Eingabe so arbeitet:
- Schreibe auf das Band und lasse darauf laufen. hält nach Voraussetzung.
- Akzeptiert (also hält auf ), gehe in eine Endlosschleife.
- Verwirft (also hält auf nicht), akzeptiere.
ist eine Turingmaschine, denn Kopieren, Aufrufen von und eine Schleife sind mit Zuständen und Übergängen baubar. Für jedes gilt also
hält auf verwirft hält nicht auf .
Setze nun ein. Dann ist , und die Äquivalenz wird zu
hält auf hält nicht auf .
Das ist ein Widerspruch. Also gibt es keinen Entscheider , und ist unentscheidbar.
Der Beweis als Diagonale
Der Beweis als Diagonale
Schreibe in eine Tabelle, ob auf dem Wort hält ("hält") oder nicht ("läuft"). Die Einträge unten sind ausgedacht, nur die Konstruktion zählt.
| hält | läuft | hält | hält | |
| läuft | läuft | hält | läuft | |
| hält | hält | hält | läuft | |
| läuft | hält | läuft | läuft | |
| läuft | hält | läuft | hält |
Die Zeile von ist die umgekehrte Diagonale: verhält sich auf anders als .
Also unterscheidet sich von jeder Zeile der Tabelle an mindestens einer Stelle. Aber ist eine Turingmaschine und muss daher selbst eine Zeile sein, nämlich die mit . 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.
Warum ist die Maschine aus dem Beweis nur unter der Annahme baubar, dass entscheidbar ist?
Entscheidbar heißt: von beiden Seiten semi-entscheidbar
Eine Sprache ist genau dann entscheidbar, wenn und beide semi-entscheidbar sind.
"": Ist ein Entscheider für , so ist , also semi-entscheidbar. Vertauscht man in die Zustände und , entsteht ein Entscheider für ; also ist auch semi-entscheidbar.
"": Seien und Maschinen mit und . Die Zwei-Band-Maschine kopiert die Eingabe auf beide Bänder und simuliert dann abwechselnd einen Schritt von auf Band 1 und einen Schritt von auf Band 2. Akzeptiert , akzeptiert . Akzeptiert , verwirft . Hält eine der beiden verwerfend, simuliert die andere allein weiter.
hält immer: Jedes liegt in oder in , also akzeptiert oder nach endlich vielen Schritten , und hält nach höchstens simulierten Schritten. antwortet richtig: Es akzeptieren nie beide, denn und sind disjunkt; akzeptiert , ist , akzeptiert , ist . Also ist ein Entscheider für .
Im Beweis von "" läuft auf ewig, und akzeptiert in seinem 5. Schritt. beginnt mit einem Schritt von und wechselt dann ab. Nach wie vielen simulierten Schritten insgesamt verwirft ?
Das Komplement des Halteproblems
ist nicht semi-entscheidbar.
ist semi-entscheidbar. Wäre auch semi-entscheidbar, so wäre nach dem letzten Satz entscheidbar. Das widerspricht der Unentscheidbarkeit von .
Dass auch die Wörter ohne die Form enthält, ändert nichts: Diese Form zu prüfen ist leicht, also ist genau dann semi-entscheidbar, wenn es ist.
Praktische Folgen
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 Bit Speicher (8 Gibibyte) sind das aber mögliche Speicherinhalte, mehr als jede denkbare Rechenzeit durchprobieren kann. Das Turingmodell mit unbegrenztem Speicher beschreibt die Lage treffender.
Man kann es doch für dieses Programm entscheiden
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."
Unentscheidbar ist eine Aussage über ein einziges Verfahren für alle Eingaben. Für ein festes Paar 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.
Lange genug laufen lassen
Lange genug laufen lassen
"Wenn ein Programm nach einer Milliarde Schritten nicht gehalten hat, hält es nie."
Eine Maschine, die bis zählt und dann hält, widerlegt das. Es gibt sogar keine berechenbare Schranke: Gäbe es eine berechenbare Funktion , sodass jede Maschine , die auf überhaupt hält, nach höchstens Schritten hält, dann könnte man entscheiden: ausrechnen, so viele Schritte simulieren und antworten. Das widerspricht dem Satz.
Zusammenfassung
ist das Halteproblem.
ist semi-entscheidbar: Man simuliert auf mit der universellen Maschine und akzeptiert, wenn sie hält.
ist unentscheidbar: Ein Entscheider ergäbe eine Maschine , die auf genau dann hält, wenn sie nicht hält.
ist genau dann entscheidbar, wenn und semi-entscheidbar sind; der Entscheider simuliert beide abwechselnd.
Daraus folgt: 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
Sei die Maschine aus dem Beispiel (bei führender bleibt sie stehen, bei führender akzeptiert sie, das leere Wort verwirft sie). Welches Wort liegt in ?
Der Entscheider aus dem Satz über und simuliert abwechselnd, beginnend mit . Auf einem Wort akzeptiert in ihrem 7. Schritt, hält nie. Wie viele Schritte hat der Entscheider insgesamt simuliert, wenn er akzeptiert?
Welche Aussage ist richtig?
Sei eine Turingmaschine, die wie das Goldbach-Programm genau dann auf hält, wenn die Goldbach-Vermutung falsch ist. Was folgt aus der Unentscheidbarkeit von für ?
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.
Sei . Zeige direkt mit einem Diagonalargument, ohne den Satz über und , dass nicht semi-entscheidbar ist.