Question 45

Post's Theorem is a fundamental theorem in computability theory:
'A language $L$ is recursive (decidable) if and only if both $L$ and its complement $\bar{L}$ are recursively enumerable (Turing-recognizable).'

Let us evaluate each possibility:

• (A) Viable: Both $L$ and $\bar{L}$ can be non-recursively enumerable (e.g., diagonal language or Kolmogorov complexity languages).
• (B) Viable: One can be r.e. but undecidable (such as the Halting Problem $H$), while its complement $\bar{H}$ is not r.e.
• (C) Not viable: If both $L$ and $\bar{L}$ were recursively enumerable, then by Post's theorem, we could run enumerators/recognizers for both in parallel; one of them must halt, making $L$ decidable (recursive). Thus, it is impossible for both $L$ and $\bar{L}$ to be r.e. without being recursive.
• (D) Viable: If $L$ is recursive, $\bar{L}$ is also recursive, so both are recursive.

Hence, possibility C is NOT viable.