Ein Beweis dafür, dass es mindestens ein triviales Computerprogramm gibt, das nicht existieren kann

Die schönsten mathematischen Beweise, vol. 2, Maxime Coutte.

In dem Artikel der letzten Woche ging es um "Sind einige Unendlichkeiten größer als andere?" und das Cantor Diagonal Argument. Diese Woche möchte ich eines meiner Lieblingsprobleme in der theoretischen Informatik teilen.

Ich erinnere mich, dass ich in der Mittelschule, als ich anfing, Informatik zu studieren, dachte, ich könnte theoretisch jedes Computerproblem mit den richtigen mathematischen Werkzeugen und der richtigen Programmierung lösen. Ich habe mich geirrt. Es gibt theoretische Einschränkungen für jede Rechenmaschine, und hier sehen wir den Beweis, dass es mindestens ein logisches Problem gibt, das kein Computerprogramm jemals lösen kann.

Definieren von H, dem unmöglichen Computerprogramm

Wir definieren ein Computerprogramm P (i) als eine Liste von Anweisungen P, die, wenn sie mit einer Eingabe i ausgeführt werden, eine Ausgabe o ergeben.

Zum Beispiel,

ist ein Programm, das die beiden Zahlen summiert, die Sie ihm als Eingaben geben, und

ist ein Programm, das ein anderes Programm - P_add - als Eingabe verwendet und diesem Programm die beiden anderen Eingaben übergibt. Es macht das, was P_add (a, b) macht und verdoppelt es.

Wenn ein Programm ausgeführt wird, kann es stecken bleiben, für immer ausgeführt werden und niemals etwas ausgeben. Beispielsweise fügt ein Programm P_sum, das zur Summe aller natürlichen Zahlen übergeht, für immer natürliche Zahlen hinzu, ohne jemals die Ausführung zu beenden (dh anzuhalten) und Ausgabe des Ergebnisses.

Nehmen wir nun an, dass es ein Programm H (P, i) gibt, das die Liste der Anweisungen P des Programms P (i) und i die Eingabe von P (i) als Eingabe verwendet und eine 1 ausgibt, wenn P (i) Halte irgendwann an und 0, wenn P (i) stecken bleibt und für immer rennt. Einfach gesagt,

Warum die Liste der Logikanweisungen H möglicherweise nicht vorhanden ist

Basierend auf Alan Turings Beweis in der Arbeit "Auf berechenbaren Zahlen mit einer Anwendung auf das Entscheidungsproblem" -1937 werden wir beweisen, dass H nicht existieren kann.

Basierend auf der Annahme, dass H existiert, konstruieren wir ein Programm X (P), das genau dann für immer läuft, wenn H (P, P) = 1 ist, und genau dann anhält, wenn H (P, P) = 0. Mit anderen Worten,

Wir können nun in Betracht ziehen, X (i) eine eigene Liste von Anweisungen X als Eingabe zu geben: X (X).

Daher läuft X (X) genau dann für immer, wenn H (X, X) = 1 und X (X) genau dann anhalten, wenn H (X, X) = 0. Mit anderen Worten,

Wir haben einen Widerspruch! Wir haben durch Reductio ad absurdum gezeigt, dass H nicht existieren kann, da seine Existenz zu absurden Schlussfolgerungen führt.

Daher ist ein Computerprogramm, das bestimmen kann, ob ein Computerprogramm mit einer Eingabe für immer hängen bleibt und ausgeführt wird oder die Ausführung beendet wird, unmöglich. Es gibt mindestens ein Computerprogramm, das ein logisches Problem löst, das unmöglich existieren kann.

Referenzen, Alan Turing. "Auf berechenbaren Zahlen, mit einer Anwendung auf das Entscheidungsproblem". 1937.

Ich bin Max Coutte, Mitbegründer von Relativty.com, einem VR-Headset, das ich von Grund auf neu entwickelt habe und dessen Code und Hardware ich als Open-Source-Lösung verwendet habe. Folgen Sie mir auf Twitter @maxcoutte.