Dinge, Die Computer Niemals Tun können

Philip J. Erdelsky
Erstveröffentlichung in Dr. Dobbs Journal im Mai 1987

Bitte senden Sie Kommentare, Korrekturen und Ergänzungen per E-Mail an den Webmaster unter [email protected].

Jeder, der die enormen Verbesserungen bei Computern in den letzten 40 Jahren miterlebt hat, kann den Eindruck gewinnen, dass Computer irgendwann in der Lage sein werden, jedes genau festgelegte Problem zu lösen. Fortschritte beim Sprachverstehen und bei anderen Formen der künstlichen Intelligenz waren enttäuschend, aber die menschliche Sprache ist voller Unklarheiten. Das ist also kein genau definiertes Problem. Schach hingegen ist sehr gut definiert. Obwohl es früher als Inbegriff intelligenter Aktivität galt, können Computer heute besser Schach spielen als alle anderen, bis auf wenige menschliche Spieler.

Einige Probleme sind zwar klar definiert, aber zu groß, um sie selbst auf unseren größten Computern in angemessener Zeit zu lösen. Aber wenn ein Computer von allen zeitlichen und speicherlichen Einschränkungen befreit werden könnte, könnte er dann doch ein genau definiertes Problem lösen?

Die überraschende Antwort auf diese Frage, die den Mathematikern schon vor dem Bau der ersten echten Computer bekannt war, lautet Nein. Es gibt einige Dinge, die kein Computer jemals tun kann, weil bewiesen werden kann, dass es keine Algorithmen gibt, um sie zu tun – so wie es keine Möglichkeit gibt, einen Kreis mit einem Kompass und einem Lineal zu quadrieren.

Diese Dinge sind keine bloßen mathematischen Kuriositäten. Das sind Dinge, die Programmierer gerne von ihren Computern erledigen lassen möchten, und Dinge, die die Anbieter von Software-Entwicklungstools gerne in ihre Debugger integrieren möchten. In den Lehrplänen der Informatik werden in der Regel nicht berechenbare Funktionen behandelt, aber Programmierer, die keine Hauptfachleute der Informatik sind, fragen manchmal nach dem Unmöglichen, ohne es zu bemerken.

Alan Turing fragte 1935, ob es eine Methode gibt, mit der ein Computerprogramm bestimmen kann, ob ein anderes Computerprogramm anhält. Dies ist das berühmte “Halteproblem”. Turing hat gezeigt, dass es keine Lösung gibt.

Ein Debugger mit dieser Fähigkeit wäre sicherlich nützlich. Normales Anhalten ist eine häufige Form von Programmfehlern. Darüber hinaus könnte der Debugger nacheinander auf Teile des fehlgeschlagenen Programms angewendet werden, um den Teil zu isolieren, der aufhängt.

Es ist nicht offensichtlich, dass ein solcher Debugger unmöglich ist. Natürlich kann der Debugger das Programm nicht einfach in einem Schritt starten, um festzustellen, ob es anhält. Wenn das Programm nicht angehalten wird, kann der Debugger für immer ausgeführt werden, ohne dass dies der Fall ist. Oder es gibt auf, gerade als das Programm gerade beendet wird, wie es menschliche Programmierer manchmal tun. Irgendwann müsste der Debugger sagen können: “Aha! Diese Schleife ist unendlich!” Es scheint, als ob ein geschickt geschriebener Debugger, der über alle Werkzeuge moderner Hochsprachen verfügt, in der Lage wäre, dies zu tun.

Der Unmöglichkeitsnachweis beruht auf folgendem Argument. Wenn Sie einen Debugger haben, der das Problem des Anhaltens aufgrund der unbegrenzten Zeit und des unbegrenzten Speichers lösen kann, können Sie denselben Code verwenden, um den Debugger andere Dinge ausführen zu lassen, von denen einige widersprüchlich und daher unmöglich sind.

Die jeweilige Computersprache ist nicht wichtig. Wenn Sie das Halteproblem für eine Sprache lösen können, können Sie es für eine andere lösen. Verwenden Sie einfach einen Compiler oder ein anderes Übersetzungsprogramm, bevor Sie das Problem lösen. Beachten Sie, dass das Übersetzen eines Assembler-Programms in eine höhere Sprache recht einfach ist, obwohl das Objektprogramm ineffizient sein muss. Ziel ist es jedoch zu zeigen, dass eine Lösung des Halteproblems nicht nur ineffizient, sondern unmöglich ist.

Turing selbst schlug eine Minimalmaschine vor, die Turingmaschine genannt wird. Sein Speicher sollte unendlich lang sein, aber nur ein Bit breit, und die Maschine hatte nur sequentiellen Zugriff darauf, wie bei einem Band. Die Programmiersprache war im Wesentlichen ein Flussdiagramm mit nur wenigen grundlegenden Befehlen. Trotzdem zeigte Turing, dass seine Maschine mit genügend Zeit und einem geeigneten Programm jede andere Maschine emulieren konnte. Eine solche Konstruktion ist für unsere Zwecke nicht erforderlich – Sie können sich vorstellen, dass der Computer in einer vertrauten Hochsprache programmiert ist.

Betrachten Sie nun das Problem, festzustellen, ob ein Programm eine bestimmte Zeichenfolge S (mit oder ohne andere Ausgabe) ausdrucken kann. Wenn Sie das Halteproblem lösen können, können Sie dieses Problem lösen. Ersetzen Sie einfach jede Druckanweisung im Programm durch eine Routine, die die Ausgabe nicht an den Drucker sendet, sondern die Ausgabe verfolgt und anhält, wenn die Zeichenfolge S angezeigt wird. Ersetzen Sie anschließend alle Halt-Anweisungen im Programm durch Endlosschleifen, um zu verhindern, dass das Programm aus einem anderen Grund angehalten wird. Lösen Sie dann das Halteproblem für das Ergebnis.

Ein solches Programm wäre an sich nützlich, da viele Laufzeitfehler unterschiedliche Meldungen erzeugen, und es wäre hilfreich, vorherzusagen, dass solche Fehler auftreten werden.

Da dies für jeden String S gilt, können Sie auch bestimmen, ob ein Programm eine Kopie von sich selbst druckt. Das ist nicht so merkwürdig, wie es auf den ersten Blick erscheint. Es ist einfach, ein Programm mit 1.000 Zeichen zu schreiben, das alle Kombinationen von 1.000 Zeichen einschließlich der eigenen ausgibt. Tatsächlich sind 1.000 Zeichen wahrscheinlich eine Überschätzung der Anzahl der in den meisten Hochsprachen erforderlichen Zeichen.

Jetzt können Sie ein Programm schreiben, um die folgenden Dinge zu tun. Generieren Sie zunächst nacheinander alle möglichen Programme. Der einfachste Weg, dies zu tun, besteht darin, alle Zeichenfolgen zu generieren und zu überprüfen, ob es sich um ein Programm handelt. Compiler tun dies, wenn sie die Syntax überprüfen. Überprüfen Sie dann jedes Programm, um festzustellen, ob es eine Kopie von sich selbst druckt. Drucken Sie abschließend eine Kopie jedes Programms aus, das keine Kopie von sich selbst druckt.

Dieses Programm, das gerade alle Programme generiert, generiert sich schließlich von selbst. Druckt es eine Kopie von sich selbst aus? In diesem Fall wird die Regel verletzt, indem eine Kopie eines Programms gedruckt wird, das eine Kopie von sich selbst druckt. Wenn dies nicht der Fall ist, wird die Regel dadurch verletzt, dass keine Kopie eines Programms gedruckt wird, das keine Kopie von sich selbst druckt. Dieser fatale Widerspruch beweist, dass das Stopp-Problem keine Lösung hat.

Sie können dies als Russells Paradoxon (die Menge aller Mengen, die sich nicht selbst enthalten) oder als das Friseurparadoxon (der Friseur, der jeden Mann rasiert, der sich nicht selbst rasiert) erkennen.

Jedes Problem, das ein Debugger in das Problem des Anhaltens umwandeln kann, z. B. das Problem der Zeichenfolgenausgabe, ist ebenfalls nicht lösbar. Einige andere offensichtliche Beispiele sind:

  1. Feststellen, ob ein Programm einen bestimmten Punkt erreicht (Ada-Programmierer: Aus diesem Grund muss PROGRAM_ERROR ein Laufzeitfehler und kein Kompilierungsfehler sein)
  2. Bestimmen, ob eine Variable initialisiert wird, bevor sie verwendet wird
  3. Bestimmen, ob ein bestimmtes Codesegment nicht zugänglich ist und niemals ausgeführt wird
  4. Bestimmen, ob zwei Programme dasselbe tun

Natürlich kann ein Debugger oder Compiler solche Fehler manchmal vorhersagen – zum Beispiel kann manchmal unzugänglicher Code zum Zeitpunkt der Kompilierung identifiziert werden. Universelle Lösungen für solche Probleme gibt es jedoch nicht.

Die Unmöglichkeit festzustellen, ob zwei Programme dasselbe tun, bedeutet, dass es immer möglich ist, eine bestimmte Art von Trojaner zu besiegen. In einem in den Notices of the ACM (August 1984) abgedruckten Vortrag argumentierte Ken Thompson, er könne ein trojanisches Pferd in einen C-Compiler einbinden, der die Login-Anweisung falsch kompiliere, um auf jedes damit kompilierte Unix-System zugreifen zu können Kompilieren Sie den C-Compiler nicht, um eine Kopie von sich selbst einzufügen. Der Trojaner selbst würde nicht im Quellcode des C-Compilers erscheinen. In einem Brief an den Herausgeber bemerkte Steve Draper, dass ein solches trojanisches Pferd besiegt werden kann, indem der C-Compiler paraphrasiert wird (indem ein anderer Code geschrieben wird, der dasselbe tut) und dann neu kompiliert wird. Kein Trojanisches Pferd kann paraphrasierte Programme unfehlbar erkennen – daher gibt es immer eine Paraphrase, die das Trojanische Pferd besiegt.

Meine eigene Meinung in dieser Angelegenheit ist, dass die meisten Paraphrasen es besiegen würden, wenn das Trojanische Pferd nicht geschickt geschrieben worden wäre, und in der Tat würde es wahrscheinlich irgendwann durch normale Softwarewartung besiegt werden. Jedes trojanische Pferd, das intelligent genug ist, die meisten Paraphrasen zu erkennen, wäre wahrscheinlich viel größer als der Rest des C-Compilers. Sie würden es nie durch die Tore bekommen.

Das Stopp-Problem hängt eng mit zwei anderen Problemen zusammen, die der Mathematiker David Hilbert 1900 aufstellte. Gibt es für jede mathematische Aussage einen formalen Beweis oder einen Disproof? Gibt es einen Algorithmus, um Beweise zu finden?

Die erste Frage wurde 1931 von Kurt Gödel verneint. Gödels Beweis war komplex, aber wenn Sie die Unlösbarkeit des Halteproblems akzeptieren, kann dies einfach bewiesen werden. Ob ein bestimmtes Programm anhält, ist eine mathematische Aussage. Tatsächlich sind viele mathematische Theoreme bereits Spezialfälle des Halteproblems, da Sie ein Programm schreiben können, um nach Gegenbeispielen zu suchen und anzuhalten, wenn es eines findet. Der Satz entspricht der Behauptung, dass das Programm niemals anhält.

Wenn die Behauptung, dass ein Programm anhält, immer formal bewiesen oder widerlegt wurde, könnten Sie einfach alle Beweise (mehr oder weniger so wie das zuvor beschriebene Programm alle Programme erzeugt hat) erstellen, bis Sie entweder einen Beweis oder einen Widerspruch gefunden haben. Das würde das Halteproblem lösen. Da das Stopp-Problem im Allgemeinen nicht lösbar ist, muss es mindestens eine solche mathematische Aussage geben, die nicht zu entscheiden ist – das heißt, sie kann nicht formal bewiesen oder widerlegt werden.

Dies zeigt, dass es im Allgemeinen unmöglich ist zu beweisen, dass ein Programm funktioniert. Es kann nachgewiesen werden, dass bestimmte Programme oder eingeschränkte Programmklassen bestimmte Aufgaben ausführen. Dies ist jedoch nicht für jedes Programm möglich.

Gibt es angesichts der Tatsache, dass einige mathematische Aussagen unentscheidbar sind, ein Programm, das “Entscheidbarkeitsprogramm”, das erkennen kann, ob eine mathematische Aussage entscheidbar ist, auch ohne zu entscheiden, ob sie wahr oder falsch ist? Wie Sie vielleicht aus dem Ton dieses Artikels erraten haben, lautet die Antwort erneut nein. Wenn Sie ein Entscheidbarkeitsprogramm haben, können Sie jedes Programm nehmen und fragen, ob es anhält. Wenden Sie dann das Entscheidbarkeitsprogramm auf diese Frage an. Wenn die Frage entscheidbar ist, wird eine Suche nach allen Beweisen dies beweisen oder widerlegen. Wenn die Frage unentscheidbar ist, hält das Programm niemals an. Andernfalls können Sie beweisen, dass es anhält, indem Sie es einfach so lange ausführen, bis es anhält.

Daher können Theorembeweisungsprogramme, wie erfolgreich sie auch in begrenzten Bereichen sein mögen, niemals alles beweisen. Manche Dinge müssen immer außer Reichweite bleiben.

Diese Argumente sind im mathematischen Sinne nicht streng, weil zu viel weggelassen wurde. Ein wesentlicher Teil von Turings und Gödels Arbeit bestand in der Formalisierung der Begriffe “Berechnung” und “Beweis” bis zu dem Punkt, an dem ihre Argumente von Mathematikern akzeptiert würden.

Möglicherweise haben Sie bereits eine implizite Annahme entdeckt, die nicht der Realität entspricht. Die Programme sind nicht an Speicherbeschränkungen gebunden. Wenn ein Programm eine Speicherbegrenzung hat, kann das Problem des Anhaltens theoretisch gelöst werden – aber nur durch ein Programm mit einem viel größeren Speicher.

So kann es gemacht werden. Ein Programm mit einer Speicherbegrenzung hat nur eine begrenzte Anzahl von Zuständen. Ein Debugger kann es in einem Schritt ausführen und dabei die Status verfolgen, die es besetzt hat. Wenn es vor dem Anhalten zweimal denselben Zustand einnimmt, wiederholt es die gleiche Abfolge von Zuständen auf unbestimmte Zeit und hört nie auf.

Zu diesem Zweck benötigt der Debugger genügend Speicher, um zu verfolgen, welche Zustände das Programm belegt hat. Für jeden möglichen Zustand ist nur ein Bit erforderlich, aber die Anzahl der möglichen Zustände selbst für ein einfaches Programm ist wirklich umwerfend. Jede Kombination von Bits im Speicher ist ein anderer Zustand. Daher hat ein Programm mit nur 1.024 Bytes Speicher allein aufgrund der Speicherkonfiguration mindestens 2 (1024 x 8) Zustände, von Flags und Registern ganz zu schweigen. Diese Anzahl von Flip-Flops würde nicht in das gesamte bekannte Universum passen. Man kann daher sagen, dass das Halteproblem auch in diesem Fall keine Lösung hat.

Es sollte daher klar sein, dass der künstlichen Intelligenz definitiv Grenzen gesetzt sind und dass die Arbeit von Mathematikern und Programmierern niemals vollständig automatisiert werden kann. (Das ist ein großer Trost für mich, weil ich Mathematiker und Programmierer bin.

Nur perfekte Lösungen sind jedoch unmöglich. Es kann immer noch argumentiert werden, und es wird von einigen argumentiert, dass Programme für künstliche Intelligenz schließlich in der Lage sein werden, jedes Problem, das der menschliche Verstand lösen kann, mit mindestens der gleichen Erfolgsrate zu lösen. Und wenn die einzige Anforderung praktische Lösungen sind, nicht perfekte, dann können viele interessante, aber theoretisch unlösbare Probleme gelöst werden.


Hinterlasse eine Antwort