12
$\begingroup$

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?

Improve this question
$\endgroup$
29
$\begingroup$

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.)

Improve this answer
$\endgroup$
  • 11
    $\begingroup$ 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) $\endgroup$ – Alexander Aug 4 '16 at 16:06
  • 1
    $\begingroup$ @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) $\endgroup$ – John Dvorak Aug 5 '16 at 7:06
  • $\begingroup$ 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. $\endgroup$ – user56834 Aug 6 '16 at 8:23
  • $\begingroup$ @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. $\endgroup$ – David Richerby Aug 6 '16 at 11:20
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

To add on to David Richerby's answer:

If it were true that no self-modifying algorithms can't be modeled by non-self-modifying algorithms, then those algorithms would have to be executed on something that's also self-modifying. It'd have to be turtles all the way down.

As I mentioned in my comment, a self-modifying algorithm can be executed on a processor that itself abides by the rules of a static algorithm (encoded in its design) which "tells" it how to execute machine instructions.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I think that might be an interesting dividing line. I think one could argue that "life" is a self-modfying algortihm that can't be modeled by non-self-modifying algorithms, but then again, "life" is typically not thought of as an algorithm. $\endgroup$ – Cort Ammon Aug 4 '16 at 19:09
  • 2
    $\begingroup$ @CortAmmon: If we view "life" as an algorithm, then what is its input and its output? How could one prove that any equivalent algorithm (meaning, any algorithm that produces the same output when given the same input) must be self-modifying? $\endgroup$ – ruakh Aug 4 '16 at 21:47
  • $\begingroup$ @ruakh If I were to argue that life was a self modifying algorithm, the inputs would be itself, and its outputs would be itself. Proving that it can't be reduced to a non self-modifying algorithm would be trickier, but I think it is a popular hypothesis. After all, how many people want to believe they can be reduced to an algorithm that can run on a computer? $\endgroup$ – Cort Ammon Aug 4 '16 at 21:52
  • 1
    $\begingroup$ @CortAmmon: I can't be reduced to an algorithm that runs on a computer because that algorithm is no longer "me"; I am more than my inputs and outputs. But if we start from the assumption that I am just an algorithm, then tacking on "that can run on a computer" doesn't actually change anything. Re: "If I were to argue that life was a self modifying algorithm, the inputs would be itself, and its outputs would be itself": In that case I think you would be veering well outside CS, and dangerously close to crackpottery. $\endgroup$ – ruakh Aug 4 '16 at 21:58
  • 1
    $\begingroup$ @CortAmmon A program that outputs itself given itself as input is just cat. (No pun intended, even though cats happen to be living things) $\endgroup$ – user253751 Aug 5 '16 at 1:06
1
$\begingroup$

Of course you can unwind self modifying code to some sort of semantic equivalent version. However, self modifying code where timing and external state or internal cache behavior is part of what influences the output CANNOT be represented except by anything beyond perhaps a good high level description language with a compiler or translator that can take that description back to its binary original.

If the output of a Turing machine is the entire state at each step, the sequence itself would be impossible to replicate even though this requires an alternative definition of a TM to capture these hidden practical states.

Furthermore forgetting these issues, the question of whether a given self modifying code can be unrolled in P time or P space is hardly proven. It could be that removing all self modifying code causes an exponential blow up in program size. It's also the case that optimal Kolnogorov complexity might only be achievable via self modifying code. So the fact that it can theoretically be unrolled in all cases, says nothing about its impact on complexity, nor does it work in a practical environment which has micro instruction timing, cache issues, or even external clock type sensitivity which is measurable with modern processors very easily. It would be easy to make hand written assembly that detects if it is in it's original form verse a unwound form using several different techniques. Modern processors are highly complex state machines and effectively cannot be strictly modeled as TMs as there is no way to model an input tape that has external stimuli with such a primitive theoretical model. Immediately we must step into non deterministic or probabilistic TMs and NP or worse complexity

Improve this answer
New contributor
Gregory Morse is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.