Recursive iff language and complement are RE

Theorem. A language L is recursive if and only if both L and its complement Lᶜ = Σ* − L are recursively enumerable (RE).

(⇒) Recursive implies L and Lᶜ are RE

Let M be a TM that decides L (it always halts).

• M itself accepts L, so L is RE.
• Build M′ from M by swapping the accepting and rejecting outcomes: M′ accepts exactly when M rejects. M′ halts on every input and accepts Lᶜ. Hence Lᶜ is recursive, so also RE.

(⇐) If L and Lᶜ are RE, then L is recursive

Let M1 be a TM that accepts L (halts and accepts every w ∈ L) and M2 a TM that accepts Lᶜ.

Construct a two-tape TM M that, on input w:

1. Copies w to both tapes.
2. Simulates M1 on tape 1 and M2 on tape 2 alternately, one step at a time (a step of M1, then a step of M2, and so on).
3. If M1 accepts, M accepts. If M2 accepts, M rejects.

         input w
        /       \
     M1 (for L)  M2 (for Lc)
        \       /
    run in lock-step (1 step each)
      M1 accepts -> ACCEPT
      M2 accepts -> REJECT

Why this works. Every string w lies in exactly one of L or Lᶜ.

• If w ∈ L, then M1 eventually halts and accepts (M2 may loop forever, but it does not matter).
• If w ∉ L, then w ∈ Lᶜ, so M2 eventually halts and accepts.

So exactly one of M1, M2 accepts in finite time, and the combined machine M always halts with the correct answer. Therefore M is a decider for L, and L is recursive.

Consequence

If L is RE but not recursive (for example the halting language), then Lᶜ cannot be RE. Otherwise L would be recursive by this theorem.