It is possible to show ($HALT_{TM}$ is decidable $\Rightarrow A_{TM}$ is decidable), but how about the converse?

Question

Let $HALT_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ halts on } w \}$ and $A_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ accepts } w \}$.

It is possible to show that

$HALT_{TM}$ is decidable $\Rightarrow A_{TM}$ is decidable $(*)$

by using a Turing machine (TM) $H$ that decides $HALT_{TM}$ to construct another TM $A$ that decides $A_{TM}$ as follows:

$A =$ "On input $\langle M,w\rangle$,

1. Run $H$ on $\langle M, w \rangle$.
2. If $H$ rejects $\langle M, w \rangle$ then reject $\langle M, w \rangle$.
   • If $H$ accepts $\langle M , w \rangle$ then run $M$ on $w$:
     • If $M$ accepts $w$ then ACCEPT
     • If $M$ rejects $w$ then REJECT "

However I am having difficulty showing the converse, i.e.

$A_{TM}$ is decidable $\Rightarrow HALT_{TM}$ is decidable $(**)$

by using a TM that decides $A_{TM}$ to construct a TM that decides $HALT_{TM}$. Is it possible to do this? If it is not possible, how does one rigorously prove that this is not possible?

Here is a natural way to begin to proceed to show $(**)$:

Let $M_A$ be a TM that decides $A_{TM}$. We will try to construct $M'$ that decides $HALT_{TM}$ (But I cannot construct it successfully using $M_A$).

$M_H =$ "On input $\langle M,w\rangle$,

1. Run $M_A$ on $\langle M, w \rangle$.
   • If $M_A$ aceepts $\langle M, w \rangle$ then ACCEPT.
   • $M_A$ rejects $\langle M, w \rangle$ then run $M$ on $w$
     • If $M$ rejects $w$ then ACEEPT.
     • (Not sure what to do on this line. I know that $M$ will never accept $w$ but I have no way of knowing whether $M$ will never reject $w$, so I can't use $M_A$ to somehow show $M$ will not halt) "

Comments:

I find that unintuitive if it is the case that we cannot show $(**)$ because it can be shown that

$A_{TM} \le_m HALT_{TM}$ (1)

and

$HALT_{TM} \le_m A_{TM}$ (2)

where $ A \le_m B$ means that $A$ is mapping reducible to $B$ if there exists a computable function $f:\Sigma^* \longrightarrow \Sigma^* $ such that for every string $w$, $w\in A$ iff $f(w)\in B$.

$A_{TM}$ can be shown to be undecidable independent of the undecidability of $HALT_{TM}$ and vice versa, hence we can show $HALT_{TM}$ is undecidable via $A_{TM} \le_m HALT_{TM}$ by virtue of the undecidability of $A_{TM}$ (and similarly show $A_{TM}$ is undecidable via $HALT_{TM} \le_m A_{TM}$ by virtue of the undecidability of $HALT_{TM}$. So because (2) holds, intuitively it seems to me that there should be a way of showing $(**)$?

Summary of questions:

1. Is it possible to show $(**)$ by using a TM that decides $A_{TM}$ to construct a TM that decides $HALT_{TM}$. If it is not possible, how does one rigorously prove that this is not possible?
2. If it is the case that it is not possible to show $(**)$, what is really going on because (2) being true seems to suggest that there is a way to construct a TM that decides $HALT_{TM}$ (assuming $A_TM$ is decidable)? Unless there's a good reason that this intuition is not correct?

Answer 1

Yes, if $\texttt{A}_{\texttt{TM}}$ is decidable then $\texttt{HALT}$ is decidable. Better put, a Turing Machine with an $\texttt{A}_\texttt{TM}$ oracle can decide $\texttt{HALT}$ or $\texttt{HALT} \leq_m \texttt{A}_\texttt{TM}$. As stated in the question, $\texttt{A}_\texttt{TM} \leq_m \texttt{HALT}$. The corollary here is that $\texttt{A}_\texttt{TM}\equiv_m\texttt{HALT}$. I will describe the procedure.

For any Turing Machine $M$, if $M$ accepts $w$ then $M$ halts on $w$. If $M$ does not accept on $w$ then construct $\overline{M}$ that rejects a string whenever $M$ accepts it. $\overline{M}$ can be computably constructed uniformly on $M$. If $\overline{M}$ accepts $w$ then $M$ rejects $w$, thus $M$ halts on $w$. If neither $\overline{M}$ nor $M$ accept $w$ then $M$ neither accepts nor rejects $w$, thus $M$ does not halt on $w$.