# Clarification: Are runtime bounds in P decidable?

In Emanuele Viola's much upvoted answer to the question, "Are runtime bounds in P decidable?" he uses the following proof:

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $$(M,x)$$ of the halting problem, construct a new machine $$M'$$ that works as follows: on inputs of length $$n$$, it simulates $$M$$ on $$x$$ for $$n$$ steps. If $$M$$ accepts, loop for $$n^2$$ steps and stop; otherwise loop for $$n^3$$ steps and stop.

If $$M$$ halts on $$x$$ it does so in $$t=O(1)$$ steps, so the run time of $$M'$$ would be $$O(n^2)$$. If $$M$$ never halts then the run time of $$M'$$ is at least $$n^3$$.

Hence you can decide if $$M$$ accepts $$x$$ by deciding if the run time of $$M'$$ is $$O(n^2)$$ or $$O(n^3)$$.

I have a significant problem with this proof, but as it is well accepted by theoreticians much smarter than me I am sure that I must be misunderstanding.

Here is my issue:

$$M'$$ simulates $$M$$ on $$x$$ for $$n$$ steps.

If $$M$$ accepts, then $$M$$ certainly halts on $$x$$. However, if $$M$$ does not accept, this does not mean that $$M$$ does not halt on $$x$$; it only means that $$M$$ does not halt on $$x$$ in the first $$n$$ steps. In a comment, Emanuele clarifies that $$M$$ and $$x$$ are selected independently of $$n$$; however, this does not negate the fact that $$M$$ is only simulated on $$x$$ for $$n$$ steps.

So either this is a reduction from, "Does $$(M,x)$$ halt in $$n$$ steps?" which is a decidable problem, or I am missing some major component of this proof. Could someone please clarify?

• If $M$ halts in $t$ steps, then $M'$ runs in time $n^2$ for all $n\geq t$, which is still $O(n^2)$. I.e. $t$ is some constant that depends on $M$ and is independent of $n$. Commented Sep 18, 2015 at 13:18
• Actually, I see the same problem. @SashoNikolov, are you sure that t and n are independent? Doesn't t have to depend on both M and x? Further, n is the length of x. Perhaps I am also missing something.
– user1338
Commented Sep 18, 2015 at 13:45
• @PhilipWhite : $\;\;\;$ t and n are independent because n is not constrained and if t is constrained, then it's to the number of steps M runs for on x. $\:$ t probably does have to depend on both M and x. $\:$ If n is the length of x, then that's by coincidence. $\:$ ($M\hspace{.03 in}'$'s inputs certainly do not need to have the same length as x.) $\;\;\;\;\;\;\;\;$
– user6973
Commented Sep 18, 2015 at 13:51
• @RickyDemer: What are we calling the input to M' then? I believed that "on inputs of length n, it [M'] simulates M on x for n steps" meant that M' is simulating M on the input of M' (i.e., "x"). My impression was that M' calls the UTM and simulates M on its input ("x") for |x| steps. Is that a mistake?
– user1338
Commented Sep 18, 2015 at 14:01
• @PhilipWhite : $\;\;\;$ We're not calling that anything. $\:$ Yes, since x is an entry of the reduction's input.
– user6973
Commented Sep 18, 2015 at 14:07

## 1 Answer

In my opinion, the wording of the answer is a little confusing. Specifically:

Given an instance $(M,x)$ of the halting problem, construct a new machine $M′$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for n steps.

...confused me, too. What you have to understand is that the machine $M'$ is based on one specific instance of the halting problem; it doesn't simulate $M$ on $x$ for $|x|$ steps.

Here is how I would word that part:

Fix an instance $(M,x_1)$ of the halting problem. Construct a machine $M'$ that takes as input $x_2$, and that works as follows: simulate $M$ on $x_1$ for $|x_2|$ steps. If $M$ halts within $|x_2|$ steps, loop for $|x_2|^2$ steps and stop; otherwise loop for $|x_2|^3$ steps and stop.

Hopefully that helps.

• Since this is supposed to be for the halting problem, I would replace "accepts" with "halts". $\hspace{.52 in}$
– user6973
Commented Sep 18, 2015 at 14:41
• So if $M$ halts on $x_1$ in $t$ steps, $M'$ takes $t+|x_2|^2$ steps for all $x_2$ such that $|x_2|>t$. Therefore, if $M$ halts on $x_1$, there exists some $N=t$ such that $M'$ takes fewer than $2*|x_2|^2$ steps for any input $x_2$ where $|x_2|\geq N$, so $M'$ is $O(n^2)$. If you add this to your answer, I will accept it as complete. Commented Sep 18, 2015 at 14:44
• I made the edit. @ Kittsil, Let me review that and make sure I agree.
– user1338
Commented Sep 18, 2015 at 14:49
• I agree with what you wrote, but it might be better to let someone who is good at MathJax edit it or just leave it as a comment.
– user1338
Commented Sep 18, 2015 at 15:11