Das Halteproblem

Lernziele

• Du kannst erklären, was das Halteproblem ist.
• Du kannst die Beweisidee wiedergeben, warum es unlösbar ist.
• Du kannst einordnen, was das für die Praxis bedeutet.

Programme, die nie fertig werden

Führe dieses Programm nicht unüberlegt aus — schau es zuerst an:

n = 1
while n != 0:
    n = n + 1

n startet bei 1 und wird immer grösser. Es wird nie 0. Das Programm läuft für immer — eine Endlosschleife.

Bei diesem Beispiel sieht man es sofort. Aber bei diesem?

def collatz(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1

collatz(27)

Hält das für jede Startzahl n? Das weiss bis heute niemand. Es ist eines der bekanntesten offenen Probleme der Mathematik (die Collatz-Vermutung). Für alle je getesteten Zahlen hält es — aber ein Beweis fehlt.

Die Frage

Wäre es nicht praktisch, ein Prüfprogramm zu haben, das für jedes Programm und jede Eingabe zuverlässig sagt: «hält an» oder «läuft ewig»? Dein Editor könnte dich vor jeder Endlosschleife warnen, bevor du das Programm startest.

Das ist das Halteproblem: Gibt es ein Programm haelt(programm, eingabe), das diese Frage immer korrekt beantwortet?

Turing hat 1936 bewiesen: Nein. Ein solches Programm kann es nicht geben. Nicht «wir haben es noch nicht gefunden» — es ist logisch unmöglich.

Die Beweisidee

Der Beweis ist ein Widerspruchsbeweis, und er ist kurz genug, um ihn ganz zu verstehen.

Annahme: Es gibt die Funktion haelt(p, e), die für jedes Programm p und jede Eingabe e korrekt True (hält) oder False (hält nicht) liefert.

Dann bauen wir daraus dieses fiese Programm:

def quer(p):
    if haelt(p, p):      # würde p, gefüttert mit sich selbst, anhalten?
        while True:       # ... dann laufe absichtlich ewig
            pass
    else:
        return            # ... sonst halte sofort an

quer tut also immer das Gegenteil von dem, was haelt über p vorhersagt.

Jetzt die entscheidende Frage: Was passiert bei quer(quer) — wenn wir quer mit sich selbst füttern?

• Fall 1: haelt(quer, quer) sagt True. Dann geht quer in die Endlosschleife — es hält nicht. Die Vorhersage war falsch.
• Fall 2: haelt(quer, quer) sagt False. Dann kehrt quer sofort zurück — es hält doch. Die Vorhersage war wieder falsch.

In beiden Fällen irrt sich haelt. Aber wir hatten angenommen, haelt sei immer korrekt. Widerspruch — die Annahme war falsch. Ein solches haelt kann nicht existieren. $\blacksquare$

Zum Diskutieren

Der Trick ist die Selbstanwendung: quer bekommt sich selbst als Eingabe. Kommt dir das bekannt vor? Der gleiche Kniff steckt im Satz «Dieser Satz ist falsch» und in Russells Frage nach dem Barbier, der genau die Männer rasiert, die sich nicht selbst rasieren.

Verstanden?

Was heisst das für die Praxis?

• Kein Tool der Welt kann alle Endlosschleifen im Voraus erkennen. Auch nicht mit KI, auch nicht in 100 Jahren — es ist mathematisch unmöglich.
• Viele verwandte Fragen sind genauso unlösbar: «Tun diese zwei Programme dasselbe?», «Ist dieser Code toter Code?», «Enthält dieses Programm Schadcode?» — für alle gilt: kein Verfahren kann es in jedem Fall korrekt entscheiden.
• Deshalb arbeiten Virenscanner und Code-Analyse-Tools mit Näherungen: Sie erkennen viele Fälle, aber nie alle. Das ist keine Schwäche der Entwickler, sondern eine Grenze der Berechenbarkeit selbst.

Der Bogen zurück

Endliche Automaten können nicht zählen. Turing-Maschinen können alles berechnen, was überhaupt berechenbar ist — aber selbst für sie gibt es Fragen, die keine Maschine je beantworten wird. Das ist vielleicht die schönste Erkenntnis dieses Kapitels: Die Informatik kennt ihre eigenen Grenzen, und sie kann sie sogar beweisen.