Examples of undecidable problems whose intersection is decidable

Problem Detail: 

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.

Asked By : Sam Jones

Answered By : A.Schulz

So here is a example, which is probably not as nice as you wanted it to be, but less trivial than the one you have mentioned.

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

\begin{align} L_A&:=\{a\,w \mid w\in L_1\} \cup \{c\,w \mid w\in L_3\}, \\ L_B&:=\{b\,w \mid w\in L_2\} \cup \{c\,w \mid w\in L_3\} .\\ \end{align}

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2982