Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 59 ยท Decidability and Computability

Recursive and Recursively Enumerable Languages

Understand Turing-decidable (recursive) and Turing-recognizable (recursively enumerable) languages, enumerators, closure properties and why co-RE matters, with Python.

A Turing machine on an input has three possible fates: accept, reject, or run forever. That third possibility splits the languages Turing machines can handle into two classes.

  • A language is recursive (also called Turing-decidable or just decidable) if some Turing machine halts on every input, accepting exactly the members and rejecting all others. It is an algorithm in the strict sense: it always gives an answer.
  • A language is recursively enumerable (RE) (or Turing-recognizable, semi-decidable) if some Turing machine accepts exactly the members. On non-members it may reject or loop forever.

Every decidable language is recognizable. The interesting question is whether the converse holds, and the answer, proved in the halting problem lesson, is no.

Decide or recognize

Recursive (decidable) Halts on every input with yes or no.
Recursively enumerable Halts with yes on members; may hang otherwise.
Not RE No machine even confirms the members.

Recursive means RE, but not the other way round.

1 / 2

The big picture

flowchart TB
    A["Regular"] --> B["Deterministic context-free"] --> C["Context-free"] --> D["Context-sensitive"] --> E["Recursive (decidable)"] --> F["Recursively enumerable"] --> G["All languages"]

Each class is strictly contained in the next. Beyond RE there are languages no Turing machine recognizes at all.

Class Machine Always halts?
Regular DFA / NFA yes
Context-free PDA yes
Context-sensitive LBA yes
Recursive Turing machine that halts on all inputs (decider) yes
RE Turing machine (recognizer) only on members

Recognizers and deciders in code

To see why recognition is weaker, look at a language where the natural recognizer searches. Let L be the perfect squares. A recognizer for L tries i = 0, 1, 2, โ€ฆ and accepts when iยทi = n. For a non-square it never finds such an i: if written naively it searches forever. That is a legitimate recognizer, though not a decider.

The key fact about the two classes is:

Theorem. A language L is recursive if and only if both L and its complement Lฬ„ are recursively enumerable.

Proof idea. If L is decidable, so is Lฬ„ (swap the answers), so both are RE. Conversely, given a recognizer M1 for L and a recognizer M2 for Lฬ„, run them in parallel, one step each in turn. Every string is either in L or in Lฬ„, so one of the two machines will eventually accept. If M1 accepts, answer yes; if M2 accepts, answer no. This is a decider.

The simulation below uses Python generators as step-by-step machines: each yield is one step, and return means "accepted".

Python Two recognizers make a decider

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Running the square recognizer alone on 50 never ends, but running both together always ends with an answer. The loop in decide is dovetailing: alternate steps so that neither machine can block the other.

Enumerators

A second description of RE languages uses an enumerator: a machine that prints a list of strings, possibly infinite, with no input. L is RE if and only if some enumerator prints exactly the members of L (in any order, perhaps with repeats).

  • Enumerator โ‡’ recognizer. Given w, run the enumerator; accept if w ever appears.
  • Recognizer โ‡’ enumerator. List all strings s1, s2, s3, โ€ฆ in shortlex order. For k = 1, 2, 3, โ€ฆ run the recognizer on each of s1 โ€ฆ sk for k steps; print every string that has accepted. This is dovetailing: no single non-halting run can block the process.

This explains the name "recursively enumerable": the members can be listed, but their order of appearance does not reveal which strings are left out, because the list may be endless.

The enumerator below lists numbers whose Collatz sequence (halve if even, otherwise 3n+1) reaches 1. Whether it reaches 1 for every number is a famous open question. Recognition is easy (just run the sequence); we do not know whether the language is decidable by an obvious method.

Python Enumerating an RE language by dovetailing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers appear in the order in which their runs finish, not in numerical order: the output begins 1, 2, 4, 3, 5, 8, 6, 10, 16, 12, 13, 7, 11, โ€ฆ, with 7 (16 steps) arriving after 16 (4 steps). A number whose sequence is long finishes late, so it appears much later than a small number with a short sequence. If some number never reached 1, it would simply never appear in the list, and we would not know about it.

Closure properties

Operation Recursive RE
Union yes yes
Intersection yes yes
Concatenation yes yes
Kleene star yes yes
Complement yes no
Reversal yes yes

The RE class is not closed under complement. If it were, the theorem above would make every RE language recursive, which the halting problem refutes. Languages whose complement is RE are called co-RE. A language that is both RE and co-RE is recursive. For each language exactly one of these four cases holds: recursive; RE only; co-RE only; neither.

Languages that are not even RE

Counting arguments (the next lesson) show that most languages are not RE, because there are only countably many Turing machines but uncountably many languages. A concrete one is the complement of the halting problem (strings โŸจM, wโŸฉ where M does not halt on w): to confirm "does not halt" you would have to watch forever.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the difference between recursive and recursively enumerable languages?

    A decider must always halt; a recognizer may loop on non-members.
  2. 2. If both L and its complement are recursively enumerable, then L is...

    Run both recognizers in parallel; exactly one accepts, giving a decider.
  3. 3. Which closure property distinguishes RE languages from recursive ones?

    If RE were closed under complement, RE would equal recursive, which is false.
  4. 4. Why does the enumerator for an RE language use dovetailing?

    Interleaving steps of many runs ensures every halting run eventually finishes, even if others never do.

Summary

  • Recursive (decidable): a machine halts on every input with the right answer.
  • RE (recognizable): a machine accepts exactly the members and may loop on the rest.
  • L is recursive iff both L and Lฬ„ are RE (run both recognizers in parallel).
  • RE languages are exactly those that an enumerator can list, using dovetailing.
  • Recursive languages are closed under complement; RE languages are not.
  • Some languages are not RE at all.

Next: Countability and decidable problems