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?

$\endgroup$
0

4 Answers 4

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

$\endgroup$
4
  • 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, 2016 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$ Aug 5, 2016 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, 2016 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$ Aug 6, 2016 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.

$\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.

$\endgroup$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 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$ Aug 5, 2016 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 Kolmogorov 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

$\endgroup$
2
  • $\begingroup$ Well, even then it can: it can be executed by a simulator that takes care to be timing-accurate for all of that behavior. It might be very difficult to build such a simulator from an engineering perspective but is certainly possible. I disagree that it is impossible to replicate; it is merely difficult or expensive. $\endgroup$
    – D.W.
    Jan 19, 2021 at 17:43
  • $\begingroup$ Actually you cannot simulate real world clock time exactly , theoretical impossibility. Even network traffic, real world of course can be approximated. So your simulator will introduce artificial and approximations. Real world is the key here. You can prove pretty easily though its maybe a narrow practical case, that you can not model self modifying code without having undesirable effects on these things. The theory is simply not resolving with the practical, regardless of how hard you try to do so. And we can theoretically model my argument and prove it generally $\endgroup$ Jan 20, 2021 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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