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$ Apr 29 '19 at 17:56
  • $\begingroup$ Why does a single tape have to be worse? You're simulating something simpler, so it should be easier. $\endgroup$ Apr 29 '19 at 18:15
  • $\begingroup$ @EmilJe The Wikipedia page says O(k log k steps), I too don't know why. $\endgroup$ Apr 30 '19 at 3:44
  • 1
    $\begingroup$ Has it been proven optimal? See the time-hierarchy theorem. $\endgroup$ Apr 30 '19 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$ Apr 30 '19 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.