patternMinor
Is it possible to prove Turing irreducibility
Viewed 0 times
turingpossibleirreducibilityprove
Problem
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$?
In other words, is it possible proving that there is no Turing reduction from $L_1$ to $L_2$?
Solution
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.
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.
Context
StackExchange Computer Science Q#86011, answer score: 4
Revisions (0)
No revisions yet.