Which of the following statements is NOT true?
2023
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
Attempted by 26 students.
Show answer & explanation
Correct answer: D
To identify the false statement, we review computability theory properties. Statement A is true because recursive languages are closed under complementation. Statement B is true because every recursive language is recursively enumerable (RE). Statement C is true; a language is recursive if and only if both it and its complement are RE. Statement D claims that if a language is RE, its complement is also RE. This is false; for example, the Halting Problem is RE, but its complement is not. Thus, Statement D is NOT true.