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

\[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:

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

\[(M', x) \in H \iff (M, F) \in L.\]

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.