10
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 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$ – Yuval Filmus Jan 23 '13 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 '13 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$ – Yuval Filmus Jan 24 '13 at 5:27
  • 2
    $\begingroup$ Does Universal simulation of Turing machines answer your question? $\endgroup$ – Kaveh Jan 30 '13 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 '14 at 9:36

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.