2

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 ?

achille hui
  • 122,701
Link L
  • 717

2 Answers2

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.

Reese Johnston
  • 17,988
  • 1
    +1, but this isn't really the standard construction of a pair of Turing incomparable sets - the standard one is Kleene-Post, which is much easier (just finite extensions). Friedberg-Muchnik is for incomparable c.e. sets, which of course is much harder. – Noah Schweber Sep 27 '17 at 21:33
  • @NoahSchweber As a non-logician reading this question, I wasn't sure if "language" meant r.e. set or just any old set. Thanks for clearing that up. – bof Sep 28 '17 at 00:24
-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.

Lorenzo
  • 319
  • "A general example is that of 2 non-computable sets A and B such that there's no computable function mapping one onto the other." No, what you're describing is not Turing reducibility; Turing reducibility is much more complicated. What you're describing is closer to many-one reducibility. – Noah Schweber Sep 27 '17 at 18:53
  • Actually, it's even worse than that. If $Y$ is c.e. in $X$, then there is a computable function mapping $X$ onto $Y$, and this can happen even if $X\not\ge_TY$ (e.g. $Y=X'$). In particular, if $X$ and $Y$ are both c.e., then there are computable functions mapping each onto the other. But there are Turing-incomparable c.e. sets. – Noah Schweber Sep 27 '17 at 18:57
  • "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." That's still false. You should look at the definition of Turing reducibility. (There is a sense in which it's a function from $B$ to $A$, but it's more complicated: it's a functional $f$ of a specific form satisfying $f(B)=A$, rather than a function on $\mathbb{N}$ which sends $B$ onto $A$.) – Noah Schweber Sep 27 '17 at 21:04
  • @Noah Schweber . Thanks. Edited. I used "(non) computable" meaning the broader c.e. – Lorenzo Sep 27 '17 at 21:07
  • @Noah Schweber... I'll look into that: are you sure anyway that this isn't an example of T-incomparable languages? – Lorenzo Sep 27 '17 at 21:11
  • Any c.e. function is a computable function (to compute $f(n)$, wait until you see "$f(n)=k$" enumerated for some $k$). Now fix some set $X$, and let $Y$ be properly c.e. in $X$ (say, $Y=X'$). Then there can be no computable function sending $Y$ to its complement, since then the complement would also be c.e. in $X$; but $Y$ and the complement of $Y$ have the same Turing degree. Turing reducibility is really fundamentally different from "function-y" reduction notions. – Noah Schweber Sep 27 '17 at 21:22
  • @Noah Schweber Thanks again for the feedback but after reviewing my knowledge I still don't get where my example (admittedly a general one) fails: an oracle machine for A or B wouldn't be able to (semi-)decide for the other set. Was it just a matter of using the terms "function" and "map"? – Lorenzo Sep 28 '17 at 01:35