5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ @A.Schulz I would translate "conjunction" with intersection, and I think this is what Sam means? $\endgroup$
    – Raphael
    Commented Aug 1, 2012 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
    Commented Aug 1, 2012 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
    Commented Aug 1, 2012 at 21:32
  • $\begingroup$ @SamJones: I think it would help if you edited to use either properties or languages, but not both. $\endgroup$
    – Raphael
    Commented Aug 1, 2012 at 22:15
  • $\begingroup$ Define "real life". We're talking about theoretical computer science, after all. $\endgroup$
    – Patrick87
    Commented Aug 3, 2012 at 19:20

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 2, 2012 at 20:30
  • $\begingroup$ @SamJones Can you define "real" in some more precise way? What, specifically, do you want to see? $\endgroup$
    – Patrick87
    Commented Aug 3, 2012 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
    Commented Aug 12, 2012 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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