0
$\begingroup$

I have the language:

G = {<B,w> | B is an oracle TM and B[ATM] accepts w}

I need to prove if this language is decidable relative to ATM. How would I go on about doing that??

My idea was to build a machine that just asks the oracle of ATM if <B,w> participates in ATM, but that seems "too simple" to be correct..

Improve this question
New contributor
Manos Mastronikolas is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • $\begingroup$ What do $A_{TM}$ and $B[A_{TM}]$ mean in $G$? $\endgroup$
    – minh quý lê
    Commented Dec 11 at 15:42

1 Answer 1

Reset to default
0
$\begingroup$

You cannot ask an oracle of $A_{TM}$ whether $B[A_{TM}]$ accepts $w$, because $B$ is not a standard Turing Machine, it has an oracle.

Just to put you on the right track: is there really a difference between $G$ and $A_{TM}$? (apart from the oracle) Try to recall how you proved that $A_{TM}$ is undecidable.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Why can I not ask A_TM's oracle about B? Why does the fact that B uses an oracle disable my ability to ask the oracle of A_TM? $\endgroup$
    – Manos Mastronikolas
    Commented Dec 10 at 12:28
  • $\begingroup$ Because the oracle knows how to solve $A_{TM}$, and the inputs for $A_{TM}$ are Turing Machines, not Turing machines with an oracle. It's just not the same "creature". $\endgroup$
    – Shaull
    Commented Dec 10 at 12:33
  • $\begingroup$ So basically I can prove it with Cantor's diagonalization, just like ATM $\endgroup$
    – Manos Mastronikolas
    Commented Dec 10 at 12:59
  • $\begingroup$ Yes, exactly. (Although to my knowledge this is usually not referred to as Cantor's diagonalization, but rather just "diagonalization". Cantor is reserved for pure sets, as well as the uncountability of the real numbers). $\endgroup$
    – Shaull
    Commented Dec 10 at 13:39
  • $\begingroup$ Since we already know ATM is undecidable, couldn't I reduce this language to ATM, or is it not possible because they're basically the same language $\endgroup$
    – Manos Mastronikolas
    Commented Dec 10 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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