# Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines

Consider $\mbox{Halt}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ halts on input } w\}$ and $\mbox{A}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ accepts on input } w\}$. I'd like to prove that any oracle TM $T$ that can query the $\mbox{A}_\mbox{TM}$-oracle cannot decide $\mbox{Halt}_\mbox{TM}$.

Intuitively, it appears that when $T$ queries this oracle with $\langle M, w \rangle$ and the oracle in turn replies "No" (i.e., $M$ does not accept $w$), $T$ is incapable of deciding whether $w$ is rejected by $M$ or $M$ is looping on $w$. Thus, the oracle cannot help $T$ in deciding $\mbox{Halt}_\mbox{TM}$. However, this doesn't really prove that $\mbox{Halt}_\mbox{TM}$ is undecidable relative to $\mbox{A}_\mbox{TM}$, since $T$ could feed any query it pleases to the $\mbox{A}_\mbox{TM}$-oracle. Would a contradiction proof work best in this case? (I.e., suppose that the halting problem is decidable relative to the acceptance problem...)

• Assuming that "accepts" means "halts at an accepting state", the two problems are equivalent, and there are even many-one reductions between them. – Yuval Filmus Mar 1 '17 at 0:55
• But how is $T$ able to distinguish between looping and halting at a reject state, based on what the $A_{TM}$-oracle tells it? I mean that not accepting implies either rejecting or looping. I suppose that $T$ could be much more clever than I'm imagining. – NBose35 Mar 1 '17 at 0:59
• Given any machine $M$, you can calculate a machine $\neg M$ that accepts any input $w$ iff $M$ halts on a rejecting state for $w$. Then $Halt(M,w) = A(M,w) \lor A(\neg M,w)$ – Matt Timmermans Mar 1 '17 at 1:38
• @MattTimmermans You can do even better, and use a many-one reduction. – Yuval Filmus Mar 1 '17 at 1:55

Reducing $\mathrm{Halt_{TM}}$ to $A_{\mathrm{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by marking all rejecting states as accepting. Then $\langle M,w \rangle \in \mathrm{Halt_{TM}}$ if $\langle M',w \rangle \in A_{\mathrm{TM}}$.
Reducing $A_{\mathrm{TM}}$ to $\mathrm{Halt_{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by getting to an infinite loop at every rejecting state. Then $\langle M,w \rangle \in A_\mathrm{{TM}}$ if $\langle M',w \rangle \in \mathrm{Halt_{TM}}$.