1
$\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?

Improve this question
$\endgroup$
6
  • 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, 2015 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$
    – user1338
    Sep 18, 2015 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, 2015 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$
    – user1338
    Sep 18, 2015 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, 2015 at 14:07

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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