0

$\overline{HALT}=$ { (M, w) : M does not halt on w }
$TOTAL=$ { M : M halts on every input }

The following is the proof from Hopcoft that TOTAL is not R.E.
Let R(x) be the following machine:

1) Simulate M on w for n steps
2) IF M halts after n steps Loop ELSE Halt

R halts on all inputs if and only if M does not halt on w.
Since $\overline{HALT}$ is not R.E neither is $TOTAL$

It's not clear to me why the simulation is only for n steps. If M halts only after n+1 steps doesn't the proof fail? I'm probably missing some context of what Hopcroft meant by "n steps". Could someone clarify?

user137481
  • 2,605

1 Answers1

0

To Each machine $M$ and input $w$, you associate $R$ such that $R(n)$ halts iff $M(w)$ doesn't halt in $n$ steps (or less). Hence $(M,w)\in\overline{HALT}$ is equivalent to $R\in TOTAL$. So you made a reduction and if $TOTAL$ was r.e, also $\overline{HALT}$ (and this is not true) so $TOTAL$ is not r.e.

Xoff
  • 10,310
  • I don't have any problem with the reduction. I have a problem with step 1. If M halts on the n+1 step, R would halt. But then it would not be true that R halts if and only if M does not halt on w. So, I don't understand how the proof works in that case. – user137481 Aug 25 '14 at 16:41
  • @user137481 $n$ is the input of $R$, and if M halts, then it halts for some $n$, then $R$ will not be total. – Xoff Aug 25 '14 at 17:21
  • In Hopcroft's proof, x is the input to R and n is the number of steps. In any case, I've got your point. Thanks! – user137481 Aug 25 '14 at 19:57