GATE CS 2014 Set 1 Q35 — Undecidability

To determine which option is NOT a viable possibility, we use a fundamental theorem in the theory of computation:

Theorem: A language $L$ is recursive (decidable) if and only if both $L$ and its complement $\bar{L}$ are recursively enumerable (r.e.).

Let's analyze each option based on this theorem:

• Option A: Neither $L$ nor $\bar{L}$ is r.e.
  This is a viable possibility. For example, if we take a language that is highly undecidable (beyond the class of r.e. and co-r.e. languages), neither the language nor its complement will be recursively enumerable.
• Option B: One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e.
  This is a viable possibility. For example, the Halting Problem language $H_P$ is r.e. but not recursive, whereas its complement $\overline{H_P}$ is not r.e.
• Option C: Both $L$ and $\bar{L}$ are r.e. but not recursive.
  According to the theorem, if both $L$ and $\bar{L}$ are r.e., then $L$ (and consequently $\bar{L}$) must be recursive. Therefore, they cannot be "r.e. but not recursive". This is not a viable possibility.
• Option D: Both $L$ and $\bar{L}$ are recursive.
  This is a viable possibility. The class of recursive languages is closed under complementation. For example, any regular or context-free language is recursive, and its complement is also recursive.

Thus, Option C is the only non-viable scenario.