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


  • $\begingroup$ How about $B = NP^A$? $\endgroup$ – Eugene Nov 28 '16 at 6:33
  • 3
    $\begingroup$ Think of the halting problem on Turing machines with oracle $A$. $\endgroup$ – Willard Zhan Nov 28 '16 at 6:33
  • 2
    $\begingroup$ @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. $\endgroup$ – Willard Zhan Dec 1 '16 at 2:44
  • 1
    $\begingroup$ @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. $\endgroup$ – user1354784 Dec 1 '16 at 17:13
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

