Ein Beweis, 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 Argument der Cantor-Diagonale. Diese Woche möchte ich eines meiner Lieblingsprobleme der theoretischen Informatik vorstellen.

Ich erinnere mich, als ich in der Mittelschule anfing, Informatik zu studieren, dachte ich, dass ich theoretisch jedes Computerproblem mit den richtigen mathematischen Werkzeugen und der richtigen Programmierung lösen könnte. Ich lag falsch. Es gibt theoretische Beschrä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, die Sie eingeben, summiert.

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 laufen 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 die Ausführung jemals zu beenden (dh anzuhalten) und Ergebnis ausgeben.

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) halt irgendwann an und 0 wenn P (i) stecken bleibt und ewig läuft. Einfach gesagt,

Warum die Liste der Logikanweisungen H möglicherweise nicht existiert

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.

Ausgehend von 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 dann anhält, wenn H (P, P) = 0. Mit anderen Worten,

Wir können nun erwägen, X (i) eine eigene Liste von Anweisungen X als Eingabe zu geben: X (X).

Daher läuft X (X) für immer, wenn und nur wenn H (X, X) = 1 und X (X) anhalten, wenn und nur 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 bei einer Eingabe hängen bleibt und für immer ausgeführt wird oder die Ausführung beendet, nicht möglich. Es gibt mindestens ein Computerprogramm, das ein Logikproblem löst, das möglicherweise nicht existiert.

Referenzen, Alan Turing. "Über berechenbare Nummern, mit einer Bewerbung zum Entscheidungsproblem". 1937.

Ich bin Maxime Coutte, Mitbegründer von Relativty.com, einem VR-Headset, das ich von Grund auf neu entwickelt habe und für das ich den Code und die Hardware als Open-Source-Lösung bereitgestellt habe. Ich lerne sehr gerne und interessiere mich für eine Vielzahl von Themen.
Du kannst mir auf Twitter @maximecoutte folgen.