# Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions?

Edit:

I am new to stackexchange so not sure if I'm allowed to ask a NEW question here, but here goes: Ok so the proof that it is possible is actually really simple as you guys have shown. Now, I am wondering: Are there problems for which it is more efficient (and to what extent) to use the most efficient self-modifying algorithm to solve the problem, versus the input-output-equivalent most efficient non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying program is now the interpreter's data.

In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its own description. (The description of the simulated machine, I mean; not the UTM.)

• You don't even need the hypothetical interpreter. A CPU executing your self-modifying algorithm is itself a machine that executes a fixed algorithm (which dictates how it executes instructions) – Alexander - Reinstate Monica Aug 4 '16 at 16:06
• @AlexanderMomchliov there exist CPUs that can modify parts of their instruction set on the fly (but yes, the idea is the same - the programmable part is data, the microcontroller that runs it is the interpreter - though pointing to a microcontroller inside an FPGA cell might be tricky) – John Dvorak Aug 5 '16 at 7:06
• to respond to: "you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its own description." I'm thinking: doesn't this beg the question? because now you still need to prove that the TM that is being simulated can actually model the self-modifying algorithm, right? It could still be the case that there is a self-modifying program that is NOT itself a Turing machine, so we cannot use Turing completeness to show that it can be simulated, since Turing completeness relates to the simulation of TM's and the self-modifying algo is not a TM. – user56834 Aug 6 '16 at 8:23
• @Programmer2134 It doesn't beg the question at all. Whatever CPU you think you're running your self-modifying program on, I can simulate that CPU on a Turing machine. To explain it in a different way, the initial program is a finite sequence of instructions, some of which happen modify the program itself. Each of the instructions can be simulated by the UTM, each of the modifications can be simulated, and each of the modified instructions can be simulated. There's nothing, at any stage of this process, that gets beyond the power of Turing machines. – David Richerby Aug 6 '16 at 11:20

Any Turing-complete computational model that does not have modifying code (or "code") serves as a proof of that statement. I don't know that any of the standard models (TM, RAM, ...) do have modifying code, so we don't have to look too far.

To get a program in whatever language you have in mind, compile from such a model (and make sure that the compiler does not introduce code modification).

This is, of course, an existential argument: there is an equivalent program. But we also know that there are recursive (i.e. computable) compilers between any two Turing-complete languages, so that is how you get a program of the form (read: in the language) you want.

• @CortAmmon A program that outputs itself given itself as input is just cat. (No pun intended, even though cats happen to be living things) – user253751 Aug 5 '16 at 1:06