Time is unpredictable

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 halts within O(F) steps}.

Also let H be the halting problem:

H = {(M’, x) : M halts on input x}.

We can now define the function R(M’, x) = (M, F), where F computes n2 and M, on input y, behaves as follows:

  • Simulate M’ on x for n = |y| steps.
  • If M’ has already halted, then loop for n2 steps.
  • Otherwise, loop for n3 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

(M’, x) ∈ H ⇔ (M, F) ∈ L.

If (M’, x) ∈ H, that is, if M’ halts on input x, then it does so in k steps (for some k ∈ ℕ). Hence M runs in O(n2) time (notice that it runs in n3 time for |y| < k, but it’s only the asymptotic behaviour that matters for us). Thus (M, F) ∈ 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(n3). Thus (M, F) ∉ L. □

Remark. We’ve actually proved a stronger statement, i.e., that the set of Turing machines running in O(n2) 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.

A cartoon about the halting problem

Bob is a programmer and software engineer, developing automated software testing utilities for his company. However, his manager Eve wants to fire him and, in order to get an excuse, she assigns him a very hard task: developing a tool to check the termination of programs. Eve, for some reason, seems to know that he’s doomed to failure.

Fortunately, the exhausted Bob receives a visit in his dreams by someone important, who explains the problem to him and helps him get his revenge.

Thanks to Lee Graham for this cartoon.