Consider the following statements. I. The complement of

Home » Theory of Computation » Theory of computation miscellaneous » Question

Consider the following statements.
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?

1. Only II
2. Only III
3. Only I and II
4. Only I and III

Correct Option: D

Turing decidable ⇒ Recursive language
Turing recognizable ⇒ Recursive enumerable language
(I) Complement of turning decidable language is decidable which is true.
(III) True (Theorem)
Which violates (II). Hence correct option is (d).