Kann jeder selbstmodifizierende Algorithmus durch einen nicht selbstmodifizierenden Algorithmus modelliert werden?

Wenn wir ein beliebiges Computerprogramm haben, das seine Anweisungen ändern kann, ist es möglich, dieses Programm mit einem Programm zu simulieren, das seine Anweisungen nicht ändern kann?

Bearbeiten:

Ich bin neu in StackExchange, also nicht sicher, ob ich hier eine NEUE Frage stellen darf, aber hier ist: Ok, der Beweis, dass es möglich ist, ist wirklich sehr einfach, wie ihr gezeigt habt. Nun frage ich mich: Gibt es Probleme, bei denen es effizienter (und inwieweit) ist, den effizientesten selbstmodifizierenden Algorithmus zu verwenden, um das Problem zu lösen, im Vergleich zu dem Eingabe-Ausgabe-äquivalenten effizientesten nicht selbstmodifizierenden Algorithmus?

computability computation-models turing-completeness church-turing-thesis user56834
quelle

Antworten:

Ja es ist möglich. Sie können das Programm simulieren, indem Sie einen Interpreter für die Sprache verwenden, in der es geschrieben wurde. Jetzt ist das Programm (der Interpreter) festgelegt, und das, was früher ein selbstmodifizierendes Programm war, sind jetzt die Daten des Interpreters.

Insbesondere könnten Sie durchaus eine universelle Turing-Maschine haben, mit der der TM, den er simuliert, seine eigene Beschreibung ändern kann. (Die Beschreibung der simulierten Maschine, meine ich; nicht die UTM.)

David Richerby
quelle

Sie brauchen nicht einmal den hypothetischen Dolmetscher. Eine CPU, die Ihren selbstmodifizierenden Algorithmus ausführt, ist selbst eine Maschine, die einen festen Algorithmus ausführt (der vorschreibt, wie Befehle ausgeführt werden)

Alexander - Reinstate Monica

@AlexanderMomchliov Es gibt CPUs, die Teile ihres Befehlssatzes im laufenden Betrieb ändern können (aber die Idee ist die gleiche - der programmierbare Teil sind Daten, der Mikrocontroller, auf dem er ausgeführt wird, ist der Interpreter - obwohl er auf einen Mikrocontroller in einer FPGA-Zelle verweist könnte knifflig sein)

John Dvorak

um zu antworten: "Sie könnten durchaus eine universelle Turing-Maschine haben, mit der der TM, den er simuliert, seine eigene Beschreibung ändern kann." Ich denke: ist das nicht die Frage? denn jetzt müssen Sie noch beweisen, dass das simulierte TM den selbstmodifizierenden Algorithmus tatsächlich modellieren kann, oder? Es kann immer noch vorkommen, dass es ein sich selbst modifizierendes Programm gibt, das KEINE Turing-Maschine ist. Daher können wir die Turing-Vollständigkeit nicht verwenden, um zu zeigen, dass sie simuliert werden kann, da sich die Turing-Vollständigkeit auf die Simulation von TMs und die sich selbst modifizierende Maschine bezieht algo ist kein TM.

user56834

@ Programmer2134 Es stellt sich überhaupt nicht die Frage. Unabhängig davon, auf welcher CPU Sie Ihr selbstmodifizierendes Programm ausführen, kann ich diese CPU auf einer Turing-Maschine simulieren. Um es anders zu erklären, das ursprüngliche Programm ist eine endliche Folge von Anweisungen, von denen einige das Programm selbst modifizieren. Jeder der Befehle kann von der UTM simuliert werden, jeder der Modifikationen kann simuliert werden und jeder der modifizierten Befehle kann simuliert werden. In keiner Phase dieses Prozesses geht etwas über die Leistung von Turing-Maschinen hinaus.

David Richerby

Jedes Turing-complete-Rechenmodell ohne Änderungscode (oder "Code") dient als Beweis für diese Aussage. Ich weiß nicht , dass jede der Standardmodelle (TM, RAM, ...) Sie haben Code zu modifizieren, so dass wir nicht zu weit zu suchen.

Kompilieren Sie aus einem solchen Modell (und stellen Sie sicher, dass der Compiler keine Code-Änderung vornimmt), um ein Programm in der gewünschten Sprache zu erhalten.

Dies ist natürlich ein existenzielles Argument: Es gibt ein äquivalentes Programm. Wir wissen aber auch, dass es zwischen zwei beliebigen Turing-vollständigen Sprachen rekursive (dh berechenbare) Compiler gibt, so dass Sie ein Programm der gewünschten Form (gelesen: in der gewünschten Sprache) erhalten.

Raphael
quelle

So ergänzen Sie die Antwort von David Richerby :

Wenn es wahr wäre, dass keine selbstmodifizierenden Algorithmen durch nicht selbstmodifizierende Algorithmen modelliert werden können, müssten diese Algorithmen auf etwas ausgeführt werden, das sich auch selbstmodifiziert. Es müssten Schildkröten sein.

Wie ich in meinem Kommentar erwähnt habe, kann ein selbstmodifizierender Algorithmus auf einem Prozessor ausgeführt werden, der sich selbst an die Regeln eines statischen Algorithmus (der in seinem Entwurf kodiert ist) hält, der ihm "sagt", wie Maschinenbefehle auszuführen sind.

Alexander - Setzen Sie Monica wieder ein
quelle

Ich denke, das könnte eine interessante Trennlinie sein. Ich denke, man könnte argumentieren, dass "Leben" ein selbstmodifizierender Algorithmus ist, der nicht durch nicht selbstmodifizierende Algorithmen modelliert werden kann, aber andererseits wird "Leben" normalerweise nicht als Algorithmus angesehen.

Cort Ammon

@CortAmmon: Wenn wir "Leben" als Algorithmus betrachten, was ist dann seine Eingabe und seine Ausgabe? Wie kann man beweisen, dass jeder äquivalente Algorithmus (dh jeder Algorithmus, der bei gleicher Eingabe dieselbe Ausgabe erzeugt) selbstmodifizierend sein muss?

Ruakh

@ruakh Wenn ich behaupten würde, das Leben sei ein selbstmodifizierender Algorithmus, wären die Eingaben sich selbst und die Ausgaben sich selbst. Zu beweisen, dass es nicht auf einen nicht selbstmodifizierenden Algorithmus reduziert werden kann, wäre schwieriger, aber ich denke, es ist eine populäre Hypothese. Wie viele Menschen möchten sich auf einen Algorithmus beschränken, der auf einem Computer ausgeführt werden kann?

Cort Ammon

@CortAmmon: Ich kann nicht auf einen Algorithmus reduziert werden, der auf einem Computer ausgeführt wird, da dieser Algorithmus nicht mehr "ich" ist. Ich bin mehr als meine Ein- und Ausgänge. Aber wenn wir von der Annahme ausgehen, dass ich nur ein Algorithmus bin , ändert das Anheften von "das auf einem Computer laufen kann" eigentlich nichts. Betreff: "Wenn ich behaupten würde, das Leben sei ein selbstmodifizierender Algorithmus, wären die Eingaben sich selbst und die Ausgaben sich selbst."

Ruakh

@CortAmmon Ein Programm, das sich selbst als Eingabe ausgibt, ist gerecht cat. (Kein Wortspiel beabsichtigt, obwohl Katzen Lebewesen sind)

user253751