Berechenbarkeit: Turingmaschine und Halteproblem

Rechner werden schneller, Speicher größer, Verfahren besser. Es liegt nahe zu denken, dass am Ende alles nur eine Frage von genug Rechenzeit ist.

Das ist falsch, und zwar nicht ein bisschen, sondern grundsätzlich. Es gibt klar formulierte, völlig eindeutige Aufgaben, für die kein Programm existiert. Nicht heute keines, sondern nie eines, gleich mit welcher Sprache, auf welcher Maschine, mit wie viel Zeit.

Dieses Kapitel zeigt zwei Dinge: wie man überhaupt beweisen kann, was alle Programme können, und wie der Beweis für eine solche unlösbare Aufgabe aussieht. Er passt auf eine halbe Seite und gehört zu den bemerkenswertesten Ergebnissen der Informatik.

Vorausgesetzt wird der Algorithmusbegriff aus Was ist ein Algorithmus? mit seinen Merkmalen Eindeutigkeit, Ausführbarkeit, Endlichkeit und Terminierung, dazu die Formalisierung aus Formale Sprachen.

Neu ist die Umkehrung der Fragerichtung: Bisher hieß es „wie löse ich dieses Problem?". Jetzt heißt es „gibt es überhaupt eine Lösung?".

Das Problem mit dem Wort „Algorithmus"

Die Definition aus Klasse 9 ist für die Praxis völlig ausreichend: eine endliche Folge eindeutiger, ausführbarer Schritte. Für einen Beweis reicht sie nicht, und der Grund ist entscheidend.

Angenommen, du willst zeigen: „Für dieses Problem gibt es keinen Algorithmus." Dann musst du eine Aussage über alle Algorithmen treffen, auch über die, an die noch niemand gedacht hat. Dafür brauchst du eine mathematisch exakte Fassung des Begriffs, sonst kannst du über die Gesamtheit gar nicht argumentieren.

🔴 Halte den Unterschied fest: „Ich habe keinen gefunden" ist eine Aussage über dich. „Es gibt keinen" ist eine Aussage über alle. Nur die zweite ist ein Ergebnis, und sie verlangt ein präzises Modell.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Alan Turing schlug 1936 ein Modell vor, das absichtlich so einfach wie möglich ist:

• Ein Band, unendlich lang, in Felder eingeteilt, in jedem Feld ein Zeichen.
• Ein Schreib-Lese-Kopf, der genau ein Feld sieht.
• Eine endliche Menge von Zuständen, dazu ein Startzustand.
• Eine Übergangstabelle: Aus (Zustand, gelesenes Zeichen) folgt (neuer Zustand, zu schreibendes Zeichen, Bewegung des Kopfes: links, rechts oder stehen bleiben).

Das ist alles. Es gibt keine Variablen, keine Schleifen, keine Unterprogramme.

Du erkennst darin den endlichen Automaten wieder, allerdings mit einem entscheidenden Zusatz: Die Turingmaschine kann schreiben und sich in beide Richtungen bewegen. Genau daran scheiterte der endliche Automat im vorigen Kapitel; er konnte sich nur seinen Zustand merken, und davon gibt es endlich viele. Das Band ist unbegrenzt und ersetzt den fehlenden Speicher.

Beispielhafte Arbeitsweise einer Maschine, die eine Folge von Einsen um eine verlängert:

Die Maschine läuft über alle Einsen nach rechts, findet das erste leere Feld, schreibt dort eine Eins und hält an. So mühsam das aussieht: Auf diese Weise lässt sich jede Berechnung ausdrücken, die ein heutiger Rechner ausführt.

Nun die zentrale Behauptung:

Church-Turing-These: Alles, was im intuitiven Sinn „algorithmisch berechenbar" ist, lässt sich von einer Turingmaschine berechnen.

🔴 Beachte das Wort These. Es ist kein Satz, und es kann keiner sein. Auf der einen Seite steht ein mathematisch exakter Begriff (Turingmaschine), auf der anderen ein umgangssprachlicher („was man ausrechnen kann"). Zwischen einem exakten und einem unscharfen Begriff kann es keine bewiesene Gleichheit geben.

Was es dafür gibt, ist außerordentlich starke Evidenz: Mehrere unabhängig entwickelte Modelle, darunter Turings Maschine, Churchs Lambda-Kalkül und die rekursiven Funktionen, stellten sich alle als gleich mächtig heraus. Verschiedene Menschen mit verschiedenen Ansätzen landeten bei genau derselben Grenze. Seit 1936 wurde kein Verfahren gefunden, das mehr kann.

Der praktische Nutzen der These ist groß: Wenn man zeigt, dass eine Turingmaschine etwas nicht kann, dann kann es kein Rechner und keine Programmiersprache. Deshalb sind alle üblichen Sprachen im Kern gleich mächtig; sie unterscheiden sich in Bequemlichkeit, nicht in der Menge lösbarer Probleme. Man nennt das turingvollständig.

Ein Problem heißt berechenbar, wenn es einen Algorithmus gibt, der für jede Eingabe nach endlich vielen Schritten das richtige Ergebnis liefert. Bei Ja-Nein-Fragen sagt man auch entscheidbar.

Dass es nicht berechenbare Probleme geben muss, lässt sich schon durch Abzählen einsehen:

Programme sind abzählbar. Jedes Programm ist ein endlicher Text über einem endlichen Zeichenvorrat. Man kann alle solchen Texte der Länge nach ordnen und durchnummerieren. Es gibt also „nur" abzählbar unendlich viele Programme.

Probleme sind überabzählbar. Eine Ja-Nein-Frage über allen möglichen Eingaben ist im Kern eine Funktion von den natürlichen Zahlen nach $\{0,1\}$. Von diesen gibt es überabzählbar viele, wie Cantors Diagonalargument zeigt.

Folgerung: Es gibt echt mehr Probleme als Programme. Also müssen Probleme ohne Programm existieren, und zwar unvergleichlich viel mehr als lösbare.

Dieses Argument ist elegant, aber unbefriedigend: Es sagt, dass es solche Probleme gibt, ohne eines zu nennen. Turing lieferte ein konkretes.

Halteproblem: Gibt es ein Programm $H$, das für ein beliebiges Programm $P$ und eine beliebige Eingabe $E$ zuverlässig entscheidet, ob $P$ bei Eingabe $E$ anhält oder ewig läuft?

Die Frage ist alles andere als akademisch. Ein solches Programm wäre das perfekte Werkzeug gegen Endlosschleifen, und jede Entwicklungsumgebung hätte es eingebaut.

Turings Antwort: Ein solches $H$ kann es nicht geben. Der Beweis:

Annahme: $H(P, E)$ existiere und liefere immer nach endlicher Zeit „hält" oder „hält nicht".

Schritt 1: Konstruktion: Wir bauen daraus ein neues Programm $T$, das genau eine Eingabe nimmt, nämlich ein Programm $P$:

T(P):
    wenn H(P, P) sagt "hält":
        wiederhole endlos            // T läuft absichtlich ewig
    sonst:
        halte an                     // T hält absichtlich sofort

$T$ tut also immer das Gegenteil dessen, was $H$ für $P$ mit sich selbst als Eingabe vorhersagt. Beachte: $H(P, P)$ ist erlaubt, denn ein Programm ist ein Text und darf als Eingabe dienen. Genau das tut jeder Übersetzer, der Quelltext liest.

Schritt 2: Selbstanwendung: Was macht $T$, wenn man ihm $T$ selbst gibt, also $T(T)$?

Fall 1: $H(T,T)$ sagt „hält". Dann geht $T$ nach Konstruktion in die Endlosschleife, hält also nicht. $H$ hat falsch vorhergesagt.

Fall 2: $H(T,T)$ sagt „hält nicht". Dann hält $T$ nach Konstruktion sofort an. $H$ hat wieder falsch vorhergesagt.

Schritt 3: Widerspruch: In beiden Fällen irrt $H$, obwohl es nach Annahme immer richtig liegt. Die Annahme ist also falsch.

Ergebnis: Das Halteproblem ist unentscheidbar. Ein allgemeiner Endlosschleifen-Prüfer kann nicht existieren.

Was folgt nicht: dass man nie erkennen kann, ob ein Programm hält. Für viele einzelne Programme ist das leicht. Eine Zählschleife von 1 bis 100 hält offensichtlich.

Was folgt: Es gibt kein Verfahren, das das für jedes Programm richtig entscheidet. Die Aussage betrifft die Allgemeinheit, nicht den Einzelfall.

Daraus ergibt sich der Alltag der Softwarewerkzeuge. Ein Übersetzer, der vor möglichen Endlosschleifen warnt, arbeitet zwangsläufig unvollständig: Er meldet manche Fälle und übersieht andere, oder er warnt gelegentlich zu Unrecht. Beides ist keine Schlamperei, sondern die einzige Möglichkeit. Dasselbe gilt für Virenscanner, statische Codeprüfer und automatische Programmverifikation. Wer ein Werkzeug verspricht, das „alle Fehler dieser Art zuverlässig findet", verspricht etwas beweisbar Unmögliches.