Here is the my attempt:

Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings.

We build a Turing Machine(Oracle) $M$ on input $w$ :

  • Query oracle if $wa' \cup wb' \in J$.
  • If YES, Accept. Reject Otherwise.

Now we can safely deduce $w \in A \iff wa' \in J$ and $w \in B \iff wb' \in J. \: \square$

which is not very much different from THIS ANSWER.

Is there any way we can prove this using hierarchy of languages :

enter image description here


1 Answer 1


I don't think this proposition can be proved using the hierarchy of languages as illustrated in the question alone. That hierarchy of languages is too coarse to imply directly any implication between decidability of different languages.

Since the structure of the Turing degrees is extremely rich and complicated, it does not make much sense to stick to the general hierarchy of languages if one wants to find more about them, anyway.

The construction of $J$ in the question is good.

However, the Turing machine $M$, which accepts the language $A\cup B$, is not used at all. In particular, it has nothing to do with "we can safely deduce $w \in A \iff wa' \in J$ and $w \in B \iff wb' \in J$."

What should have been done is to show that given an oracle $O$ that decides $J$,

  • there is an oracle machine with access to $O$ that decides $A$ and
  • there is an oracle machine with access to $O$ that decides $B$.

For example, we can build oracle Machine $T_A$ that on input $w$:

  1. Query $O$ if $wa'\in J$.
  2. If YES, accept. Reject otherwise.

Since $w\in A\iff wa'\in J$, $T_A$ decides $A$.

  • $\begingroup$ I am not known to the idea of Turing Degrees yet also I have not yet seen the languages harder than recursively enumerable yet. So when we say $A \nleq_{T} J$ that means even an oracle cannot decide it? Thats a bit difficult to imagine because it seemed oracle can decide everything. I have to explain this this proposition to a friend but I wanted to without explicitly defining languages but nevertheless nice revelation that we can't. $\endgroup$
    – lemniscate
    Apr 9 at 7:43

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.