$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.


$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.)

  • $\begingroup$ I'm assuming that the property of M' you are referring to is statement 3. That property just says that M' will halt if M does not halt after n steps. Equivalently, you can say that M' will halt if and only if M does not halt on w after n steps. Statement 4 is saying something more. It's saying that M' halts if and only if M does not halt on w. Isn't that like saying "run M on w for 6 steps. If M has not halted in that time, it will never halt at all"? Unless I've misinterpreted statements 3 and 4, I can't prove statement 4 is true from statement 3. $\endgroup$
    – user21038
    Aug 28 '14 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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