# To Prove an undecidable language on halting

I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press. I cannot solve the first problem in Chapter Three(p.77), which may be probably disappointing. The problem is as follow:

Show that the follow language is undecidable:
{M|M is a machine that runs in $100n^2+200$ time}.

-

You can reduce the halting problem to your problem. Given a Turing machine $M$ and input $z$, let us design a new machine $N$, which on input $y$, first runs $M$ on input $z$ for $|y|$ steps, and if this doesn't halt yet, then $N$ halts, but if $M$ does halt, then $N$ counts up to $|y|^3$ and then halts. That is, if $M$ doesn't halt on $z$, then $N$ halts quickly, but if $M$ does halt on $z$, then $N$ takes a long time on large input.

Thus, $M$ fails to halt on $z$ if and only if $N$ runs in $100n^2+200$ time on all input of size $n$. So if we could decide the latter property, then we could decide the halting problem, which is impossible.

This argument actually shows more, namely, that the complement of the halting problem is $1$-reducible to the running-in-time-$f$ problem.

(A similar argument could make use of Yuval's suggestion, using the halting-on-empty-string problem instead of the halting problem, which would eliminate the need to consider nontrivial $z$.)

-
And the problem is obviously in $\Pi_1^0$ --- you can construct a machine that for a given machine $M$ simulates it on every input $x$ for $100|x|^2 + 200$ steps. If $M$ exceeds this number of steps on any input than $M$ just halts and sayes "yes". So if your argument were correct it would mean that the above problem is \emph{recursive}. –  Michal R. Przybylek May 4 '11 at 13:55
About your $\Pi^0_1$ remark, it is resolved by observing that my argument reduces the complement of the halting problem to the given problem. (I was missing a complement, and have edited.) But this is fine for Turing reduction, since if we can decide a set, we can decide its complement. –  JDH May 4 '11 at 14:06
I understood the problem to mean that the running time should be at most $f(n)$, rather than exactly $f(n)$. (And we can easily arrange that $N$ simply ignores all small input.) About your reduction comment, my argument shows that the halting problem is Turing reducible to the running-time problem. That is, from an oracle for the running-time problem, we can decide the halting problem. It follows that the running-time problem is not decidable. But my argument shows more precisely that the complement of the halting problem $1$-reduces to the running-time problem, which is a stronger result. –  JDH May 4 '11 at 16:50
In particular, yes, my solution mentions two different reductions: the (Turing) reduction of the halting problem to the running time problem, and the $1$-reduction of the complement of the halting problem to the running time problem. –  JDH May 4 '11 at 17:27
Yes, in fact every $\Pi^0_1$ question similarly $1$-reduces to the complement of the halting problem. I agree with what you say about $O(n^2)$, and indeed, the set of such $M$ is $\Sigma^0_2$-complete. This seems to work even with $O(f)$ for any non-zero $f$, even $O(1)$, since the big-O concept in effect adds an extra quantifier. –  JDH May 4 '11 at 20:20
Hint: It is undecidable whether $M$ halts when running on the empty string.