Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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. –  Anjali Vijaya 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
It's the other way around, you should explain how your solution gets around this difficulty. –  Yuval Filmus Jan 25 '13 at 17:32
Does Universal simulation of Turing machines answer your question? –  Kaveh Jan 30 '13 at 4:29
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.