Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A \cap B$ be Turing-recognizable too?

I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in $A$ and then all the languages in $B$.

However, I also know that Turing-recognizable languages are not closed under complement, and $\overline{\bar{A} \cup \bar{B}} = A \cap B = C$, which seems to suggest that Turing-recognizable languages are not closed under intersection.

There is clearly a contradiction somewhere in my reasoning. Where is it?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Indeed, the recursively enumerable languages are closed under union and intersection, but not complement. This is not a contradiction: the formula $A \cap B = \overline{\overline{A} \cup \overline{B}}$ tells that a class closed under union and complement is closed under intersection, but does not tell anything otherwise.

A similar example: the set of finite subsets of $\mathbb N$ is clearly closed under union and intersection, but not complement.

share|improve this answer
    
Thanks! Does my enumerator work as well? –  David Faux Dec 17 '12 at 18:02
    
@David: Um, enumerators does not output languages as you wrote, but words but in a language. An enumerator for $A \cap B$ can be constructed in this way: run in parallel enumerators for $A$ and $B$. Whenever at some point a word has been enumerated by both enumerators, output it in the joint enumerator. –  sdcvvc Dec 17 '12 at 21:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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