Incomparable languages $B \nleq_T A$ and $A \nleq_T B$

Question

I came across a problem to prove that there are sets $A$ and $B$ termed 'Turing-Incomparable' languages $B \nleq_T A$ and $A \nleq_T B$. The only languages I could think of are if $A$ and $B$ are disjoint regular expressions such as $B=1^*$ and $A=0^*$. This way, one could not act as an 'oracle' for the other, but is there something missing ?

Answer 1

Your example of symbol-disjoint languages doesn't seem relevant as we can still have a Turing computable biijection between the two.

In this context, the point of Turing reducibility, comparability, jumps and the likes is to acknowledge the effects of Turing degrees on set recognition by different oracle machines.

Your problem is equivalent to proving the non-existence of a total order over the Turing degrees. A general example is that of 2 non-computably-enumerable sets A and B such that there's no computably-enumerable function mapping one onto the other.

Answer 2

"Disjoint" is by no means sufficient. The first problem is that the two languages you suggest are both computable, so you can automatically compute one from the other (there's no obligation to actually make use of an oracle you're given).

Constructing two Turing-incomparable sets is a very complex problem. In particular, there are no known "natural" examples - that is, basically, the only known examples of Turing-incomparable sets are sets cooked up specifically for proving that these pairs exist.

The standard construction of a pair of Turing-incomparable sets is the Friedberg-Muchnik finite-injury argument (http://www1.maths.leeds.ac.uk/~pmt6sbc/3163/FMslides.pdf gives an OK description of this argument). It's not a difficult technique by the standards of research math, but it's not easy to explain in a few sentences either.