1
$\begingroup$

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))$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0

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.