# A reduction of $HALT_{TM}$ to $A_{TM}$

A widely used example of reductions, is a reduction of $A_{TM}$ to $HALT_{TM}$.

How to show the opposite reduction, meaning of $HALT_{TM}$ to $A_{TM}$, if possible.

A many-one reduction from $HALT_{TM}$ to $A_{TM}$ means that all instances of the $HALT_{TM}$ problem are transformed to an instance of $A_{TM}$ (can be just one instance), such that if $A_{TM}$ is turing-recognizable then $HALT_{TM}$ is also turing-recognizable.

This reduction can be done by encoding a $TM$ $N$, such that $N$ accepts input string $\langle M,w\rangle$ iff $M$ halts with input string $w$. So if $M$ halts with input $w$, it means that $\langle M,w\rangle \in HALT$, which implies that $N$ accepts $\langle M,w\rangle$, and that the instance $\langle N,\langle M,w\rangle\rangle\in A_{TM}$.

• That's quite an obscure explanation. Could you make it more plattable? Commented Feb 8, 2018 at 17:52

There is a reduction proof here, with a lot of context: https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/22/Small22.pdf

In short, the reduction is:

Let the machine $$M'$$ be defined as follows:

$$M'$$ = On input $$⟨N, z⟩$$:

1. Run $$N$$ on $$z$$.
2. If $$N$$ halts on $$z$$, accept

We run on $$⟨M', ⟨M, w⟩⟩$$, and get that $$⟨M, w⟩ \in HALT_{TM} \iff ⟨M', ⟨M, w⟩⟩ \in A_{TM}$$