Halteproblem

Auf blog.de gibt es im Autorenbereich die Möglichkeit, zu sehen, mit welchen Suchbegriffen der eigene Blog gefunden wurde. Lustigerweise ist der häufigste Suchbegriff bei mir „Widerspruchsbeweis“ und verlinkt auf einen Eintrag, in dem ich irgendwann einmal den Beweis des Euklid brachte, dass es unendlich viele Primzahlen gibt. Keine Ahnung, ob es sich dabei um Schüler oder Studenten handelt, die nach Hinweisen für ihre Mathe-Hausaufgabe googeln, oder ob das irgenwelche Bots sind, die das Netz aus welchen Gründen auch immer nach diesem Wort durchkämmen… Diese Beobachtung soll jedenfalls als Vorgeschichte dienen, an dieser Stelle einen weiteren typischen Widerspruchsbeweis zu diskutieren, der zwar über 2000 Jahre jünger ist, als der des Euklid, aber von nicht minder wichtiger Bedeutung.

Der besagte Beweis geht auf den britischen Pionier des Computerzeitalters Alan Turin zurück und gibt die Antwort auf das sogenannte „Halteproblem für Registermaschinen“. Was zu Turings Zeit noch eine „Registermaschine“ war, ist für unser heutiges Verständnis von Computern ein Stück Software – ein Computerprogramm. Was macht ein Computerprogramm? Nun, es liest eine gewissen Menge an Daten ein, führt eine Reihe von Rechenoperationen aus, gibt etwas aus – oder auch nicht, und hält irgendwann an, in der Programmiersprache FORTRAN z.B. durch einen STOP-Befehl. Oder auch nicht: Es könnte auch in einer Endlosschleife ewig weiterlaufen und niemals anhalten. Wichtig ist, dass jedes Computerprogramm selbst auch nur aus einer bestimmten Menge an Daten besteht, die von dem Prozessor des Computers interpretiert werden.

Woher weiß man, ob ein gegebenes Programm, das eine gegebene Menge an Daten einliest, jemals anhalten wird oder nicht? Zunächst einmal kann man es einfach einmal eine begrenzte Zeit lang laufen lassen, dann weiß man zumindest, ob es in dieser Zeit anhalten wird, oder nicht. Falls es aber nicht anhält, woher weiß man, ob es irgendwann später einmal anhalten wird? Unter der guten Annahme, dass wir nur endlich viel Wartezeit zur Verfügung haben, und der Computer nur endlich viel Speicherplatz, der irgenwann einmal vollgeschrieben werden könnte, können wir auf diese Weise nicht für alle Programme entscheiden, ob es anhalten wird oder nicht. Man müsste sich also etwas anderes einfallen lassen. Manchen Programmen sieht man leicht an, dass sie in eine Endlosschleife geraten, andere muss man schon genauer analysieren, um das zu erkennen, und wieder andere sind zu kompliziert, um jemals erkennen zu können, ob sie anhalten oder nicht. Wünschenswert wäre ein Computerprogramm, das andere Compterprogramme analysiert und als Resultat ausgeben kann, ob es bei einer gegebenen Eingabe anhält oder nicht. Das ist genau das Halteproblem: Ist es möglich, ein solches Programm zu schreiben?

Selbst auf die Gefahr hin, die Spannung zu früh wegzunehmen, sei hier schon einmal das Ergebnis vorweggenommen: Die Antwort ist nein. Wie es sich für einen guten Widerspruchsbeweis gehört, gehen wir zunächst von der gegenteiligen Annahme aus: In diesem Fall also, dass es eine Programm gibt, dass entscheiden kann, ob ein beliebiges gegebenes anderes Progamm, dass einen gegebenen Datensatz einliest, anhalten wird, oder ohne Ende weiterlaufen wird. Im Prinzip künnte dieses Programm in jeder Programmiersprache geschrieben sein. Wegen meine Vorliebe für FORTRAN 90 würde ich es in dieser Sprache implementieren und den Quellcode z.B. in einer Datei „halteproblem.f90“ speichern. Mit einem FORTRAN-Compiler kann ich mir daraus ein ausführbares Programm „halteproblem.exe“ erzeugen. Wenn ich jetzt ein beliebiges anderes ausführbares Programm „test.exe“ habe, das einen Datensatz einliest, der in einer Datei namens „input.dat“ gespeichert ist, kann halteproblem.exe entscheiden, ob test.exe anhalten wird oder nicht: halteproblem.exe ist so programmiert, dass es ein ausführbares Programm einliest, das es testen soll, sowie alle Dateien, die das zu testende Programm als Eingabe einliest. Ich lasse halteproblem.exe also die Dateien test.exe einlesen, worauf es automatisch auch input.dat einliest. Als Ausgabe schreibt halteproblam.exe entweder „test.exe hält an“, oder entsprechend „test.exe hält niemals an“ auf den Bildschirm.

Es gibt keinen Grund, warum ich nicht dann nicht die folgende Manipulation vormehmen könnte: Ich könnte halteproblem.f90 in eine Datei halteproblem_mod.f90 kopieren und so modifizieren, dass das Programm, anstatt „test.exe hält an“ auszugeben, absichtlich in eine Endlosschleife läuft. Wenn ich den FORTRAN Code compiliere und das entstandene ausführbare Programm halteproblem_mod.exe auf test.exe anwende, bekomme ich nun entweder die Ausgabe „text.exe hält niemals an“ wenn test.exe tatsächlich niemals anhalten wird, oder halteproblem_mod.exe läuft ohne Ausgabe weiter, ohne jemals abzubrechen, falls test.exe irgendwann anhält.

Als nächster Beweisschritt kommt die entscheidende Tatsache ins Spiel, dass ein jedes Computerprogramm selbst auch nur ein Haufen von Daten ist, der von einem anderen Programm – aber auch von sich selbst – eingelesen werden kann. Wir bekommen es also mit dem interessanten Problem der Rückbezüglichkeit zu tun. Was passiert, wenn ich halteproblem_mod.exe sich selbst einlesen lasse? Dann muss das ursprüngliche Programm halteproblem.exe zunächst einmal so geschickt programmiert sein, dass es sich selbst nur ein einziges mal einliest. Ansonsten würde es sich unendlich oft einlesen, denn es liest sich selber als ein Programm ein, dass sich wiederum selber einliest, dass sich selber einliest, u.s.w.. Doch selbst dann, wenn es so schlau ist, dass es diese Endlosschleife erkennt und sich selbst nur ein einziges Mal selbst einliest (sogar das ist im Prinzip gar nicht nötig, denn beim Ausführen des Programms ist es ja schon im Speicher des Computers), ergibt sich ein Problem: Nämlich bei der Frage, ob halteproblem_mod.exe bei der Anwendung auf sich selbst anhalten wird, oder nicht. Ewig weiterlaufen kann es nicht, denn es ist ja so programmiert, dass es dann bei der Anwendung auf sich selbst mit der Ausgabe „halteproblem_mod.exe hält niemals an“ anhalten würde – ein Widerspruch. Anhalten kann es aber auch nicht, denn es ist so programmiert, dass es dann bei der Anwendung auf sich selbst in eine Endlosschleife geraten und ewig weiterlaufen würde – auch ein Widerspruch: Das Programm halteproblem_mod.exe kann also weder anhalten, noch nicht anhalten – was natürlich Quatsch ist, woraus zu folgern ist, dass es nicht existiert. Daraus folgt weiter, dass auch das ursprüngliche Programm halteproblem.exe nicht existieren kann, dann würde es existieren, könnte man daraus durch die beschriebene Modifikation auch halteproblem_mod.exe erhalten. Das Halteproblem ist damit unlösbar – zumindest für ein Computerprogramm. Was zu beweisen war.

Natürlich ist das soweit kein strenger mathematischer Beweis, sondern eher das, was man üblicherweise als Beweisskizze bezeichnet. Einen strengen Beweis des Halteproblems kann man in handelsüblichen Lehrbüchern über mathematische Logik finden, aber für den interessierten Laien, der – wie z.B. ich – weder den Nerv noch die Zeit haben, ein solches Lehrbuch durchzuackern, ist es vielleicht gut zu wissen, dass man es auch so verstehen kann.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s