Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $L$. Is it possible to define such an $L$ so that $T$ does not decide $E_{TM}$ (the language of descriptions of Turing machines whose languages are empty)?

Intuitively, it seems the problem is that when the oracle answers "No", $T$ is unable to distinguish whether the string it fed to the oracle to receive this response belongs to $A_{TM} - L$ or $\overline{A_{TM}}$. But this doesn't really prove that $T$ can't decide $E_{TM}$.

  • $\begingroup$ What if $L$ is $A_{TM}$ minus 3 strings? Or minus an infinite recursive subset of it? $T$ in such case is able to decide $A_{TM}$. Knowing that it is a proper non empty subset is quite weak. $\endgroup$ – chi Feb 27 '17 at 18:00
  • $\begingroup$ Would it be possible to define $L \subset A_{TM}$ in such a way that $T$ can't decide $E_{TM}$? $\endgroup$ – NBose35 Feb 27 '17 at 18:08
  • $\begingroup$ Yes, that's possible for some $L$, e.g. the recursive ones. $\endgroup$ – chi Feb 27 '17 at 18:19

Your Answer

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

Browse other questions tagged or ask your own question.