Statement 1 : "For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine."
This statement is true.
Proof.
A non-deterministic Turing machine (NTM) may have multiple possible transitions from a given configuration. The set of strings accepted by such a machine is defined as those for which some computation path leads to an accepting state. A deterministic Turing machine (DTM) can simulate all possible computation paths of the NTM using a breadth-first search (or dovetailing) strategy over the configuration tree. Since a DTM can systematically explore all finite-length paths up to any depth, it will eventually find an accepting path if one exists. Therefore, the language recognized by any NTM is also recognized by some DTM. Hence, the statement holds.
Statement 2 : "Turing recognizable languages are closed under union and complementation."
This statement is false.
Proof.
The class of Turing recognizable (recursively enumerable) languages is closed under union: given recognizers $M_1$ and $M_2$ for languages $L_1$ and $L_2$, a recognizer for $L_1 \cup L_2$ can be constructed by simulating $M_1$ and $M_2$ in parallel (e.g., via interleaving steps) and accepting if either accepts.
However, this class is not closed under complementation. Suppose $L$ is Turing recognizable but not decidable (e.g., the halting problem $A_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ accepts } w \}$). Then its complement $\overline{L}$ cannot be Turing recognizable; otherwise, both $L$ and $\overline{L}$ would be recognizable, implying that $L$ is decidable—a contradiction. Therefore, the class of Turing recognizable languages is not closed under complementation, rendering the statement false.
Statement 3 : "Turing decidable languages are closed under intersection and complementation."
This statement is true.
Proof.
Let $L_1$ and $L_2$ be decidable languages, recognized by deciders $M_1$ and $M_2$.
- For complementation, construct a decider $M'$ that simulates $M_1$ on input $w$ and reverses its output: accept if $M_1$ rejects, and reject if $M_1$ accepts. Then $M'$ decides $\overline{L_1}$.
- For intersection, construct a decider $M''$ that simulates both $M_1$ and $M_2$ on $w$ and accepts only if both accept. Since both machines always halt, so does $M''$, and it decides $L_1 \cap L_2$.
Thus, the class of decidable (recursive) languages is closed under both intersection and complementation.
Statement 4 : "Turing recognizable languages are closed under union and intersection."
This statement is true.
Proof.
As noted in Statement 2, closure under union holds via parallel simulation.
For intersection, given recognizers $M_1$ and $M_2$ for $L_1$ and $L_2$, construct a recognizer that simulates $M_1$ and $M_2$ in an interleaved fashion. It accepts the input only if both simulations eventually accept. If $w \in L_1 \cap L_2$, then both machines will accept in finite time, and the combined machine will accept. If $w \notin L_1 \cap L_2$, the machine may loop but this is permissible for a recognizer. Hence, the intersection is also Turing recognizable.
$$
\color{skyblue} \boxed{\text{C. 2 only}}
$$
