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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented Dec 17, 2012 at 21:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.