Reduction from $HALT$ to $A_{TM}$

Question

I know the reduction to from $A_{TM}$ to $HALT$. But is the following reduction from $HALT$ to $A_{TM}$ correct?

We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$. The following TM $F$ calculates the reduction $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

I think the line if T accepts or rejects, *accept* is correct, but it would be great if someone could check this.

Edit: I found the following slides, but I don't think the construction in there is correct: http://slideplayer.com/slide/13791105/

Answer 1

There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (more specific link here) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction.

While many-one reductions are generally the default notion in complexity theory, Turing reductions and the resulting degree structure are the default in computability theory. Note that if all I want to do is prove the undecidability of some set, a Turing reduction from some known-to-be-undecidable set is sufficient.

---

First, let's explicitly recall the definitions of the languages involved:

• $A_{TM}=\{\langle M,w\rangle: M$ halts and accepts on input $w\}$.

• $HALT=\{\langle M,w\rangle: M$ halts on input $w\}$.

Your proposed reduction of $HALT$ to $A_{TM}$ is correct: given $M$, we can computably build a new machine $\hat{M}$ which accepts precisely those strings on which $M$ halts. (Basically, just replace all the "reject" states in $M$ by "accept" states.)

---

Now let's look at the other reduction which you linked to (more specific link here).

Basically, rather than going to "all halting states accept" the linked argument considers separately:

• the original machine, and

• the "contrary" machine which accepts exactly when the original one rejects and vice-versa.

An affirmative answer for either case in $A_{TM}$ ensures an affirmative answer for the original machine in $HALT$.

Off the top of my head I see no reason to do this rather than follow your argument, especially because it yields a weaker result, but it is correct and is enough to prove the broader claim in the slides, namely that $A_{TM}$ is undecidable.