patternMinor
Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines
Viewed 0 times
provingproblemtheacceptancehaltingreduciblethatformachinesturing
Problem
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...)
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...)
Solution
The two problems are equivalent up to many-one reductions.
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}}$.
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}}$.
Context
StackExchange Computer Science Q#70989, answer score: 4
Revisions (0)
No revisions yet.