Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction from HALT to show that ALLHALT is not decidable.
Online (link) I found this (simular) solution:
$D$ = on input $s$:
- Check that $s$ is of the form $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string over the input alphabet of $M$. If not, reject $s$. Otherwise continue.
Define a new machine $M_2$ corresponding to the pair $M, w$ as follows.
$M_2$ = on input $v$:
- If $v$ is not the same as $w$, halt. Otherwise continue.
- Feed $v$ (meaning $w$ in this case) to $M$ and let $M$ compute on $w$.
- If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. If $M$'s computation on input $w$ halts and accepts $w$, halt. Otherwise continue looping like $M$ is doing.
Notice that we've designed $M_2$ in a clever way so that the result of $M$'s computation on input $w$ is encoded in the halting behavior of $M_2$. Namely, $M$ accepts $w$ if and only if $M_2$ halts on all inputs. In terms of language membership, this means that $\langle M, w\rangle$ belongs to Halt if and only if $\langle M_2\rangle$ belongs to Halt2. In light of this fact, finish the description of $D$'s computation as follows.
- Feed the string $\langle M_2\rangle$ into the decider $D_2$.
- Return $D_2$'s decision.
I don't understad the point 3: If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. Why does $M_2$ need to loop indefinitely?