where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and

$L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$

is it possible that $L_{1}$ is decidable, $L_{2}$ is recognizable but not decidable

and $L_{3}$ is not recognizable?

If so please give an example, if not why?

By recognizable I mean Turing Recognizable.

To make things a little easier (I think!) I have reached a conclusion that it is very much possible, I only can't think of an example of such 3 languages.

  • $\begingroup$ Although the question has been answered already, you should give your post a better title. The current one is not even a bad title, it is not a title at all. Second, 2 of 3 tags you chose for your question are not related at all to your question. Last, use \emptyset instead of \phi if you want an emptyset symbol. $\endgroup$ – ttnick Mar 10 '18 at 14:08

Is is indeed possible.

Consider the halting problem set $$H = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space halts \big\}$$

and its complement $$\overline{H} = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space doesn't \space halt \big\}$$

We know that H is recognizable and not decidable. That means that $$\overline{H}$$ is not recognizable because, otherwise, H would be decidable.

Now take $$L_1 = \emptyset \space \big( decidable \big) $$ $$L_2 = H \space \big( recognizable \space and \space not \space decidable \big) $$ $$L_3 = \overline{H} \space \big( not \space recognizable \big)$$

We have that $$L_1 \cup L_2 \cup L_3 = \Sigma^*$$ and $$L_1 \cap L_2 = L_2 \cap L_3 = L_1 \cap L_3 = \emptyset$$

  • $\begingroup$ I think you are right on the money, except for this little issue I'm having. How do you know $\phi$ is not in H or it's complement? $\endgroup$ – Anwar Saiah Mar 10 '18 at 14:07
  • $\begingroup$ If it is in H then $$H \cap L_1 = L_1 = \emptyset$$ as wanted. Same applies to $$\overline{H}$$ So it doesn't really matter where it is. $\endgroup$ – Kyrylo Yefimenko Mar 10 '18 at 14:14
  • $\begingroup$ I have another open question could you take a look at it, cs.stackexchange.com/questions/88803/… $\endgroup$ – Anwar Saiah Mar 10 '18 at 14:51
  • $\begingroup$ @KyryloYefimenko Do you assume that all strings are of the form $\big(\langle M \rangle, w\big)$, or is $L_1$ actually the set of strings that do not code a TM with its input? $\endgroup$ – Hendrik Jan Mar 11 '18 at 1:31

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.