# Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a deterministic UTM can simulate another deterministic TM with running time $t(n)$ in time $t(n)\log(t(n))$.

My question is: why is there a $\log(t(n))$ slowdown in the simulation of a deterministic TM by a UTM, as opposed to a constant factor slowdown in the nondeterministic case?

• Have you tried looking at the proofs of these simulations? If what you're stating is correct, then some trick that works for nondeterministic machines doesn't work for deterministic ones. – Yuval Filmus Feb 23 '14 at 19:10

## 1 Answer

Please refer to the answer in the similar question, "Why is simulation by non deterministic Turing machine faster than a deterministic one?".

Basically, in the non-deterministic universal Turing machine we guess the contents of the tape and check if the guess is correct later on. This allows us to save time going to and fro in the work tape.