Recursive and Recursively Enumerable Sets — Mathematics Knowledge System

Overview

A set (or language) is recursive — also called decidable — if some Turing machine can always correctly determine, for any input, whether it belongs to the set, and always halts with an answer. A set is recursively enumerable (r.e.) — also called Turing-recognizable — if some Turing machine halts and accepts every member of the set, but may run forever on non-members instead of confidently rejecting them. Every recursive set is recursively enumerable, but the halting problem is the canonical example of an r.e. set that is not recursive, showing the containment is strict. This distinction — between machines that always give a definite yes/no answer versus machines that can confirm 'yes' but never definitively say 'no' — is the fundamental fault line of computability theory.

Intuition

Imagine a search engine for mathematical proofs: given a candidate theorem, it exhaustively tries every proof of every length in order. If the theorem IS provable, the search will eventually find a proof and confidently say 'yes, provable' — the set of provable theorems is recursively enumerable, because 'yes' answers are always eventually confirmed. But if the theorem is NOT provable, the search just keeps running forever with no way to know if it should give up — there's no guaranteed moment to confidently declare 'no, unprovable.' A set is recursive (fully decidable) only when you additionally have some other trick that lets you confidently halt and say 'no' too, for every non-member — not just search endlessly for confirmation of 'yes.'

Formal Definition

Definition

Let L be a language (set of strings). The two key definitions, and their relationship:

L \text{ is recursive (decidable)} \iff \exists \text{ TM } M: \ M \text{ halts on every input, accepting iff the input} \in L

Recursive / decidable

L \text{ is recursively enumerable} \iff \exists \text{ TM } M: \ M \text{ halts and accepts iff the input} \in L \ (\text{may loop forever if input} \notin L)

Recursively enumerable / Turing-recognizable

L \text{ is recursive} \iff L \text{ and its complement } \bar{L} \text{ are both recursively enumerable}

Key characterization theorem

\text{Recursive} \subsetneq \text{Recursively enumerable}

Strict containment (e.g. HALT is r.e. but not recursive)

Notation

Notation	Meaning
$\text{r.e.}$	Recursively enumerable — accepted (but possibly not rejected) by some Turing machine that halts on all 'yes' inputs
$\bar{L}$	The complement of L (all strings NOT in L)
$\text{co-r.e.}$	A set whose complement is recursively enumerable

Theorems

Theorem 1: Recursive = r.e. and co-r.e.

\text{A language } L \text{ is recursive if and only if both } L \text{ and } \bar{L} \text{ are recursively enumerable.}

Theorem 2: HALT is r.e. but not recursive

\text{The halting problem HALT is recursively enumerable (simulate and accept on halting) but not recursive (Turing's undecidability theorem), so its complement is NOT recursively enumerable.}

Theorem 3: Closure properties

\text{The recursive sets are closed under complement, union, and intersection. The r.e. sets are closed under union and intersection, but NOT closed under complement in general.}

Applications

Static analysis and verification tools are built around this distinction: a tool that can confirm 'this program definitely has property X' (r.e.) is achievable even when a tool that always correctly answers 'does this program have property X, yes or no?' (recursive) is not — this is why bug-finders report confirmed bugs but can't guarantee a program bug-free.

Worked Examples

Build a machine U that, given ⟨M,w⟩, simulates M running on w step by step.
$U(\langle M, w \rangle): \text{simulate } M \text{ on } w$
If the simulated M ever halts, U halts and accepts; if M never halts, U simply never stops simulating — U doesn't need to reject, only to correctly accept every true 'halts' instance eventually.
$M \text{ halts on } w \implies U \text{ eventually halts and accepts}$

Answer: HALT is recursively enumerable: the universal simulator U accepts every ⟨M,w⟩ where M halts on w (eventually), satisfying the r.e. definition, even though U itself may run forever on non-halting instances.

Practice Problems

Difficulty 7/10

Prove that if HALT were recursive, then its complement would also have to be recursively enumerable — and explain why this, combined with the known fact that HALT's complement is NOT r.e., re-proves that HALT cannot be recursive.

Difficulty 6/10

A security research team builds a tool that, given a program, searches for a proof that the program contains a specific vulnerability pattern, and reports 'vulnerability confirmed' if it finds one. It may run indefinitely if no vulnerability exists. Which computability concept describes this tool's behavior, and what can it NOT guarantee?

Difficulty 6/10

A language L is recursive if and only if:

L is recursively enumerableL and its complement are both recursively enumerableL is finiteL is context-free

Difficulty 5/10

Why are the recursively enumerable sets closed under union and intersection, but NOT (in general) under complement?

Common Mistakes

Common Mistake

Treating 'recursively enumerable' and 'recursive' as synonyms.

Recursive (decidable) means a machine always halts with a correct yes/no answer. Recursively enumerable only guarantees halting-and-accepting on 'yes' instances — on 'no' instances the machine may run forever. The halting problem is the classic example that is r.e. but not recursive.

Common Mistake

Assuming that because a set is recursively enumerable, its complement must be too.

This is false in general — HALT is the standard counterexample: HALT is r.e., but its complement (pairs where the machine does NOT halt) is provably not r.e., which is exactly why HALT itself is not recursive.

Common Mistake

Believing 'recursively enumerable' means the elements can be listed in a nice, orderly (e.g. increasing) sequence.

'Enumerable' here just means there is some Turing machine that can eventually generate/confirm every element of the set (possibly out of order, possibly very inefficiently) — not that there's a natural or efficient ordering.

Quiz

Historical Background

The concepts of recursive and recursively enumerable sets emerged from the 1930s work of Alan Turing, Alonzo Church, Kurt Gödel, and Stephen Kleene on defining computability. Emil Post's 1944 paper 'Recursively Enumerable Sets of Positive Integers and Their Decision Problems' gave the theory its modern name and systematically studied the structure of r.e. sets, including the existence of r.e.-but-not-recursive sets like the halting problem, and laid groundwork for the later study of Turing degrees.

1936
Turing and Church formalize computable functions, implicitly defining decidable (recursive) sets
Alan Turing, Alonzo Church
1943
Stephen Kleene develops the theory of general recursive functions
Stephen Kleene
1944
Emil Post publishes foundational work on recursively enumerable sets and their decision problems
Emil Post

Summary

Recursive (decidable): a TM halts on every input, always giving a correct accept/reject answer.
Recursively enumerable (Turing-recognizable): a TM halts and accepts every true member, but may loop forever on non-members.
L is recursive iff both L and its complement are recursively enumerable.
HALT is the canonical example that is r.e. but not recursive — its complement is not r.e., which is exactly why HALT isn't decidable.
R.e. sets are closed under union and intersection but not (in general) complement.

References

WebsiteWikipedia — Recursively enumerable set
PaperEmil L. Post, 'Recursively Enumerable Sets of Positive Integers and Their Decision Problems', Bulletin of the AMS, 1944