HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Examples of undecidable problems whose intersection is decidable

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#2982, answer score: 7

Revisions (0)

No revisions yet.