2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ If the UTM is allowed many heads, so are the machines it simulates... $\endgroup$ – Yuval Filmus Feb 19 '16 at 9:39
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.