Suche in der Bibliothek
A B C D E F G H I J K L M N O P Q R S T U V W X Ü Y Z Ö

HALTEPROBLEM   
Das Haltproblem entsteht aus der Frage, ob ein Computer die Ausführung eines Programms mit einem bestimmten Input irgendwann beendet oder ohne zusätzliche Einwirkung bzw. Steuerung in einer Endlosschleife verbleibt (vgl. dazu die Abhandlung von Christian Maurer unter Link ).

Dieses Problem beschrieb erstmals Alan Turing im Jahr 1936 und bewies, dass es unlösbar ist. Genau das ist das Interessante am Halteproblem, denn es zeigt – im weitesten Sinn vergleichbar mit Heisenbergs Unschärferelation in der Atomphysik –, dass es prinzipiell unlösbare Probleme der wissenschaftlichen Logik gibt. Es kann, um es anders zu sagen, grundsätzlich (und nicht wegen mangelnder Daten, Formeln oder Rechenleistungen) niemals ein allgemeiner Algorithmus gefunden werden, der das Problem für jedes denkbare Programm löst. Das Halteproblem ist ein Beispiel der Informationstechnik für das Gödel-Theorem, das die Grenzen der Logik und damit letztlich auch der so zu gewinnenden Erkenntnis oder Wahrheit aufzeigt.

In diesem Sinn spielt das Halteproblem eine indirekte Rolle für die Im Spiegel der Möglichkeiten aufgeworfenen Fragen um Realität und Virtualität und darf natürlich auch gern mit den imaginären, simulierten Welten, die dort andiskutiert werden, ganz unmittelbar in Verbindung gebracht werden: Man kann die Frage, ob das Programm anhalten wird, nicht theoretisch lösen, sondern nur, indem man das Programm mit dem betreffenden Input laufen lässt. Solange es aber läuft, kann man nicht wissen, ob es irgendwann einmal in endlicher Zeit anhalten wird. Es geht einem so ähnlich wie mit Schrödingers Katze, die so lange halb lebt und halb tot ist, bis wir nachsehen. Nur: Bricht man das Programm ab, dann kann der Beweis überhaupt nicht erbracht werden. – Ich denke, das ist auch ein schönes Gleichnis für das Programm namens Evolution, ohne hier weiter auf die in den Abenteuern angerissene ethische Konsequenz eingehen zu wollen.

Unter dem Aspekt der Evolution und damit dem Spiel von Zufall und Notwendigkeit sei aber noch eines vermerkt: Eine Verallgemeinerung des Halteproblems gibt es in der algorithmischen Komplexitätstheorie mit den sog. nicht-berechenbaren Zahlen: Man wird nie beweisen können, ob eine bestimmte Reihenfolge von Ziffern zufällig ist. – Wie steht es mit der Determiniertheit oder Zufälligkeit in der Abfolge der Evolutionsschritte?

So weit wie Lars Frantzen, der das Halteproblem gut erklärt und dann religiös interpretiert (Link ), möchte ich nicht gehen. Gern zitiere ich aber einen Gedanken zu dem Extropier Hans Moravec aus dem »Lexikon der Zukunft« (Link ): »Das Halteproblem dürfte ein wichtiges Problem für den Robotiker Moravec werden, wenn er es schaffen sollte, sein Gehirn auf einen Rechner auszuschütten. Denn wer garantiert, daß der Algorithmus von Moravec nicht in eine Endlosschleife übergeht und seine Software niemals wieder irgendwelche Aussagen macht, nachdem er sich vom Menschen zum Bit-Haufen transformiert hat?«

  Portal

Computer
Turing
Unschärferelation
Schrödingers Katze
Logik
Gödels Theorem
Erkenntnis
Wahrheit
Realität
virtuell
Zeit
Ethik
Evolution
Zufall
Notwendigkeit

Ureda

Impressum / Haftungshinweis Ureda © 2002K.-J. Durwen