Halteproblem

Das „Halteproblem“ beschäftigt sich mit zwei verschiedenen Fragen, die differenziert betrachtet werden sollten.

1. Kann man bei einer Turingmaschine immer vorhersehen, was eine Turingmaschine in der Zukunft machen wird, unter der Voraussetzung, dass die Turingmaschine während sie ausgeführt wird bereits Zugriff auf dieses Ergebnis hat? (Berechnung innerhalb des Models der Turingmaschine)
2. Kann man bei einer Turingmaschine immer anhand des Programmcodes prüfen, ob sie jemals halten wird? (Berechnung außerhalb des Modells der Turingmaschine)

Antworten:

1. Nein. Ein solches Orakel ist nicht möglich. Dies wäre ein Widerspruch im Modell.
2. Ja bei allen, aber nicht bei allen Programmen in absehbarer Zeit.

Dass sich das Halteproblem mit dem Halten des Programms und nicht mit der Ausgabe des Textes „grün“ beschäftigt, ist völlig willkürlich, wurde aber vermutlich deshalb verwendet, da Informatiker dachten, damit die Lösung gefunden zu haben, warum sie immer wieder Endlosschleifen programmieren.

Nun zur ersten Frage. Um diese Frage zu lösen, ist hier ein Gleichnis zu finden:

Eines Tages kam ein Wanderer zu einem Orakel. Von diesem ist bekannt, dass es einen jeden Wanderer in seinen gesamten elementaren Bestandteilen so gut untersuchen kann, dass es daraus dessen Zukunft vorhersehen kann. Dieses fragte der Wanderer: „Werde ich jemals auf einem Esel reiten?“ Der Wanderer aber glaubt nicht an das Orakel und setzt alles daran, dessen Vorhersage nicht Wirklichkeit werden zu lassen.

Sollte das Orakel sagen, dass er nie auf einem Esel reiten wird, so würde er dies sogleich tun. Würde es das Gegenteil sagen, so würde er künftig Esel meiden. Das Orakel müsste übermenschliche Kräfte haben, um sein Schicksal in seinem Sinne verlaufen zu lassen.

Dass keine Haltemaschine, welche das Halten vorhersehen kann, (Frage 2) gefunden werden kann wird häufig mit folgendem Gegenbeispiel (Widerspruchsbeweis) begründet. In Wirklichkeit wird aber Frage 1 beantwortet.

H ist die Haltemaschine, welche prüft, ob das Programm hält.
Falls dies der Fall ist wird „wahr“ ausgegeben, ansonsten „falsch“.

T ist Turingmaschine:
  wenn H(b(T)) ist wahr
    dann halte nicht an
  wenn H(b(T)) ist falsch
    dann halte an

Das Programm macht also immer das Gegenteil von dem, was vorhergesagt wird. Dadurch kann nicht vorhergesehen werden, ob das Programm halten wird und damit wird das Programm auch nicht lauffähig sein, da es diese Prüfung zwingend benötigt. Die Beweise werden aber nicht so einfach wie hier gemacht, sondern meist unnötig verkompliziert.

Ein Programm mit bekannten Anweisungen, bei dem auch alle Anweisungen der Programme, auf die es zugreift, bekannt sind, ist genau dann nicht vorhersehbar, wenn es Zufall verwendet oder die nötige Berechnung zu viel Zeit benötigen würde. Nur dann. Es ist unmöglich ein System zu erschaffen, welches innerhalb einer kurzen Zeit zu einem Ergebnis kommt und keinen Zufall verwendet, aber nicht vorhersehbar ist.

Kommt in einem Programm, dass innerhalb von einer absehbaren Zeit zu Ende gerechnet hat, also nicht die Funktion Random() oder eine unvorhersehbare Funktion Magic(), dessen Programmcode unbekannt ist, vor, ist es es auch vorhersehbar. Wenn es rekursiv seine eigene Vorhersehbarkeit abfragen würde, um damit ähnlich dem Gleichnis mit dem Orakel dieses zu hintergehen, so wird die Vorhersehbarkeits-Abfrage eine Abfrage auf sich selber finden und das ganze Programm abstürzen lassen, sodass durch die höheren Kräfte des Vorhersehbarkeits-Programm das Vorhersehbarkeits-Programm recht behält. Man könnte natürlich auch ein fehlerhaftes Vorhersehbarkeitsprogramm verwenden, welches ein falsches Ergebnis auswirft. Würde man diesen ganzen Vorgang dann aber mit einem richtigen Vorhersehbarkeitsprogramm untersuchen, würde man herausfinden, dass das ganze Programm inklusive dem falschen Vorhersehbarkeitsprogramm vorhersehbar ist.

Bei dem Gedankenspiel ist zu beachten, dass alles, was in der Turingmaschine abläuft, auch nur in der Turingmaschine abläuft und keinen Anspruch hat, die eigenen Regeln außerhalb des zu beobachtenden Modells zu ändern. Nur weil in der Turingmaschine ein defektes Programm zur Vorhersehbarkeit läuft, darf das nicht bedeuten, dass wir in der Beurteilung der Vorhersehbarkeit der Turingmaschine beeinträchtigt werden.

Vorhersehbarkeit bei Max Planck

Max Planck führt an, dass sobald jemand die Zukunft kennen würde, er diese auch jemanden anderen erzählen können, der sich deshalb anders verhält, sodass diese Zukunft nicht eintritt. Dabei bezieht sich diese Art der Vorhersehbarkeit auf das Universum und nicht auf ein bestimmtes Programm, welches man von außen betrachten kann.