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.