For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$

I am trying to come up with a proof for the following:

For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$.

I was thinking of letting $B$ be $A_{\mathrm{TM}}$, but I realize that not all languages are Turing reducible to $A_{\mathrm{TM}}$, so $A \le _T B$ would not hold. What other choice of $B$ do I have that would allow me to write a TM which uses an oracle for $B$ to decide $A$?

Thanks!

• How about $B = NP^A$? – Eugene Nov 28 '16 at 6:33
• Think of the halting problem on Turing machines with oracle $A$. – Willard Zhan Nov 28 '16 at 6:33
• @user1354784 Turing machines with oracle $A$ can be enumerated. So try to use the standard diagonalization, where the only change is that for every $\alpha\in\Sigma^*$, $M_\alpha$ represents an oracle TM with oracle $A$ instead of a normal TM. – Willard Zhan Dec 1 '16 at 2:44
• @DavidRicherby Yes, but B is not fixed, it is built knowing what A is. If we are given some A, we build a B that accepts every oracle TM with an oracle for this specific A that accepts strings in A. If we are given a different A, the list of TMs in B will be different. – user1354784 Dec 1 '16 at 17:13
• @user1354784 Exactly. I meant that comment as another explanation of why we can't take $B=A_{\mathrm{TM}}$ as you had suggested (and already rejected, for a different reason) in your question. I forgot to explain that that was the point I was making -- sorry for the confusion there. – David Richerby Dec 1 '16 at 18:08

Let $$B=A'$$, the Turing jump of $$A$$. This is a basic result in the theory of the Turing degrees.

Before diving into the good answer - namely, that we can relativize the halting problem to assign to each language $$X$$ a language $$X'$$ such that (among other things) $$X<_TX'$$ - it's worth seeing the silly answer:

• Cantor showed that there are uncountably many languages.

• But every specific language $$A$$ can only compute countably many languages: a single Turing machine can only possibly yield one reduction from a given language $$A$$, and there are only countably many Turing machines.

So in fact we know, without doing any serious work, that:

For every language $$A$$, most (= all but countably many) languages $$B$$ satisfy $$B\not\le_TA$$.

Now we combine this with the Turing join: given languages $$X,Y$$, the join $$X\oplus Y$$ consists of "interleaving" $$X$$ and $$Y$$. There are various ways to define it - e.g. thinking of $$X$$ and $$Y$$ as sets of naturals, we usually let $$X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$$ - but the important feature is that $$X\oplus Y\ge_TX,Y$$ (and in fact is their $$\le_T$$-least upper bound).

So we can apply the above, to get:

For every language $$A$$, most (= all but countably many) languages $$B$$ satisfy $$A<_TA\oplus B$$.

This then raises the question of giving a non-stupid proof, namely a natural way to produce a language strictly more complicated than a given one, and this is what the Turing jump is for; but it's worth understanding this nonconstructive argument on its own.