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

Entscheidungsphase

In letzter Zeit habe ich ziemlich viel über Quantenphysik und eine wissenschaftliche Theorie der Willensfreiheit geschrieben. Dabei habe ich meinen Blog vor inzwischen fast genau vier Jahren begonnen, nicht um die Willensfreiheit theoretisch zu ergründen, sondern vielmehr als Hilfestellung für ihre praktische Anwendung (in Wirklichkeit ist nur beides zusammen möglich). Nur aus diesem Grund habe ich den Blog auch „willensfreiheit“ genannt. In dieser Zeit ging es mir überhaupt nicht gut. Ich war von Ängsten an meiner Existenz, an der sozialen Kontakten mit anderen, und von Schuldgefühlen geplagt. Ich sah mich als unfähig und unberechtigt an, meine Bedürfnisse gegenüber anderen zu artikulieren. Zwar sind das Themen, mit denen ich schon immer – vor dieser persönlichen Krise, aber auch danach – mehr oder weniger zu kämpfen habe bzw. hatte, aber in dieser Zeit war es besonders schlimm. Wenn man sich meine ersten Blogeinträge ansieht, kann man sich das vielleicht in etwa vorstellen, was da abging.

Eine eigene Theorie, warum ich in diese Krise hineingeraten bin, habe ich mir über die Zeit entwickelt, und ich halte sie auch bis heute für plausibel. Es war eine wichtige Umbruchszeit in meinem Leben, in der ich gerade dabei war, meine Dissertation in Physik abzuschließen. Damals standen mir in einer kurzen Zeitspanne von vielleicht vier bis sechs Monaten eine Menge möglicher Wege zur Verfügung, mein Leben weiterzuführen. Ich denke, dass mir in dieser Zeitspanne echte, relativ weitgehende Entscheidungsfreiheit zur Verfügung stand. Ich gehe nicht von der Annahme aus, dass der Mensch permanent in der Lage ist, völlig freie, undeterminierte Willensentscheidungen zu treffen. Ich glaube zwar schon, dass wir immer, zu jedem Zeitpunkt, in der Lage sind, etwas zu tun, aber es hängt sicherlich von der jeweiligen Situation ab, wie viel wir tun können, wieviel Anstrengung dafür nötig ist, und wie lange es dauert, bis Resultate spürbar werden. Die Zeiten dagegen, in denen wir wirklich weitehende Entscheidungen treffen können, sind für die meisten Menschen aber wahrscheinlich relativ selten. Gerade deshalb ist stets Achtsamkeit über die eigenen Handlungen geboten, denn es ist immer damit zu rechnen, dass eine solche Situation unerwartet wieder entstehen kann, und sich das eigene Schicksal in zwei oder mehre mögliche Wege aufspaltet, je nachdem, wie man sich entscheidet. Das ist im wesentlichen das, was ich unter „Karma“ verstehe, ein Begriff, der aus den fernöstlichen Religionen entliehen worden ist, und der meines Wissens nach in der wesltichen Philosophie keine direkte Entsprechung hat, obwohl er mit dem eher westlich geprägten Thema Willensfreiheit in engem Zusammenhang steht.

Um den Kreis wieder zu schließen: Ich glaube heute, dass ich im Jahr 2007 aufgrund unzutreffender Vorstellungen über die Welt – und über mich selbst – in einer Umbruchssituation meines Lebens in Existenzängste geraten bin, die mich wiederum dazu gebracht haben, wichtige Hinweise meiner Umwelt (die ich als Spiegel meiner seelischen Innenwelt verstehe) zu übersehen und zu überhören, was mich – schlussendlich – in eine Situation katapultiert hat, in die ich eigentlich gar nicht hinein wollte.

Bisher habe ich diese Theorie ausschließlich für mich selbst behalten; aber hier passt sie eigentlich ganz gut hin, denn wie ich eingangs schon schrieb, war der Beginn des „willensfreiheit“ Blog eine der Maßnahmen, die ich im Folgejahr 2008 unternahm, um aus dieser sich äußerst beschissen anfühlenden Situation wieder herauszukommen (Das ist irgendwie typisch für mich: erst dann aktiv werden, wenn´s allzu brenzlig wird…). Allmählich begannen die Maßnahmen dann auch zu wirken: Zunächst verschwanden die Angstzustände und das Gefühl, mit der Situation ganz alleine zu sein. Dann besserte sich das Gefühl der Unsicherheit, und inzwischen auch weitgehend die Zweifel bezüglich meiner Berufswahl.

Heute ist mein Leben ein völlig anderes als zu der Zeit bevor der entstandenen Krisensituation. Eine völlig andere Familiensituation; eine andere Stadt; und statt der Quantenphysik beschäftige ich mich jetzt beruflich mit dem Klima – ein wesentlich politischeres Thema als das erstere (wer weiß, vielleicht wird es damnächst einmal genau umgekehrt sein…). Die meisten meiner früheren Hobbys sind dieser Krisensituation zum Opfer gefallen. Ich habe bisher nicht mehr die Zeit und die Gelegenheit, sie wieder aufzunehmen. Vermutlich hätte ich es einfacher haben können, hätte ich in der Entscheidungsphase im Jahr 2007 besser auf mein Herz statt auf mein Ego gehört – und auf die Vorschläge einige meiner Freunde.

Eine solche Erkenntnis ist eine Gratwanderung: Sich einerseits selbst einzugestehen, dass man für seine eingene Situation in einer bestimmten Weise selbstverantwortlich ist, andererseits aber auch nicht in Selbstvorwürfe zu verfallen (ich neige zu letzterem). Und selbst wenn man es hinkriegt, hier den richtigen Weg zu gehen, gibt einem niemandem das Recht, über andere zu urteilen, die durch ihren freien Willen in eine schwierige Situation geraten sind. „Eigenverantwortlich“ (der Kampfbegriff des Neoliberalismus schlechthin) ist man nur gegenüber sich selber, anderen gegenüber ist man entweder verantwortungsvoll oder verantwortungslos.