## 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) :Mhalts withinO(F) steps}.

Also let *H* be the halting problem:

H= {(M’,x) :Mhalts on inputx}.

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*= |*y*| 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

(

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*(*n*^{2}) time (notice that it runs in *n*^{3} 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*(*n*^{3}). Thus (*M*, *F*) ∉ *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.

**Explore posts in the same categories:**Complexity, Computability, Favourite theorems

**Tags:** Halting problem, Turing machine

## Leave a Reply