GATE CS 2015 Set 2 Q21 — Undecidability

Let us analyze each statement individually:

• Statement I: The complement of every Turing decidable language is Turing decidable.
  This statement is True. Turing decidable (recursive) languages are closed under complementation. If a language $L$ is decided by a Turing machine $M$ (which halts on all inputs), we can construct a Turing machine $M'$ that decides the complement $\overline{L}$ by swapping the accepting and rejecting states of $M$.
• Statement III: If $L$ is a language in NP, $L$ is Turing decidable.
  This statement is True. The class $\text{NP}$ is a subset of the class of Turing decidable (recursive) languages ($\text{NP} \subseteq \text{Decidable}$). Any language in $\text{NP}$ can be decided by a deterministic Turing machine in exponential time by systematically exploring all branches of the non-deterministic computation tree.
• Statement II: There exists some language which is in NP but is not Turing decidable.
  This statement is False. Since $\text{NP} \subseteq \text{Decidable}$, every language in $\text{NP}$ is guaranteed to be Turing decidable.

Thus, only statements I and III are true, which corresponds to option D.