I would like to know if there is a turing machine which can do the following:

take as input a turing machine T and integer n:
return true if the turing machine halts before time n and false otherwise

Clearly such a TM (turning machine) exists. Take the TM that simply runs T for n steps, then if it has halted return true and return false otherwise, however what I would like to know is if there exists a TM that can do better than this. I'm not sure how to formalize this question exactly. so hopefully it is clear what I am asking. Thanks

  • 2
    $\begingroup$ What do you mean by "better"? Do you mean "faster"? $\endgroup$ – xskxzr Feb 26 at 3:57

Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear_speedup_theorem)

Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$. These Turing Machines would basically run $k$ steps of the original TM as $1$ step, hence having more state space, but linearly faster.

Was this your question?

| cite | improve this answer | |

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.