ISRO CS 2023 Q.58: solution and answer

Official answer: DSource: ISRO's revised and final answer key of 16 February 2024

1. Recursive (decidable) languages are closed under complement: take a decider for $L$ and swap its accept and reject outcomes. So statement (a) is true.

2. Every recursive language is recursively enumerable, because a decider is also a recogniser. The complement of a recursive language is recursive by (a), so it is also recursively enumerable. Statement (b) is true.

3. Suppose both $L$ and $\overline{L}$ are recursively enumerable. Run a recogniser for each on the same input, alternating one step at a time. Every string belongs to exactly one of $L$ and $\overline{L}$, so exactly one recogniser eventually accepts. The combined machine therefore always halts, accepting when the recogniser for $L$ accepts and rejecting when the recogniser for $\overline{L}$ accepts. This decides $L$, so $L$ is recursive. Statement (c) is true (Post's theorem).

4. Recursively enumerable languages are not closed under complement. The halting language $L_{\text{halt}}$ is recursively enumerable but not recursive. If its complement were also recursively enumerable, (c) would make $L_{\text{halt}}$ recursive, which is false. So the complement of $L_{\text{halt}}$ is not recursively enumerable, and statement (d) is false.

5. The statement that is NOT true is (d).