Topic: Theory of Computation
Which of the following statements is NOT true?
- A. If a language is recursive its complement is recursive
- B. If a language is recursive its complement is recursively enumerable
- C. If a language and its complement are recursively enumerable it is recursive
- D. If a language is recursively enumerable its complement is also recursively enumerable
Answer: D. If a language is recursively enumerable its complement is also recursively enumerable
Explanation: Recursively enumerable (RE) languages are not closed under complementation. The Halting problem is a classic example of an RE language whose complement is not RE. Statements (a), (b), and (c) are all fundamental theorems in computability.