4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$

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.