# Universal Turing Machine simulation with bounded time overhead

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?

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