# Machine with an oracle for a language that cannot decide another language in polynomial time

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

• 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? – CerealKiller Sep 25 '15 at 19:10
• EMPTY is stronger then HALT, so $P^{HALT} \subseteq P^{EMPTY}$. – Yuval Filmus Sep 25 '15 at 20:18

## 1 Answer

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

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