# Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the language accepted by a given pushdown automaton $M$ has that property. Clearly $P$ and $\lnot P$ are undecidable (for a given $M$) but $P \cap \lnot P$ is trivially decidable (it is always false).

I wonder if there are any "real life" examples which do not make use of the "trick" above? When I say "real life" I do not necessarily mean problems which people come across in their day to day life, I mean examples where we do not take a problem and it's complement. It would be interesting (to me) if there are examples where the intersection is not trivially decidable.

• @A.Schulz I would translate "conjunction" with intersection, and I think this is what Sam means? – Raphael Aug 1 '12 at 13:45
• @Raphael: Yepp, I mixed things up. I think "intersection" should be the right term, since we are speaking about languages, which are sets. – A.Schulz Aug 1 '12 at 14:05
• Sorry, I was thinking of properties of languages, ie. Does $L$ have $P$ and $Q$ but yes, I guess the proper formalism would be: is $L$ in $P \cap Q$. – Sam Jones Aug 1 '12 at 21:32
• @SamJones: I think it would help if you edited to use either properties or languages, but not both. – Raphael Aug 1 '12 at 22:15
• Define "real life". We're talking about theoretical computer science, after all. – Patrick87 Aug 3 '12 at 19:20

Let $L_1,L_2\subset \{a,b,c\}^*$ be two undecidable languages, and $L_3\subseteq \{a,b,c\}^*$ a decidable language. We define
Clearly, both $L_A$ and $L_B$ are not decidable, however their nonempty intersection $$L_A\cap L_B =\{c\,w \mid w\in L_3\}$$ is decidable.