We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$.

However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?

I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\{<M>: L(M) \mbox{ is finite}\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?

  • $\begingroup$ For example, I believe that if we have $M$ a Turing machine, even with a $HALT$ oracle deciding if $<M> \in EMPTY$ is impossible, because it would take an infinte amount of time to check every possible input for $M$. Is this right? $\endgroup$ – CerealKiller Sep 25 '15 at 19:10
  • $\begingroup$ EMPTY is stronger then HALT, so $P^{HALT} \subseteq P^{EMPTY}$. $\endgroup$ – Yuval Filmus Sep 25 '15 at 20:18

Let $A,B$ be two incomparable Turing degrees (these can be constructed by diagonalization, known in this context as forcing). If $P^A \subseteq P^B$ then in particular $A \in P^B$, and so $A$ reduces to $B$; since we know this is impossible, we can conclude that $P^A \nsubseteq P^B$. Similarly $P^A \nsupseteq P^B$.

  • $\begingroup$ Then how can I build an incomparable Turing degree for $0^{\prime}$ (the Turing degree of $\mbox{HALT}$)? $\endgroup$ – CerealKiller Sep 25 '15 at 21:02
  • $\begingroup$ You'd have to look that up in a recursion theory monograph. $\endgroup$ – Yuval Filmus Sep 25 '15 at 21:11
  • $\begingroup$ Then there is not a simple answer for that question? $\endgroup$ – CerealKiller Sep 25 '15 at 21:12
  • $\begingroup$ There might be but I'm not aware of it since it's not my area. $\endgroup$ – Yuval Filmus Sep 25 '15 at 21:14

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.