Clarification: Are runtime bounds in P decidable? In Emanuele Viola's much upvoted answer to the question, &quot;Are runtime bounds in P decidable?&quot; 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, &quot;Does $(M,x)$ halt in $n$ steps?&quot; which is a decidable problem, or I am missing some major component of this proof. Could someone please clarify?
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.