Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?
A)I only
B)I and II
C)I and III
D)II and III

Question

Quizplus · Accepted Answer

I. Recursive languages are indeed closed under complementation because if a language is recursive, there exists a Turing machine that decides it, and by inverting the accept and reject states of this Turing machine, one can decide the complement of the language. II. Recursively enumerable languages are closed under union because if there are two recursively enumerable languages, there exist Turing machines that recognize each of them. A Turing machine can be constructed to recognize the union of these two languages by simulating both machines in parallel and accepting if either does. III. Recursively enumerable languages are not closed under complementation because there exist recursively enumerable languages whose complements are not recursively enumerable.

Consider the Following Statements