Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original running-time of $M$, where $\Gamma$ and $Q$ are the tape alphabet and states of $M$ respectively?

If so, how can this be done?

  • 1
    $\begingroup$ That's a good question. What have you tried so far? What is the performance of the best simulation you could think of? $\endgroup$ Jan 23, 2013 at 18:14
  • $\begingroup$ If we try to encode one character of input on UTM it takes log|T| bits. similarly for states also we can do this. then for each transition on original TM, UTM takes log|T|+log|Q| steps. Is my arguments are correct. $\endgroup$
    – Kumar
    Jan 24, 2013 at 5:07
  • 2
    $\begingroup$ The UTM has to simultaneously read the "program" (the Turing machine it's simulating) and the "data" (the tape that the simulated Turing machine operates on). How do you handle that? $\endgroup$ Jan 24, 2013 at 5:27
  • 2
    $\begingroup$ Does Universal simulation of Turing machines answer your question? $\endgroup$
    – Kaveh
    Jan 30, 2013 at 4:29
  • $\begingroup$ How do you look up the value of the transition function in time $o(|\Gamma|\cdot|Q|)$? At least I don't see how to encode said table in that space and TMs don't have random access. That may be a naive thought, but still. $\endgroup$
    – Raphael
    Dec 6, 2014 at 9:36


Your Answer

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

Browse other questions tagged or ask your own question.