19 February 2011

*This post is inspired by the question Are runtime bounds in P decidable? asked by John Sidles on the CSTheory website, and the answer given by Emanuele Viola.*

Is there an automatic procedure to determine whether a given Turing machine, *known* to be halting, operates within time bound $O(f)$ (assuming $f$ is a computable function)?

Predictably, the answer turns out to be negative.

Let’s start by formalising the problem. Assume $M$ is the Turing machine whose runtime we’re interested in, and $F$ is another TM computing the time bound $f$; then

\[L = \{ (M, F) : M \text{ halts within } O(F) \text{ steps} \}.\]Also let $H$ be the halting problem:

\[H = \{ (M’, x) : M \text{ halts on input } x \}.\]We can now define the function $R(M’, x) = (M, F)$, where $F$ computes $n^2$ and $M$, on input $y$, behaves as follows:

- Simulate $M’$ on $x$ for $n = \lvert y \rvert$ steps.
- If $M’$ has already halted, then loop for $n^2$ steps.
- Otherwise, loop for $n^3$ steps.

We’re finally ready to prove our undecidability result.

**Theorem.** $R$ is a many-one reduction from $H$ to $L$.

*Proof.* Clearly $R$ is a computable function, so we just need to show that

If $(M’, x) \in H$, that is, if $M’$ halts on input $x$, then it does so in $k$ steps (for some $k \in \mathbb{N}$). Hence $M$ runs in $O(n^2)$ time (notice that it runs in $n^3$ time for $\lvert y \rvert < k$, but it’s only the asymptotic behaviour that matters for us). Thus $(M, F) \in L$.

On the other hand, if $M’$ does not halt on $x$, then $M$ never completes its simulation, and the runtime for $M$ is $O(n^3)$. Thus $(M, F) \notin L$. □

**Remark.** We’ve actually proved a stronger statement, i.e., that the set of Turing machines running in $O(n^2)$ time is undecidable, even if we restrict the domain to machines halting in polynomial time. Similar undecidability results hold for an infinite class of time bounds.