I'm looking at the following question from this handout:

The class of decidable languages is closed under union

My question is, does this hold in reverse? Is there a phrase for this? Basically, if $L_1 ∪ L_2$ is decidable would $L_1$ and $L_2$ be decidable as well?

I believe it does, by making one machine $M$ to emulate both on any given input string and have the following:

Save a copy of input somewhere (multitape)
Run M1
    If it accepts, accept
Reset the tape using copy
Run M2
    If it accepts, accept
Both machines have rejected, so reject

Does this work? If so, would this also apply in the case of intersection as well?

  • $\begingroup$ "I believe it does, by making one machine M to emulate both on any given input string and have the following" What is $M1$ supposed to be here? You only have $M$ to start with. $\endgroup$ – Alexey Romanov Feb 12 at 7:16

No, if $L_1\cup L_2$ is decidable $L_1$ and $L_2$ are not necessarily decidable.

Here's an example.

$$\begin{align} L_1 &= \text{any language that is not decidable.}\\ L_2 &= \Sigma^*\setminus L_1. \end{align}$$ $L_1\cup L_2$ is $\Sigma^*$, which is decidable. However, $L_1$ is not decidable. In fact, $L_2$ is not decidable, either.

The proof given in the preformatted block of the question is a proof for the original proposition, "if $L_1$ and $L_2$ are decidable, then $L_1\cup L_2$ is decidable". It is not a proof for its converse proposition.

To prove its converse proposition, all you can assume is a Turing machines that decides $L_1\cup L_2$. There is no way that you can construct a Turing machine that can decide $L_1$ from that machine.

Intuitively, one condition cannot imply two other conditions. That is, "$L_1 \cup L_2$ is decidable" cannot imply both "$L_1$ is decidable" and "$L_2$ is decidable"

Here are a few related exercises.

Exercise 1. Does $L_1 \cup L_2$ is regular imply $L_1$ is regular and $L_2$ is regular?

Exercise 2. Does $L_1 \cup L_2$ is context-free imply $L_1$ is context-free and $L_2$ is context-free?

Exercise 3. Does $L_1 \cup L_2$ is recursively enumerable imply $L_1$ is recursively enumerable and $L_2$ is recursively enumerable?

Exercise 4. Raise a question similar to the above question.

Exercise 5. If you know that $L_1\cup L_2$ and $L_1$ are both decidable, does that imply $L_2$ is decidable?

The case with intersection is the same. Please check question if $L_1$ and $L_2$ are languages over the same alphabet and $L_1\cup L_2$ is context free, at least one of them must be context free, its answer and its exercises.

  • $\begingroup$ Just to clarify, $L_2$ here is defined as an alphabet without $L_1$? $\endgroup$ – Andrew Raleigh Feb 11 at 23:11
  • $\begingroup$ Yes, in the example, $L_2$ is the language of words that are not in $L_1$. That backslash, "$\setminus$", means the minus operation of two sets. $\endgroup$ – Apass.Jack Feb 11 at 23:21
  • $\begingroup$ Is there a theorem behind $Σ^*$ being decidable? Google returns Kleene star but not a lot of information on $Σ^*$. $\endgroup$ – Andrew Raleigh Feb 12 at 0:19
  • 1
    $\begingroup$ Let Turing machine $\mathcal A=⟨\{q_0\}, \Gamma, b, \Sigma, q_0, \{q_0\}, \delta⟩$, where $\delta$ is not defined anywhere. That is, given any input, $\mathcal A$ just halts and accepts. Then $A$ is a Turing machine that accepts the language of all words, $\Sigma^*$. $\endgroup$ – Apass.Jack Feb 12 at 1:23
  • 1
    $\begingroup$ I'd add one more exercise: if you know that $L_1 \cup L_2$ and $L_1$ are both decidable, does that imply $L_2$ is decidable? $\endgroup$ – Alexey Romanov Feb 12 at 7:18

No. $\Sigma^*\cup L$ and $\emptyset\cap L$ are both decidable for every language $L$, whether $L$ is decidable or not.

Your proof shows that, if $L_1$ and $L_2$ are decidable, then so $L_1\cup L_2$. You started by assuming that $L_1$ and $L_2$ are decided by machines $M_1$ and $M_2$, and then you built a machine that decides $L_1\cup L_2$. But you were supposed to be proving the converse! (Which you can't, because it's not true.)

  • $\begingroup$ I don't really understand the sentence after "No." - are those counterexamples for the union and intersection decidability respectively? $\endgroup$ – Andrew Raleigh Feb 11 at 23:00
  • $\begingroup$ @AndrewRaleigh Yes: the union/intersection is decidable even if $L$ is undecidable. $\endgroup$ – David Richerby Feb 12 at 0:44
  • $\begingroup$ So in the case of intersection, $∅$ alone is not decidable, while $L$ is. How is $∅∩L$ then decidable? $\endgroup$ – Andrew Raleigh Feb 12 at 22:10
  • $\begingroup$ No, $\emptyset$ is definitely decidable and, for any $L$, $\emptyset\cap L = \emptyset$, which is decidable. But that's for any $L$, even undecidable ones. This tells you that $X\cup Y$ being decidable doesn't imply that $X$ and $Y$ are necessarily decidable. (In my example, one of them is and one of them isn't, but Apass.Jack's answer shows that you can have neither $X$ nor $Y$ decidable, even thought $X\cap Y$ is decidable. $\endgroup$ – David Richerby Feb 12 at 22:12
  • 1
    $\begingroup$ $\emptyset$ is decidable by the TM that rejects all inputs, yes. Rice's theorem is used to show that the set of Turing machines that reject all inputs is undecidable. More formally, that's the language of strings that encode Turing machines that reject all inputs. That langauge definitely isn't $\emptyset$. $\endgroup$ – David Richerby Feb 13 at 15:52

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.