GATE CS 2005 Q56 — Undecidability

To determine the correct statement, let's analyze the properties of the given languages:

1. For $L_1$ (Recursive Language):
   • The class of recursive languages is closed under complementation.
   • Since $L_1$ is recursive, its complement $L_1'$ is also recursive.
2. For $L_2$ (Recursively Enumerable but not Recursive):
   • According to a fundamental theorem in computability theory, a language $L$ is recursive if and only if both $L$ and its complement $L'$ are recursively enumerable (RE).
   • We are given that $L_2$ is RE but not recursive. Therefore, its complement $L_2'$ cannot be recursively enumerable (if $L_2'$ were RE, then $L_2$ would have to be recursive, which is a contradiction).

Combining these two results:

• $L_1'$ is recursive.
• $L_2'$ is not recursively enumerable.

This matches Option B.