2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – NBose35
    Commented Mar 1, 2017 at 2:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Mar 1, 2017 at 2:51
  • $\begingroup$ Unfortunately, I'm only familiar with computable functions. What does it mean to say that a language is computable? Is this just the same as saying that the language is Turing-recognizable? $\endgroup$
    – NBose35
    Commented Mar 1, 2017 at 2:55
  • 1
    $\begingroup$ A language is computable if there is a Turing machine that always halts and outputs Yes iff the input is in the language. $\endgroup$
    – Yuval Filmus
    Commented Mar 1, 2017 at 2:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Mar 1, 2017 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.