Why is $A_{TM}$ reducible to $HALT_{TM}$?

Question

In Sipser, there is a proof I don't understand.

First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input.

$$A_\mathrm{TM}=\left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ accepts }w\right\}\,.$$

Then defined $\mathrm{HALT_{TM}} = \left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ halts on input }w\right\}$, he assume that $\mathrm{HALT_{TM}}$ is decidable and use that assumption to show that $A_\mathrm{TM}$ is decidable, contradicting.

He assume that we have a TM $R$ that decides $\mathrm{HALT_{TM}}$. Then he uses $R$ to construct $S$:

$S$ = "On input $\left \langle M,w \right \rangle$, an encoding of a TM $M$ and a string $w$:

1. Run TM $R$ on input $\left \langle M,w \right \rangle$.
2. If $R$ rejects, reject
3. If $R$ accepts, simulate $M$ on $w$ until it halts.
4. If $M$ has accepted, accept; if $M$ has rejected, reject."

He says "Clearly, if $R$ decides $\mathrm{HALT_{TM}}$, then $S$ decides $A_\mathrm{TM}$. Because $A_\mathrm{TM}$is undecidable, $\mathrm{HALT_{TM}}$ also must be undecidable."

I don't understand why is so obvious the problem is $R$. I mean, I don't understand why if $R$ exists, then inevitably we can simulate $M$. We know that the step number 4 is not possible because $H(\left \langle M,w \right \rangle)$ = "accept if $M$ accepts $w$ OR reject if $M$ rejects $w$" is not possible, so why is $R$ guilty?

Answer 1

Step one, don't try to argue why this TM can not work: under the assumption it does work. But then, since everything else $S$ does is possible (you have to accept that separately), the existence of $R$ certainly is "the problem".

As for understanding, the proof, there are two facts you have to check (under the assumption that $R$ exists):

1. $S$ is a Turing machine (i.e. its function is computable)
2. $S$ decides $A_{TM}$.

Arguably, 1) is clear; simulating other TMs given their indices/encodings is something TMs can do (thanks to the existence of a universal TM, which you should have seen a proof of already) and $S$ does little more. This is as close to a proof as you'll get with this form of "definition" of $S$; it's more of an idea, really.

For the second, note that $S$ always halts because $R$ always halts and

$\qquad\begin{align*} S\langle M,w \rangle) = 1 &\iff R(M,W) = 1 \land M(w) = 1 \\ &\iff M(w)\downarrow \land M(w) = 1 \\ &\iff w \in L_M \\ &\iff \langle M,w \rangle \in A_{TM} \;. \end{align*}$

By definition, that means that $S$ decides $A_{TM}$.

Similar arguments usually works for this kind of proof; check our reference questions and other questions tagged computability+reductions.