Halteproblem

Das Halteproblem ist ein Problem der Informatik. Das Problem besteht darin, sich ein Computerprogramm anzusehen und herauszufinden, ob das Programm für immer läuft oder nicht. Wir sagen, dass ein Programm "das Halteproblem löst", wenn es sich ein anderes Programm ansehen und herausfinden kann, ob dieses andere Programm ewig läuft oder nicht.

Zum Beispiel ein Programm wie dieses:

obwohl wahr: weitermachen;

wird sich für immer in einer Schleife drehen, aber das Programm

während Falsch: weiter;

stoppt sehr schnell.

Gibt es ein Programm, das das Stopp-Problem löst? Es stellt sich heraus, dass es keins gibt. Wir beweisen diese Tatsache, indem wir zeigen, dass, wenn es ein Programm gibt, das das Halteproblem löst, etwas Unmögliches geschieht. Im Moment werden wir also so tun, als gäbe es wirklich ein Programm, das das Halteproblem löst. Hier ist P eine Funktion, die die Funktion F (aufgerufen mit dem Argument I) auswertet und wahr zurückgibt, wenn sie ewig läuft, und sonst falsch.

def P(F, I): wenn F(I) für immer läuft: return True; sonst: return False;

P kann sich jedes Programm ansehen und herausfinden, ob es für immer läuft oder nicht. Wir benutzen P, um ein neues Programm zu erstellen, das wir Q nennen. Was Q tut, ist, sich ein anderes Programm anzusehen und dann die folgende Frage zu beantworten: "Wenn wir dieses Programm ausführen und es auf eine Kopie von sich selbst schauen lassen, wird es dann für immer laufen? Wir können Q machen, weil wir P haben. Alles, was wir tun müssen, ist Q anzuweisen, ein neues Programm zu erstellen, das das alte Programm ist, das auf sich selbst schaut, und dann mit P herauszufinden, ob das neue Programm ewig läuft oder nicht.

def Q(F): Rückgabe P(F, F);

Jetzt machen wir ein anderes Programm R. R schaut sich ein anderes Programm an und fragt Q nach seiner Antwort zu diesem Programm. Wenn Q antwortet: "Ja, wenn wir dieses Programm ausführen und dafür sorgen, dass es sich eine Kopie von sich selbst ansieht, wird es für immer laufen", dann hört R auf. Wenn Q antwortet: "Nein, wenn wir dieses Programm ausführen und dafür sorgen, dass es sich eine Kopie von sich selbst ansieht, wird es nicht ewig laufen", dann tritt R in eine Endlosschleife ein und läuft ewig.

def R(F): wenn Q(F): zurückkehren; //andere beenden: während Wahr: weitermachen; //für immer in der Schleife bleiben

Nun schauen wir uns an, was passiert, wenn wir R auf eine Kopie von sich selbst schauen lassen. Zwei Dinge können passieren: Es wird entweder anhalten oder für immer laufen.

Wenn das Ausführen von R und das Anzeigen einer Kopie von sich selbst nicht für immer läuft, antwortete Q: "Ja, wenn wir dieses Programm ausführen und es auf eine Kopie von sich selbst schauen lassen, wird es für immer laufen". Aber Q sagte dies, als er sich R selbst ansah. Was Q also tatsächlich sagte, ist: "Ja, wenn wir R ausführen und es auf eine Kopie von sich selbst schauen lassen, wird es ewig laufen". Also: Wenn R, das auf einer Kopie von sich selbst läuft, nicht für immer läuft, dann läuft es für immer. Das ist unmöglich.

Wenn die Ausführung von R und das Anzeigen einer Kopie von sich selbst für immer läuft, dann antwortete Q: "Nein, wenn wir dieses Programm ausführen und es auf eine Kopie von sich selbst schauen lassen, wird es nicht für immer laufen". Aber Q sagte dies, als er sich R selbst ansah. Was Q also tatsächlich sagte, ist: "Nein, wenn wir R ausführen und es eine Kopie von sich selbst betrachten lassen, wird es nicht ewig laufen". Also: Wenn R, das auf einer Kopie von sich selbst läuft, ewig läuft, dann läuft es nicht ewig. Auch das ist unmöglich.

Ganz gleich, was passiert, wir bekommen eine unmögliche Situation. Wir haben etwas falsch gemacht, und wir müssen herausfinden, was es war. Die meisten Dinge, die wir getan haben, waren nicht falsch. Wir können nicht sagen, dass es falsch ist, "ein Programm dazu zu bringen, auf eine Kopie von sich selbst zu schauen", oder dass es falsch ist, "sich anzuschauen, was ein anderes Programm gesagt hat, und dann in eine Schleife zu geraten, wenn es eine Sache gesagt hat, und aufzuhören, wenn es eine andere Sache gesagt hat". Es macht keinen Sinn zu sagen, dass es uns nicht erlaubt ist, diese Dinge zu tun. Das einzige, was wir getan haben, das so aussieht, als ob es falsch sein könnte, ist, dass wir so getan haben, als ob ein Programm wie P überhaupt existiert. Und da dies das Einzige ist, was falsch sein könnte, und etwas falsch sein muss, ist dies das Einzige, was falsch sein kann. Das ist der Beweis, dass ein Programm wie P nicht existiert. Es gibt kein Programm, das das Halteproblem löst.

Dieser Beweis wurde 1936 von Alan Turing gefunden.

Fragen und Antworten

Q: Was ist das Halting-Problem?

A: Das Halting-Problem ist ein Problem in der Informatik, bei dem es darum geht, ob ein Computerprogramm ewig laufen wird oder nicht.

F: Woher wissen wir, ob ein Programm das Halteproblem löst?

A: Wir sagen, dass ein Programm "das Halteproblem löst", wenn es ein beliebiges anderes Programm betrachten und feststellen kann, ob dieses andere Programm ewig läuft oder nicht.

F: Kann man beweisen, dass es kein solches Programm gibt?

A: Ja, indem man zeigt, dass, wenn es ein solches Programm gäbe, etwas Unmögliches passieren würde. Dieser Beweis wurde von Alan Turing im Jahr 1936 erbracht.

F: Was macht P?

A: P ist eine Funktion, die eine andere Funktion F (die mit dem Argument I aufgerufen wird) auswertet und wahr zurückgibt, wenn sie ewig läuft, und andernfalls falsch.

F: Was macht Q?

A: Q schaut sich ein anderes Programm an und beantwortet dann die Frage, ob die Ausführung desselben Programms in einer Endlosschleife endet oder nicht. Dazu verwendet es P, um eine Auswertung der gegebenen Funktion F vorzunehmen.

F: Was macht R?

A: R schaut sich ein anderes Programm an und fragt Q nach seiner Antwort für dieses Programm. Wenn Q antwortet: "Ja, wenn wir dieses Programm ausführen und es eine Kopie von sich selbst ansehen lassen, wird es ewig laufen", dann hält R an. Wenn Q jedoch antwortet: "Nein, wenn wir dieses Programm ausführen und es eine Kopie von sich selbst ansehen lassen, wird es nicht ewig laufen", dann tritt R in eine Endlosschleife ein und läuft ewig.

F: Was passiert, wenn Sie R dazu bringen, sich selbst zu betrachten?

A: Zwei Dinge können passieren - entweder bleibt R stehen oder läuft ewig - aber beide Ergebnisse sind unmöglich, wenn man bedenkt, was für Programme wie P bewiesen wurde, die nicht existieren.