4
$\begingroup$

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...)

|cite|improve this question
$\endgroup$
  • $\begingroup$ Assuming that "accepts" means "halts at an accepting state", the two problems are equivalent, and there are even many-one reductions between them. $\endgroup$ – Yuval Filmus Mar 1 '17 at 0:55
  • $\begingroup$ 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. $\endgroup$ – NBose35 Mar 1 '17 at 0:59
  • $\begingroup$ 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)$ $\endgroup$ – Matt Timmermans Mar 1 '17 at 1:38
  • $\begingroup$ @MattTimmermans You can do even better, and use a many-one reduction. $\endgroup$ – Yuval Filmus Mar 1 '17 at 1:55
3
$\begingroup$

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}}$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.