Example of two undecidable languages that cannot be reduced to each other

Question

I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some non-Turing-recognizable language, then it is clear that $B$ cannot reduce to $A$, but I don't know which $B$ can I pick to show that $A$ cannot reduce to $B$

Answer 1

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.

---

The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary strings $$\sigma_0\prec\sigma_1\prec\sigma_2\prec ...\quad\mbox{and}\quad \tau_0\prec\tau_1\prec\tau_2\prec ...$$ such that for each $i$ there do not exist infinite binary sequences $f,g$ extending $\sigma_i,\tau_i$ respectively such that $\Phi_i^f=g$ or $\Phi_i^g=f$.

• Proving that such sequences in fact exist is a good exercise.

Taking $$a=\bigcup\sigma_i,\quad b=\bigcup\tau_i$$ we then have that $a$ and $b$ are Turing-incomparable. (Thinking about this construction a bit, we can in fact ensure that $a,b$ are $\le_T{\bf 0'}$.)

---

A better result is that there are computably enumerable sets which are Turing incomparable (the Friedberg-Muchnik theorem). This is much harder to prove, however; it was the first example of a priority argument.

Yuval Filmus commented that a pair of "random" languages should probably work. There are multiple senses in which this is true - in particular, the set of pairs of infinite binary sequences which are Turing incomparable is both comeager and of full measure in the space of all pairs of infinite binary strings (with the usual topology and measure). The former observation is basically just the mutual diagonalization argument above, slightly tweaked; the latter is a bit harder to prove. (In general, in computability theory measure is more complicated than category.)

• In fact, the proofs of the observations in the previous paragraph actually yield stronger results without significant changes: namely, we get that for every noncomputable infinite binary sequence $f$ the set of infinite binary sequences Turing-incomparable with $f$ is both comeager and of full measure in the space of all infinite binary sequences.