Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps.

Wikipedia's page on EXPTIME-complete says it takes O(k) time but the page on universal Turing machines says O(k log k) on a multitape machine which only implies a single tape machine might do even worse.

Am I mixing things up? What is the best known bound for the given problem? Is it provably optimal? If not, what is the best bound that probably cannot be beaten?

Thanks for clearing this long standing doubt

  • $\begingroup$ I don’t see where the $\log k$ comes from, but there definitely has to be some dependence on $|M|$. $\endgroup$ – Emil Jeřábek Apr 29 at 17:56
  • $\begingroup$ Why does a single tape have to be worse? You're simulating something simpler, so it should be easier. $\endgroup$ – Peter Shor Apr 29 at 18:15
  • $\begingroup$ @EmilJe The Wikipedia page says O(k log k steps), I too don't know why. $\endgroup$ – ghosts_in_the_code Apr 30 at 3:44
  • 1
    $\begingroup$ Has it been proven optimal? See the time-hierarchy theorem. $\endgroup$ – Peter Shor Apr 30 at 10:54
  • 1
    $\begingroup$ Um ... it proves it optimal up to a $\log$ factor in almost all realistic cases (time-constructible running times). $\endgroup$ – Peter Shor Apr 30 at 10:57

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.