Clarification of Hopcroft's proof that “deciding whether a program halts on all inputs” is not R.E

Question

$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$
$AlwaysHalt =\{ M : M$ halts on all inputs x $\}$

Hopcroft gives the following proof that $AlwaysHalt$ is not R.E.

1) Given an input x of length n, $M'$ simulates $M$ on w for n steps.
2) If during that time $M$ halts then $M'$ loops and $M'$ does not halt on its own input x.
3) However if $M$ does not halt on w after n steps then $M'$ halts.
4) Thus $M'$ halts if and only if $M$ does not halt on w.
5) Since the problem of telling whether $M$ does not halt on w is not R.E., it follows that whether a given TM halts on all inputs must not be R.E. either.

I don't understand why in (1) the number of steps to simulate needs to be dependent on the length of the input x.

I don't understand how step 3 implies step 4. I don't see how knowing that $M$ does not halt on w after n steps (or less) allows us to conclude that $M$ will not halt on w after more than n steps.

Could someone clarify? Thanks.

Answer 1

$M'$ doesn't "need" to do anything. $M'$ is a machine that we construct for purposes of the proof. Hopcroft wrote the theorem, so he can design $M'$ however he wanted -- of course, then it's his obligation to show how his choice of machine helps him prove the theorem. He chose $M'$ cleverly in a way that helps make the proof easy, but that was his choice.

So, it was his choice to make the $M'$ simulate $M$ for only $n$ steps. He could have chosen something else, but this particular choice makes the proof work out nicely. In particular, this property of $M'$ is useful for showing that statement 4 is true. (Exercise: try proving that statement 4 is true, and check where you used the fact that $M'$ will only simulate $M$ for $n$ steps, not more.)