Recursively enumerable languages are not closed under
A)Complementation
B)Union
C)Intersection
D)None of the above

Question

Quizplus · Accepted Answer

Recursively enumerable languages are closed under union and intersection but not under complementation. This is because while we can construct a Turing machine that recognizes the union or intersection of two recursively enumerable languages, there is no guarantee that the complement of a recursively enumerable language is also recursively enumerable.

Recursively Enumerable Languages Are Not Closed Under