Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape.

We can build a Turing machine $U$ that accepts a (reasonable) binary representation of a Turing machine $M$ and simulates it (possibly doing additional computation before and/or after the simulation).

Such concept of simulation is used massively and in different contexts (e.g. in the proof of the time hierarchy theorem).

I'm wondering if there is a formal definition of "simulation" (or different definitions) and when such definition(s) appeared for the first time.

Something like "Given a description $p$ of $M$, $U$ on input $p$ simulates $M$ if during the computation there is a one-to-one mapping between the internal state of $U$ and the internal state of the simulated $M$, and between the content of the work tape of $U$ and the simulated work tape of $M$"

Note 1: as commented by Zonko we could use this definition: "Given a description $p$ of $M$, $U$ simulates $M$ if $U(p,x)=M(x)$, $\forall x$ accepted by $M$"; but if $U(p,x)=M(x)+1$ then probably $U$ needs to "simulate" $M$ as well.

  • $\begingroup$ How about "Given a description $p$ of $M$, $U(p,x) = M(x)$, $\forall x$ accepted by $M$. $\endgroup$ – Zonko Sep 11 '17 at 22:06
  • $\begingroup$ I'm confused. Isn't that just a universal TM? $\endgroup$ – Raphael Sep 12 '17 at 5:52
  • $\begingroup$ @Zonko: in my interpretation of "simulation" we could also have $U(p,x) = M(x)+1$ and $U$ in this case simulates $M$ as well. I slightly edit the question to reflect this note. $\endgroup$ – Vor Sep 12 '17 at 6:47
  • $\begingroup$ @Raphael: yes, it must "embed" the power of an Universal Turing machine in some sense. UTMs are generarlly used in a broader context, while "simulation" also on narrower contexts; e.g. on restricted classes of Turing machines (polynomial time, deciders, ...) ... I'm only searching if there is a formal definition of such "in some sense" in the literature :-) (e.g. the one-to-one state/tape correspondence) $\endgroup$ – Vor Sep 12 '17 at 7:14
  • $\begingroup$ I think I'd define that a computation $U(y)$ simulates computation $M(x)$ if there is a subsequences of configurations during $U(y)$ that, mapped with a configuarion-compiler, is the sequences of configurations of $M(x)$. But that's just a spontaneous thought; I don't think I've ever seen such a definition. $\endgroup$ – Raphael Sep 12 '17 at 8:43

Your Answer

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

Browse other questions tagged or ask your own question.