patternMinor
Examples of undecidable problems whose intersection is decidable
Viewed 0 times
undecidablewhoseexamplesdecidableintersectionproblems
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#2982, answer score: 7
Revisions (0)
No revisions yet.