# In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

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

1. If $$v$$ is not the same as $$w$$, halt. Otherwise continue.
2. Feed $$v$$ (meaning $$w$$ in this case) to $$M$$ and let $$M$$ compute on $$w$$.
3. 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?

\begin{align} \{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, w is a string,}\\ &\text{and M }accepts\text{ w after a finite computation}\} \end{align}