1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! Does my enumerator work as well? $\endgroup$ – David Faux Dec 17 '12 at 18:02
  • $\begingroup$ @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. $\endgroup$ – sdcvvc Dec 17 '12 at 21:05

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.