3
$\begingroup$

According to source page 20, theorem 1.9, it states that there is a universal Turing machine that can simulate any Turing machine with a time overhead of $O(\log n)$.

Can a universal Turing machine exists with less overhead? Can we prove that no such universal Turing machine exists?

If not, can we at least prove a lower bound on the overhead?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I believe it is an open question. $\endgroup$ – Yuval Filmus Apr 6 '17 at 18:27
  • $\begingroup$ @Yuval What about if we restrict a UTM to simulating another UTM. Is it then still an open question? $\endgroup$ – Anon21 Apr 6 '17 at 18:30
  • 1
    $\begingroup$ This isn't really well-defined. $\endgroup$ – Yuval Filmus Apr 6 '17 at 18:30
  • $\begingroup$ related $\endgroup$ – Ariel May 2 '18 at 7:15

Your Answer

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

Browse other questions tagged or ask your own question.