Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
That's a good question. What have you tried so far? What is the performance of the best simulation you could think of? – Yuval Filmus Jan 23 '13 at 18:14
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. – Kumar Jan 24 '13 at 5:07
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? – Yuval Filmus Jan 24 '13 at 5:27
Does Universal simulation of Turing machines answer your question? – Kaveh Jan 30 '13 at 4:29
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. – Raphael Dec 6 '14 at 9:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.