# determine if a turing machine halts in less than n step, in less than n step

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

• What do you mean by "better"? Do you mean "faster"? – xskxzr Feb 26 at 3:57

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.