Recursive and recursively enumerable languages

Recursively enumerable (RE) languages

A language L is recursively enumerable (Turing-recognisable) if some Turing machine M accepts it: for w ∈ L, M halts in an accepting state; for w ∉ L, M either halts in a non-accepting state or runs forever. M recognises L but need not decide it.

Example: the halting language H = { ⟨M, w⟩ : M halts on input w }. Simulate M on w; if the simulation halts, accept. If M loops, the simulator loops. So H is RE but not recursive.

Recursive languages

A language L is recursive (decidable) if some TM M halts on every input, accepting w ∈ L and rejecting w ∉ L. Such a machine is an algorithm.

Examples:

• { aⁿbⁿcⁿ : n ≥ 1 }: mark one a, one b, one c repeatedly and check nothing remains. It always halts.
• The set of prime numbers (in binary or unary): try all possible divisors; this halts.
• Every regular language and every context free language is recursive.

Relationship

 all languages
 ┌──────────────────────────────┐
 │  RE languages                │
 │  ┌────────────────────────┐  │
 │  │ recursive languages    │  │
 │  │  ┌──────────────────┐  │  │
 │  │  │ CFL ⊃ regular    │  │  │
 │  │  └──────────────────┘  │  │
 │  └────────────────────────┘  │
 │   (H lies here: RE, not rec.)│
 └──────────────────────────────┘

• Every recursive language is RE, but not every RE language is recursive.
• L is recursive if and only if both L and its complement are RE.
• The complement of H is not RE, so it lies outside RE.