<p>In <a href="https://cstheory.stackexchange.com/users/259/emanuele-viola">Emanuele Viola</a>'s much upvoted <a href="https://cstheory.stackexchange.com/a/5006/35605">answer</a> to the question, <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no">&quot;Are runtime bounds in <strong>P</strong> decidable?&quot;</a> he uses the following proof:</p>
<blockquote>
<p>The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance <span class="math-container">$(M,x)$</span> of the halting problem, construct a new machine <span class="math-container">$M'$</span> that works as follows: on inputs of length <span class="math-container">$n$</span>, it simulates <span class="math-container">$M$</span> on <span class="math-container">$x$</span> for <span class="math-container">$n$</span> steps. If <span class="math-container">$M$</span> accepts, loop for <span class="math-container">$n^2$</span> steps and stop; otherwise loop for <span class="math-container">$n^3$</span> steps and stop.</p>
<p>If <span class="math-container">$M$</span> halts on <span class="math-container">$x$</span> it does so in <span class="math-container">$t=O(1)$</span> steps, so the run time of <span class="math-container">$M'$</span> would be <span class="math-container">$O(n^2)$</span>. If <span class="math-container">$M$</span> never halts then the run time of <span class="math-container">$M'$</span> is at least <span class="math-container">$n^3$</span>.</p>
<p>Hence you can decide if <span class="math-container">$M$</span> accepts <span class="math-container">$x$</span> by deciding if the run time of <span class="math-container">$M'$</span> is <span class="math-container">$O(n^2)$</span> or <span class="math-container">$O(n^3)$</span>.</p>
</blockquote>
<p>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.</p>
<p>Here is my issue:</p>
<blockquote>
<p><span class="math-container">$M'$</span> simulates <span class="math-container">$M$</span> on <span class="math-container">$x$</span> for <span class="math-container">$n$</span> steps.</p>
</blockquote>
<p>If <span class="math-container">$M$</span> accepts, then <span class="math-container">$M$</span> certainly halts on <span class="math-container">$x$</span>. However, if <span class="math-container">$M$</span> does not accept, this does not mean that <span class="math-container">$M$</span> does not halt on <span class="math-container">$x$</span>; it only means that <span class="math-container">$M$</span> does not halt on <span class="math-container">$x$</span> in the first <span class="math-container">$n$</span> steps. In a comment, Emanuele clarifies that <span class="math-container">$M$</span> and <span class="math-container">$x$</span> are selected independently of <span class="math-container">$n$</span>; however, this does not negate the fact that <span class="math-container">$M$</span> is only simulated on <span class="math-container">$x$</span> for <span class="math-container">$n$</span> steps.</p>
<p>So either this is a reduction from, &quot;Does <span class="math-container">$(M,x)$</span> halt in <span class="math-container">$n$</span> steps?&quot; which is a decidable problem, or I am missing some major component of this proof. Could someone please clarify?</p>

CC BY-SA 3.0
2015-09-18T13:18:04.273Z
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
<cc.complexity-theory>
Clarification: Are runtime bounds in P decidable?
Kittsil
# Clarification: Are runtime bounds in P decidable?

(Asked by: username_0 on 2015-09-18)

In [Emanuele Viola](https://cstheory.stackexchange.com/users/259/emanuele-viola)'s much upvoted [answer](https://cstheory.stackexchange.com/a/5006/35605) to the question, ["Are runtime bounds in **P** decidable?"](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no) 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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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$.  

---

## 0 answers

