---
title: "Recursive iff language and complement are RE"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:recursive-iff-complement-re"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-iff-complement-re
site: BCT Engineering
---

# Recursive iff language and complement are RE

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2071 Chaitra; 2073 Chaitra (asked 2 times)
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-iff-complement-re
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Prove that a language is recursive if and only if both it and its complement are recursively enumerable. (That is, if a language L and its complement are both recursively enumerable, then L is recursive.)

## Short answer

If L is recursive, a decider M for L also decides complement by swapping accept/reject, so both are RE. Conversely, if L and complement are RE, run acceptors for both in parallel; one will accept, so we can decide L. Thus L is recursive.

## Answer

**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**.

```text
         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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. To show a recursive L has an RE complement, what is done to its decider M?
   A. Make M run forever on non-members
   B. Swap the accepting and rejecting outcomes
   C. Remove all states
   D. Add a second tape
   Answer: B. Swapping outcomes gives a machine that halts always and accepts the complement, so it is recursive and hence RE. (Key point: Forward direction)

2. In the reverse direction, how does M use M1 (for L) and M2 (for L complement)?
   A. Runs M1 to completion, then M2
   B. Runs M2 only
   C. Runs them alternately one step at a time
   D. Runs them on different inputs
   Answer: C. M1 might loop forever, so M alternates single steps of M1 and M2 so whichever accepts is eventually found. (Key point: Lock-step simulation)

3. In the combined machine M, what happens when M2 accepts?
   A. M accepts
   B. M loops
   C. M rejects
   D. M restarts M1
   Answer: C. M2 accepting means w is in the complement, so w is not in L and M rejects. (Key point: Decision rule)

4. Why does M always halt?
   A. Every string is in exactly one of L or its complement, so one of M1, M2 accepts in finite time
   B. Both M1 and M2 always halt
   C. M has only one state
   D. The input is finite so M halts
   Answer: A. w lies in L or in its complement; the corresponding recogniser halts and accepts, even if the other loops. (Key point: Why it halts)

## Related in Theory of Computation

- [Recursive and recursively enumerable languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-vs-re-examples) — Theory of Computation, chapter 4
- [Recursive language and its properties](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-language-properties) — Theory of Computation, chapter 4, asked 2×

## Related in other subjects

- [Prove n even iff 7n+4 even](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aprove-n-even-iff-7n-plus-4-even) — Discrete Structure, chapter 1