Recursive language and its properties

Definition

A language L is recursive (also called decidable or Turing-decidable) if there is a Turing machine M that halts on every input and accepts exactly the strings of L: M accepts w if w ∈ L and halts in a rejecting state (or with no move) if w ∉ L. Such a TM is called a decider or an algorithm for L.

This differs from a recursively enumerable (RE) language, where the TM must halt and accept for w ∈ L but may loop forever for w ∉ L.

Examples: every regular language and every CFL; { aⁿbⁿcⁿ }; the set of prime numbers in binary.

Properties

1. Closed under complement. Run the decider and swap accept and reject.
2. Closed under union and intersection. Run both deciders on the input (one after the other) and accept if either (union) or both (intersection) accept. Both always halt.
3. Closed under difference (L1 − L2 = L1 ∩ L2ᶜ), concatenation, Kleene star and reversal.
4. Recursive ⊂ RE. Every recursive language is RE, but not conversely (the halting language is RE but not recursive).
5. L is recursive if and only if both L and its complement Lᶜ are RE.
6. Membership is decidable: for a recursive L, the question "is w in L?" always has an algorithmic yes/no answer.
7. Hierarchy: regular ⊂ CFL ⊂ context sensitive ⊂ recursive ⊂ RE ⊂ all languages.
8. Recursive languages are not closed under arbitrary homomorphism (RE languages are).

If L is RE but not recursive, then its complement is not RE.