1

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?

Community
  • 1
Kittsil
  • 113
  • 3
  • 2
    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$. – Sasho Nikolov Sep 18 '15 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. –  Sep 18 '15 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.) $;;;;;;;;$ –  Sep 18 '15 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? –  Sep 18 '15 at 14:01
  • @PhilipWhite : $;;;$ We're not calling that anything. $:$ Yes, since x is an entry of the reduction's input. –  Sep 18 '15 at 14:07
  • I think I understand what I was missing. The trick is that M' is a whole separate machine that treats M and x as constants. I.e., you start with an instance of the halting problem, and then construct a whole new machine based on that instance. You don't necessarily even have to call the UTM. –  Sep 18 '15 at 14:16

1 Answers1

4

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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • Since this is supposed to be for the halting problem, I would replace "accepts" with "halts". $\hspace{.52 in}$ –  Sep 18 '15 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. – Kittsil Sep 18 '15 at 14:44
  • I made the edit. @ Kittsil, Let me review that and make sure I agree. –  Sep 18 '15 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. –  Sep 18 '15 at 15:11