GATE CS 2008 Q13 — Undecidability

This is a fundamental theorem in the theory of computation regarding the relationship between recursive and recursively enumerable (RE) languages.

Theorem: A language $L$ is recursive if and only if both $L$ and its complement $\overline{L}$ are recursively enumerable.

Proof Sketch:

• If $L$ is recursive: There exists a Turing Machine (TM) $M$ that halts on every input $w$, accepting if $w \in L$ and rejecting if $w \notin L$. Since $M$ halts on all inputs, it also serves as an recognizer for $L$. By swapping the accept and reject states of $M$, we get a TM that decides $\overline{L}$. Thus, both $L$ and $\overline{L}$ are recursively enumerable.
• If both $L$ and $\overline{L}$ are recursively enumerable: Let $M_1$ be the TM that recognizes $L$, and $M_2$ be the TM that recognizes $\overline{L}$. For any input string $w$:
  • We can run $M_1$ and $M_2$ in parallel (by interleaving their execution steps).
  • Since $w$ must belong to either $L$ or $\overline{L}$, exactly one of $M_1$ or $M_2$ is guaranteed to halt and accept $w$ in a finite number of steps.
  • If $M_1$ accepts, we halt and accept.
  • If $M_2$ accepts, we halt and reject.
  Since this combined machine always halts and correctly decides membership in $L$, the language $L$ is recursive.

Therefore, if $L$ and $\overline{L}$ are recursively enumerable, then $L$ must be recursive.