Given the following statements: (i) Recursive enumerable sets are closed under…
2012
Given the following statements:
(i) Recursive enumerable sets are closed under complementation
(ii) Recursive sets are closed under complementation
Which is/are the correct statements?
- A.
only (i)
- B.
only (ii)
- C.
both (i) and (ii)
- D.
neither (i) nor (ii)
Attempted by 26 students.
Show answer & explanation
Correct answer: B
Recursive sets are decidable, allowing complementation by swapping accept and reject states. Recursive enumerable sets lack this property; if closed under complement, RE would equal Recursive, contradicting undecidable problems.
A video solution is available for this question — log in and enroll to watch it.