Arbitrary Turing machine run time analysis on the empty word

Question

Consider $L = \{ \langle M,n \rangle : M $ accpets $\epsilon $ in less than $T(n)$ steps$\}$

This language is decidable because a decider can simulate $M$ on $\epsilon$ and accept if it accepts and reject if it rejects or passed more than $T(n)$ steps.

The decider above will run in $O(T(n)log(T(n)))$ time corresponding to simulation time bounds (maybe even $O(T(n))$ has been achieved for simulation time of $T(n)$ steps)

but since we are dealing with a constant word, might it have a better simulation time? $o(T(n))$?

Answer 1

The $\log T(n)$ factor in the analysis stems from the need to keep (and update) a step counter, in binary, that goes up to $T(n)$. This requires $\log(T(n))$ cells, and the need to update it (or rather, to drag it along on the tape) costs $\log(T(n))$ in every iteration.

Now, if you could avoid this for $\epsilon$, then you could avoid it for an arbitrary input word $w$, by modifying the given TM $M$ to a new TM $M'$ that first writes $w$ on the tape, and then simulates $M'$ for $T(n)+|w|$ steps on $\epsilon$.

Since $T(n)$ is super-linear, this would contradict the best known lower bounds.

Note that this does not prove that a better simulation is not possible, only that the word $\epsilon$ plays no special role.

In fact, however, you could prove that $o(T(n))$ is not achievable, by tweaking slightly the Time Hierarchy Theorem