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

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.