TOTAL is not Recursively Enumerable $\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?

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.