# If a language is not Turing reducible to two languages, may it still be Turing reducible to their “union”?

Consider a language $L$ that is undecidable relative to $L_1$ and is also undecidable relative to $L_2$. Suppose, however, that there is a "multi"-oracle Turing machine $M$ that can query both the $L_1$ oracle as well as the $L_2$ oracle such that $M$ decides $L$. In other words, $L$ requires both the $L_1$ and $L_2$ oracles to be decided, but neither one alone suffices to decide $L$. I would like to come up with such languages $L$, $L_1$, and $L_2$. At first, I was hoping that the oracles for the rejecting and the accepting problems for Turing machines together could be queried to decide the halting problem (but neither oracle alone could be used decide it), but that turns out to be a dead end.

Now I'm wondering if I can approach the problem by trying to come up with two languages such that neither is Turing-reducible to the other, but I'm struggling to find examples.

A classical theorem of Sacks states that if $L$ is not computable, then it is almost surely not computable relative to a random oracle. In other words, if $O$ is a random oracle, then the probability that $L$ is computable given $O$ is zero.
Now take your favorite uncomputable $L$, and choose $L_1,L_2$ at random among all languages such that $L = L_1 \Delta L_2$ (here $\Delta$ is symmetric difference). Individually, $L_1,L_2$ are random oracles, and so almost surely $L$ is not computable given just $L_1$ or just $L_2$. However, it is clearly computable given both.
Another solution is to take any two incomparable Turing degrees $L_1,L_2$ and $L = \{ 0x : x \in L_1 \} \cup \{ 1x : x \in L_2 \}$. The proof then follows practically by definition.
• Unfortunately, my knowledge is pretty much limited to Sipser's textbook. What is meant by a computable language (I'm only familiar with Turing-computable functions)? Also, what does the $\Delta$ mean in this context? – NBose35 Mar 1 '17 at 2:50
• Computable is another term for Turing-computable – a better term, in my humble opinion. The symbol $\Delta$ stands for symmetric difference, the analog of XOR. – Yuval Filmus Mar 1 '17 at 2:51
• I think that a straightforward diagonalization argument would work. You construct two sets $A,B$ in steps, at step $i$ ensuring that (i) the $i$th program doesn't compute $A$, (ii) the $i$th program doesn't compute $B$, (iii) the $i$th program doesn't compute $A$ given an oracle for $B$, (iv) the $i$th program doesn't compute $B$ given an oracle for $A$. Each such point is handled by finding an input on which the language isn't already defined, running the program (setting values of the oracle if needed), and setting the value of the input accordingly. – Yuval Filmus Mar 1 '17 at 4:25