This blog post is motivated by a question John Sidles recently asked on the Theoretical Computer Science Q&A site. Emanuele Viola answered it (providing a very clever proof), and Raphael (I don’t know his last name) rephrased that answer, hoping the proof would be a bit clearer. I think things might be made clearer still, so this is my attempt to express Emanuele’s fine idea in my own words.
Suppose we know for sure that a Turing machine runs in polynomial time. The question is: can we say more than that? Is there some algorithm to determine the minimum so that the Turing machine runs in ? Unfortunately, the answer is NO.
Proposition: Let be a Turing machine. There is no algorithm that determines the minimum such that .
Proof: We will show that if we can solve this problem, we can solve the Halting Problem. Let be an arbitrary Turing machine, and an arbitrary natural number (intuitively, is an input to ). Now define the Turing machine as follows:
- Let be the length (i.e., number of bits) of the input to .
- Simulate running with input for steps.
- If accepts during step 2, loop for steps and then halt.
- Otherwise, loop for steps and then halt.
Note that the value of is independent of the choice of input to . So iff halts on , and iff does not halt on . We know that is in . (In fact, we know something stronger: it is either in or .) If we could determine the minimum exponent (for simplicity, either 2 or 3) such that upper-bounds the running time of , we would be able to decide whether an arbitrary Turing machine accepts an arbitrary input — the Halting Problem. So no algorithm can exist that will provide us the value of .
I really like this argument. It’s almost poetic: nothing unnecessary included.