The halting-after-$n$ steps problem may be defined as the question if a given turing machine halts after a maximum of $n\in\mathbb{N}$ steps. Is it theoretically possible to solve this problem in general in less than $n$ execution steps (just execution the program) or can't this be done? If not, why not?
Thank you
The time hierarchy theorem, or rather its proof, gives some answer to this question. If you look at the proof, you should get a lower bound of $\Omega(n/\log n)$.
In more detail, consider the language $L$ of all triples $\langle M,x,1^t \rangle$ such that $M$ halts on $x$ after at most $t$ steps. Suppose that this can be solved in time $f(n)$, where $n$ is the input length (which is $t + |M| + |x|$). Then you can construct a Turing machine which on input $\langle x,1^t \rangle$ determines whether $\langle x,x,1^t \rangle \in L$, if so runs into an infinite loop, otherwise halts. When run on itself as input, this machine either halts in time $f(t + O(1)) + O(1)$ or never halts. Hence if $f(t + O(1)) + O(1) \leq t$, we reach a contradiction. This shows that $f$ has to essentially be at list linear.
