I am working on theory of computation problems, and I came across this one:

Show that for A and B, a language J exists such that $A \leq_T J$, $B \leq_T J$

The only $J$ I can think of for the moment is the language that uses a $TM$ $N$ which contains a recognizer $M1$ for $A$, and another recognizer $M2$ for $B$. $N$ uses oracle $J$ to check if input $x\in A U B$. If $J$ accepts, then it means that either $M1$ or $M2$ will halt, so $N$ can now simultate $M1$ and $M2$ simultaneously.

But I think there should be a simpler way to solve this..... any help?


Just define $J$ as $A\oplus B = \{m \mid m =2k \text{ if } k \in A, \text{ and } m =2k+1 \text{ if } k \in B \}$. Then $k \in A$ is decided by querying $2k \in A\oplus B$, and $k \in B$ is decided by querying $2k+1 \in A\oplus B$. Thus $A \leq_T A\oplus B$, $B \leq_T A\oplus B$.

This result is well known in the theory of computability. It establishes the least upper bound on the lattice of the Turing degrees of $A$ and $B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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