1
$\begingroup$

Question:

Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are).

Definition of a decidable language: A language L is decidable if there exists a Turing-machine $M$ such that on input $x$, $M$ accepts if $x \in L$, otherwise $M$ rejects $x$.

Proof:

By the definition of a decidable language, we know that $M$ over $\Sigma$ accepts input $x \in L_1 \cap L_2$ and rejects $x$ otherwise. This means we can construct another Turing-machine $M'$ such that, $M'$ accepts $x \in \overline{L_1} \cup \overline{L_2}$ when $M$ rejects and reject when $M$ accepts. We know that both $L(M)$ and $L(M')$ are both decidable languages. Since $L(M) \cup L(M') = \Sigma^*$, $\Sigma^*$ is decidable and so $L_1 \subseteq \Sigma^*$, $L_1$ must be a decidable language. By the same logic $L_2 \subseteq \Sigma^*$ which means $L_2$ is also a decidable language.

$\endgroup$
  • $\begingroup$ How does $L_1$ - decidable follow from $L(M) \cup L(M') = \Sigma^*$ and $L_1 \subseteq \Sigma^*$? $\endgroup$ – xyzzyz Jan 28 '14 at 22:00
  • $\begingroup$ Oh I was assuming that $\Sigma^*$ is decidable since $L(M) \cup L(M')$ are both decidable? I missed putting that in. $\endgroup$ – 1337holiday Jan 28 '14 at 22:07
  • $\begingroup$ $\Sigma^*$ is always decidable : it is recognized by a Turing machine which always accepts. $\endgroup$ – fkraiem Jan 28 '14 at 22:08
  • $\begingroup$ hmm yes that makes sense, I'm confused about how $M$ works then, when it says that $M$ accepts $x \in L_1 \cap L_2$, does it mean that $M$ checks if $x \in L_1$ and $x \in L_2$, in which case accept, otherwise reject? $\endgroup$ – 1337holiday Jan 28 '14 at 22:13
  • 1
    $\begingroup$ I'd suggest supposing that $L_1$ contains a bunch of nonsense and {a,b,c}, then $L_2$ contains different nonsense and {a,b,c}. Then suppose further that $L_1 \cap L_2 = \{a,b,c\}$ is decidable. What would you say about $L_1$ and $L_2$, then? $\endgroup$ – jasotastic Jan 28 '14 at 22:20
4
$\begingroup$

Let $U$ be an undecidable subset of the natural numbers. Let $L_1$ be the set of all $2x$, where $x$ ranges over $U$, and let $L_2$ be the set of all $2x+1$, where $x$ ranges over $U$.

Then $L_1\cap L_2$ is empty, hence trivially decidable, but $L_1$ and $L_2$ are not.

Remark: In more "language" language, let $L_0$ be an undecidable language over the alphabet $\{x\}$. Let $L$ be the same language, considered over the alphabet $\{x,a,b\}$. Let $L_1$ be obtained from $L$ by replacing every occurrence of $t$ by the letter $a$, and let $L_2$ be obtained in the same way, using the letter $b$. Then $L_1\cap L_2$ is clearly decidable, while $L_1$ and $L_2$ are not.

$\endgroup$
  • $\begingroup$ I see, but what property of $L_1$ and $L_2$ makes them undecidable, is it because they are an infinite set? $\endgroup$ – 1337holiday Jan 28 '14 at 22:21
  • $\begingroup$ No. Suppose that we had an algorithm for deciding, for any $y$, whether $y$ is in $L_1$. Then we could input $2x$ into that algorithm, and we would get an algorithm for deciding whether $x\in U$. By the definition of $U$, there is no such algorithm. (And you know that there are undecidable subsets of the natural numbers, just pick your favourite.) $\endgroup$ – André Nicolas Jan 28 '14 at 22:26

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.