2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Sep 18 '15 at 13:18
  • $\begingroup$ 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. $\endgroup$ – Philip White Sep 18 '15 at 13:45
  • $\begingroup$ @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.) $\;\;\;\;\;\;\;\;$ $\endgroup$ – user6973 Sep 18 '15 at 13:51
  • $\begingroup$ @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? $\endgroup$ – Philip White Sep 18 '15 at 14:01
  • $\begingroup$ @PhilipWhite : $\;\;\;$ We're not calling that anything. $\:$ Yes, since x is an entry of the reduction's input. $\endgroup$ – user6973 Sep 18 '15 at 14:07
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Since this is supposed to be for the halting problem, I would replace "accepts" with "halts". $\hspace{.52 in}$ $\endgroup$ – user6973 Sep 18 '15 at 14:41
  • $\begingroup$ 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. $\endgroup$ – Kittsil Sep 18 '15 at 14:44
  • $\begingroup$ I made the edit. @ Kittsil, Let me review that and make sure I agree. $\endgroup$ – Philip White Sep 18 '15 at 14:49
  • $\begingroup$ 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. $\endgroup$ – Philip White Sep 18 '15 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.