Question 17

Evaluate the properties of recursively enumerable languages:

1. Complementation: RE languages are not closed under complementation (for example, the halting problem language $L_H$ is RE, but its complement $\overline{L_H}$ is not RE).
2. Intersection: If $L_1$ and $L_2$ are accepted by Turing machines $M_1$ and $M_2$, a Turing machine can simulate $M_1$ and $M_2$ sequentially on the input, accepting if and only if both accept. Thus, RE languages are closed under intersection.
3. Subset relation: Every recursive language is RE ($R \subseteq RE$), so RE is a superset of recursive languages, not a subset.
4. Countability: Each RE language is recognized by some Turing machine. Every Turing machine can be encoded as a finite binary string, so the set of all Turing machines is countably infinite. Therefore, the set of all RE languages is countable.

Thus, only statement B is true.