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_2subset {a,b,c}^*$ be two undecidable languages, and $L_3subseteq {a,b,c}^*$ a decidable language. We define begin{align} L_A&:={a,w mid win L_1} cup {c,w mid win L_3}, L_B&:={b,w mid win L_2} cup {c,w mid win L_3} . end{align} Clearly, both $L_A$ and $L_B$ are not decidable, however their nonempty intersection $$ L_Acap L_B ={c,w mid win L_3}$$ is decidable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2982
