Time is unpredictable

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

Also let $H$ be the halting problem:

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.