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.

  • $\begingroup$ @A.Schulz I would translate "conjunction" with intersection, and I think this is what Sam means? $\endgroup$ – Raphael Aug 1 '12 at 13:45
  • $\begingroup$ @Raphael: Yepp, I mixed things up. I think "intersection" should be the right term, since we are speaking about languages, which are sets. $\endgroup$ – A.Schulz Aug 1 '12 at 14:05
  • $\begingroup$ 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$. $\endgroup$ – Sam Jones Aug 1 '12 at 21:32
  • $\begingroup$ @SamJones: I think it would help if you edited to use either properties or languages, but not both. $\endgroup$ – Raphael Aug 1 '12 at 22:15
  • $\begingroup$ Define "real life". We're talking about theoretical computer science, after all. $\endgroup$ – Patrick87 Aug 3 '12 at 19:20

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.

  • $\begingroup$ Yeah, that's better than my exmaple. I was just wondering if this ever crops up in any "real" situations? I was hoping there would be lots of examples. $\endgroup$ – Sam Jones Aug 2 '12 at 20:30
  • $\begingroup$ @SamJones Can you define "real" in some more precise way? What, specifically, do you want to see? $\endgroup$ – Patrick87 Aug 3 '12 at 19:21
  • $\begingroup$ I want to see an instance of this phenomenon (where the intersection isn't trivial) in someone's research in any area of science. Preferably an instance where the intersection is interesting and gives rise to a non-trivial algorithm. I realize that this may not be as common as I originally suspected so I will accept the above answer. If something fitting my description above is posted at a later date then I will change which answer is accepted. $\endgroup$ – Sam Jones Aug 12 '12 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.