Halt! Stehenbleiben!

Manche Computerberechnungen haben ein Ergebnis, andere laufen ewig weiter. Die Frage, ob es eine eindeutige Methode gibt, schon im Vorhinein zwischen diesen beiden Fällen zu unterscheiden, ist das „Halteproblem“. Alan Turing hat es gelöst.

Alan Turing

Jeder kennt Computerprogramme, die nicht mehr reagieren. Manchmal kann es geschehen, dass ein Programm in einer unendlichen Schleife läuft – also für immer ohne Unterbrechung Arbeitsschritte ausführt, ohne jemals zu einem Ende zu kommen. Das ist unangenehm: Ein ewig laufendes Programm liefert kein Ergebnis, vergeudet nur wertvolle Rechenzeit. Beim Programmieren muss man daher darauf achten, dass solche Fälle niemals eintreten können – auch dann nicht, wenn das Computerprogramm anfangs mit ungewöhnlichen Eingaben gefüttert wird.

Ergebnis oder unendliche Rechnung?

Herauszufinden, ob ein Computerprogramm ein Ergebnis liefern wird oder auf eine unendlichen Schleife zusteuert, ist eine komplizierte Angelegenheit. Nachdem wir für komplizierte Dinge gerne den Computer verwenden, liegt die Frage nahe: Können wir ein Computerprogramm schreiben, das herausfindet, ob unser Computerprogramm auf eine unendliche Schleife führt, oder ob es irgendwann halten wird? So ein Halte-Test-Programm wäre eine feine Sache: Jeder Programmierer würde mit diesem Halte-Test-Programm seine neuen, eigenen Programme untersuchen, und sie erst dann laufen lassen, wenn das Halte-Test-Programm bestätigt, dass mit einem Ergebnis zu rechnen ist, auf das man nicht unendlich lange warten muss. Die Frage, ob es ein solches Halte-Test-Programm geben kann, nennt man in der Mathematik das „Halteproblem“. Alan Turing konnte zeigen, dass ein solches Halte-Test-Programm logisch nicht möglich ist.

Ein Programm untersucht sich selbst

Der Beweis kann auf viele verschiedene Arten formuliert werden. Entscheidend ist in jedem Fall die Idee, dass ein Computerprogramm sich selbst als Untersuchungsobjekt seiner Rechnungen verwenden kann. Das klingt seltsam, ist aber eigentlich leicht zu verstehen: Ein Computerprogramm bekommt eine Zahl als Eingabe, rechnet, und gibt als Endprodukt wieder eine Zahl aus. Den Begriff „Zahl“ kann man hier ruhig großzügig verwenden: Natürlich kann das Programm auch mehrere Zahlen als Input oder Output haben – doch die kann ich immer zu einer einzigen Zahl zusammenfügen, indem ich die Ziffern zu einer einzigen, langen Zahl aneinanderhänge. Das ist bloß eine Frage der Definition. Auch ein Foto oder ein Musikstück kann – in digitalisierter Form – als Zahl dargestellt werden und als Input für das Programm dienen, oder als Output Ergebnis der Rechnung sein.

Ein Programm beißt sich selbst in den Schwanz: Es ist die Eingabe, mit der es selbst gefüttert wird.
Quelle: [1]

In diesem Sinn ist es klar, dass auch ein Computerprogramm selbst als Zahl dargestellt werden kann. Damit ist es auch möglich, einem Computerprogramm sich selbst als Eingabe für seine Rechnungen zu füttern. Auch in diesem Fall können wir fragen: Wird das Programm, gefüttert mit sich selbst, in einer unendlichen Schleife enden oder ein Ergebnis liefern?

Nur mal angenommen …

Nehmen wir an, wir hätten ein Halte-Test-Programm, das für alle Programme für jeden beliebigen Input-Zahlenwert vorhersagt, ob das Programm halten wird. Nun schreiben wir ein weiteres Programm, wir können es Uroboros-Programm nennen, das dieses Halte-Test-Programm verwendet: Das Uroboros-Programm bekommt als Input ein Computerprogramm (also eine Zahl) und verwendet das Halte-Test-Programm um festzustellen, ob das Input-Programm, gefüttert mit sich selbst, halten wird. Wenn ja, dann führt das Uroboros-Programm auf eine unendliche Schleife und hält nie, wenn nein, dann endet das Uroboros-Programm und liefert eine Zahl als Ergebnis – sagen wir: eins.

Was passiert nun, wenn wir das Uroboros-Programm sich selbst als Eingabe füttern? Zunächst wird mit Hilfe des Halte-Test-Programms zuverlässig und eindeutig herausgefunden, ob das Programm halten wird oder nicht. Ist die Antwort ja, dann ist der nächste Schritt die unendliche Schleife – so wurde das Uroboros-Programm ja definiert. Aber dann läuft das Programm ja für immer – und wir sagten doch eben, wir hätten vom Halte-Test-Programm das Ergebnis bekommen, dass Uroboros halten würde. Umgekehrt: Wenn das Halte-Test-Programm sagt, Uroboros würde in eine unendliche Schleife gehen, dann endet das Programm ganz friedlich und gibt „eins“ aus.

„Dieser Satz ist falsch“

Das Programm endet also genau dann wenn es nicht endet. Das ist ein logischer Widerspruch. Wir haben also unter der Annahme, dass es ein Halte-Test-Programm gäbe, einen inneren Widerpruch konstruiert. Das bedeutet, dass die Annahme, es könne so ein Halte-Test-Programm überhaupt geben, falsch gewesen sein muss.

Turing konnte den Beweis mit größerem mathematischen Aufwand sauberer und präziser führen, als es in bloßen Worten darstellbar ist. Außerdem ist Turings Beweis deutlich weitreichender als dieses simple Gedankenspiel. Zentral ist aber in jedem Fall, dass man rasch auf Schwierigkeiten stößt, wenn Programme Aussagen über sich selbst machen.

Das errinert an das berühmte Paradoxon des Epimenides: „Epimenides der Kreter sagt: Alle Kreter sind Lügner.“ Stimmt dieser Satz nun? Wenn der Satz stimmt, dann ist auch Epimenides ein Lügner. Nachdem er den Satz sagt, muss der Satz dann aber falsch sein. Dann ist er aber doch kein Lügner? Die Logik war schon in der griechischen Antike ein kompliziertes Fachgebiet – und heute, im Computerzeitalter, ist sie das erst recht.

Weiterlesen...