Recursive and Recursively Enumerable Languages

Recursively Enumerable (r.e.) Language

A language L is recursively enumerable (r.e.) if L = L(M) for some Turing Machine M. This means M accepts exactly the strings in L, but it may loop forever on strings not in L.

Recursive (Decidable) Language

A language L is recursive (or decidable) if L = L(M) for some total Turing Machine M. A total TM always halts (accepts or rejects) on every input. So, for a recursive language, there is an algorithm that always gives a yes/no answer.

Total Turing Machine

A total Turing Machine is a TM that halts on all possible inputs. It never enters an infinite loop. It always reaches the accept state (t) or the reject state (r).

Key Relationship: Recursive ⊆ r.e.

Every recursive language is recursively enumerable, but not every r.e. language is recursive. A recursive language has a total TM; an r.e. language might only have a TM that loops on "no" answers.

Closure: Recursive under Complement

The class of recursive languages is closed under complement. If L is recursive (decided by total TM M), then its complement ~L is also recursive: just swap the accept and reject states of M.

Closure: r.e. NOT under Complement

The class of recursively enumerable languages is NOT closed under complement. If L is r.e., ~L might not be r.e. (If both L and ~L were r.e., then L would actually be recursive).

Theorem: L and ~L are r.e. ⇒ L is Recursive

If a language L and its complement ~L are both recursively enumerable, then L is recursive (decidable). You can build a total TM that runs the TMs for L and ~L in parallel; one must halt and accept.

Proof Idea: "Dovetailing" Simulation

To prove L is recursive if L and ~L are r.e.: Build a new TM N that simulates M_L (for L) and M_~L (for ~L) in parallel on the same input. Whichever halts and accepts first determines the answer (accept if M_L accepts, reject if M_~L accepts). This new TM N always halts.

Example: {ww} is Recursive

The language {ww | w ∈ {a,b}*} is recursive. There exists a total TM (an algorithm) that always halts and correctly decides if a string is of that form (e.g., by finding the middle and comparing halves).

Decidable Property

A property P of strings is decidable if the set {x | P(x)} is a recursive language. There is an algorithm that, for any input x, always halts and correctly outputs whether P(x) is true.

Semidecidable Property

A property P is semidecidable if the set {x | P(x)} is a recursively enumerable language. There is a procedure (TM) that halts and outputs "yes" whenever P(x) is true, but may loop forever if P(x) is false.

Analogy: Decidable vs. Semidecidable

Decidable: A total TM; always answers "yes" or "no". Semidecidable: A partial TM; always answers "yes" if true, but may say nothing (loop) if false. A "yes" answer is guaranteed, but a "no" answer is not.

Why the Distinction Matters

This hierarchy is crucial for understanding the limits of computation. It separates problems we can always solve with an algorithm (recursive/decidable) from those we can only partially solve (r.e./semidecidable), leading to the concept of undecidable problems.

Co-recursively Enumerable

A language L is co-recursively enumerable if its complement ~L is recursively enumerable. The class of co-r.e. languages is the complement of the class of r.e. languages.

The Big Picture

Sets/Languages form a hierarchy:

1. Recursive (Decidable): TM always halts with answer.
2. Recursively Enumerable (Semidecidable): TM halts on "yes", may loop on "no".
3. Co-recursively Enumerable: Complement is r.e.
4. None of the above: Some languages are not even r.e.