"Den gesamten Code in einer gegebenen Binärdatei zu finden, entspricht dem Halting-Problem." Wirklich?

Das Halteproblem für Finite-State-Maschinen ist lösbar (obwohl es viele Lebensdauern benötigen könnte ... des Universums ) und jede Maschine, die Sie emulieren könnten, ist eine endliche Zustandsmaschine. Führen Sie einfach das Programm aus, und die Anzahl der Schritte wird durch die Anzahl der möglichen Zustände begrenzt. Wenn diese Zahl überschritten wird, ohne anzuhalten, wird das Programm niemals angehalten, da es sich in einer Schleife befinden muss.

Praktisch gesehen ist es viel einfacher, den gesamten Code zu finden, es sei denn, der Code kann berechnete gotos verwenden. Anstatt den Code auszuführen, nehmen Sie einfach alle Zweige genau einmal an jedem möglichen Verzweigungspunkt.

Ich stimme Larsman zu, und ich glaube, das Argument kann präzisiert werden. Zuerst muss ich zustimmen, dass "das Auffinden des gesamten Codes in einer gegebenen Binärdatei" in diesem Kontext bedeutet, dass es eine einzige berechenbare Funktion hat, die bestimmt, welche Bytes innerhalb einer eingegebenen Binärdatei den ausgeführten Anweisungen entsprechen.

EDIT: Wenn jemand nicht klar ist, warum es hier ein Problem gibt, denken Sie an verschleierten Maschinencode. Die Zerlegung eines solchen Codes ist ein nicht-triviales Problem. Wenn Sie die Disassemblierung mitten in einer Multi-Byte-Anweisung beginnen, erhalten Sie eine falsche Disassemblierung. Dies bricht nicht nur die fragliche Anweisung, sondern typischerweise einige Anweisungen darüber hinaus. usw. hineinschauen. (zum Beispiel Google "Verschleierung und Demontage").

Skizze der Strategie, um dies zu präzisieren:

Definieren Sie zuerst ein theoretisches Computer- / Maschinenmodell, in dem ein Programm in binären Multibit-Anweisungen codiert ist, ähnlich wie Maschinencode auf "echten" Computern, aber präzise gemacht wird (und so, dass es vollständig ist). Angenommen, die Binärdatei codiert das Programm und alle Eingaben. Dies muss alles genau gemacht werden, aber angenommen, dass die Sprache eine (binär codierte) Halteanweisung hat, und dass ein Programm anhält, wenn und nur wenn es eine Haltanweisung ausführt.

Nehmen wir als erstes an, dass die Maschine den Programmcode nicht ändern kann, aber über einen Speicher verfügt, in dem sie arbeiten kann. (angenommen in interessanten Fällen unendlich).

Dann steht jedes gegebene Bit entweder am Anfang eines Befehls, der während der Ausführung des Programms ausgeführt wird, oder nicht. (zB kann es in der Mitte einer Anweisung oder in Daten oder "Junk-Code" sein - das heißt Code, der nie laufen wird. Beachten Sie, dass ich nicht behauptet habe, dass diese sich gegenseitig ausschließen, wie zum Beispiel eine Sprunganweisung kann ein Ziel haben, das in der Mitte eines bestimmten Befehls ist, wodurch ein anderer Befehl erzeugt wird, der "beim ersten Durchgang" nicht wie ein ausgeführter Befehl aussieht.).

Definieren Sie ins (i, j) als die Funktion, die 1 zurückgibt, wenn die binäre i eine Anweisung hat, die an der Bitposition j beginnt und die in einer Ausführung des von i codierten Programms ausgeführt wird. Definieren Sie ins (i, j) andernfalls als 0. Nehmen wir an, dass ins (i, j) berechenbar ist.

Lassen Sie halt_candidate (i) das folgende Programm sein:

Da wir den oben beschriebenen selbst-modifizierenden Code nicht zulassen, ist es für ein Programm nur möglich, dass ein Haltbefehl an einer Position j, die ausgeführt wird, vorliegt. Mit dem Entwurf berechnet halt_candidate (i) die Haltefunktion.

Dies liefert eine sehr grobe Skizze einer Richtung des Beweises. wenn wir annehmen, dass wir testen können, ob Programm i eine Anweisung an Position j für alle j hat, dann können wir die Haltefunktion kodieren.

Für die andere Richtung muss man einen Emulator der formalen Maschine innerhalb der formalen Maschine kodieren. Erstellen Sie dann ein Programm plus die Eingänge i und j, die das Programm i emulieren, und wenn ein Befehl an der Bitposition j ausgeführt wird, gibt er 1 zurück und hält an. Wenn irgendeine andere Anweisung ausgeführt wird, läuft sie weiter, und wenn die Simulation jemals eine "Halt" -Funktion in i simuliert, springt der Emulator zu einer Endlosschleife. Dann ist ins (i, j) gleichbedeutend mit halt (Emulator (i, j)), und so impliziert das Halteproblem das Fehlercode-Problem.

Natürlich muss man annehmen, dass ein theoretischer Computer dem bekannten unlösbaren Halteproblem gleichkommt. Andernfalls ist das Halteproblem für einen "echten" Computer lösbar, aber unlösbar.

Für ein System, das selbst modifizierenden Code erlaubt, ist das Argument komplexer, aber ich erwarte das nicht anders.

EDIT: Ich glaube, ein Beweis im selbstmodifizierenden Fall wäre, einen Emulator des System-plus-selbst-modifizierenden Codes in dem obigen statischen Code plus Datensystem zu implementieren. Das Anhalten mit selbstmodifizierendem Code, der für das Programm i mit den Daten x zulässig ist, ist das gleiche wie das Anhalten des obigen statischen Code plus Datensystems, wobei die Binärdatei den Emulator, i und x als Code plus Daten enthält.