While defining the following time hierarchy theorem (for deterministic case ) :If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$The $\log$ factor comes due to the overhead of simulation by universal Turing machine, as the universal Turing machine has only one head. But what if the universal Turing machine uses same number of tapes and tape heads as some Turing machine $M$, when $<M,x>$ is given as an input to it ? Does the $log$ factor vanish ? Am I missing something ?
Why is universal turing machine considered with only one head?
complexity theory;turing machines;computation models;simulation
There are two (related) answers to your question. The first answer is that the time complexity classes are traditionally defined using one-head Turing machines. For the diagonalization argument to work, we need the simulating machine to be of the same kind as the simulated machines.The second answer is that even if you consider time complexity classes defined using $N>1$ heads, then you are going to encounter a similar problem with the universal Turing machine who only has $N$ heads but has to simulate both the original $N$ heads and to read the program. (It could be that the performance hit is not as bad for more than one head.) Making the number of heads finite but unbounded will make things even worse, since the universal Turing machine has a fixed number of heads.