Question 31

Examine Statement I:
'The complement of every Turing decidable language is Turing decidable.'
If $L$ is decidable by a halting Turing Machine $M$, a machine $M'$ that flips the accept and reject halt states of $M$ decides $\overline{L}$. Thus, the class of decidable (recursive) languages is closed under complementation. Statement I is true.

Examine Statement II:
'There exists some language which is in NP but is not Turing decidable.'
Every language in NP can be decided by a non-deterministic Turing machine in polynomial time $O(n^k)$. A deterministic Turing machine can simulate all branches in $O(2^{n^k})$ time, which halts on every input. Thus, $\text{NP} \subseteq \text{EXPTIME} \subset \text{Decidable}$. Every language in NP is decidable. Statement II is false.

Examine Statement III:
'If $L$ is a language in NP, $L$ is Turing decidable.'
Since $\text{NP} \subseteq \text{Decidable}$, any language in NP is necessarily decidable. Statement III is true.

Statements I and III are true, corresponding to option D.