# Is it possible to prove Turing irreducibility

Given two languages $L_1$ and $L_2$, is there a known way to show that $L_1\not\leq_T L_2$?

In other words, is it possible proving that there is no Turing reduction from $L_1$ to $L_2$?

## 2 Answers

Let $A_{TM}$ be the language of the Halting problem. Then $\overline{A_{TM}} \nleq_T A_{TM}$, otherwise $A_{TM }$ would be recursive.

Another well-known theorem by Friedberg–Muchnik proves (using the finite injury priority argument) that there are recursively enumerable languages $A$ and $B$ such that $A \nleq_T B$ and $B \nleq_T A$ (pairwise incomparable).

R. Soare's book, for example, has more on this subject.

Yes, in some cases it is possible to prove that a set does not Turing-reduce to another.

For instance, if $L_2$ is recursive, and $L_1$ is not, then surely we can not have $L_1 \leq_T L_2$. (This does not generalize to r.e. sets, unlike for $\leq_m$-reduction).