A set is recursively enumerable if there is an algorithm that can list its elements.

The older name is recursively enumerable, often abbreviated as r.e. The modern name is computably enumerable, often abbreviated as c.e. Both terms refer to the same idea.

A set $A \subseteq \mathbb{N}$ is recursively enumerable if there is a Turing machine that prints exactly the elements of $A$ :

A = {a_0, a_1, a_2, a_3, \dots}

The machine may run forever. It does not need to print the elements in order. It may also print the same element more than once, although duplicates can be removed by another computable procedure.

Enumeration

The simplest way to understand an r.e. set is by listing.

For example, the set of even natural numbers is r.e.:

0, 2, 4, 6, 8, \dots

The set of prime numbers is also r.e.:

2, 3, 5, 7, 11, 13, \dots

These examples are not only r.e.; they are computable. Given a number $n$ , we can decide whether $n$ is even or prime.

The important point is that r.e. sets may be harder than computable sets. An r.e. set can be listable without being decidable.

Semi-Decidability

There is another equivalent way to define r.e. sets.

A set $A$ is recursively enumerable if there is a machine $M$ such that:

x \in A \quad \Longrightarrow \quad M(x) \text{ eventually accepts}

and:

x \notin A \quad \Longrightarrow \quad M(x) \text{ either rejects or runs forever}

Usually, we simplify this by saying:

x \in A \quad \Longleftrightarrow \quad M(x) \text{ eventually accepts}

The machine must accept members of $A$ . For nonmembers, it has no obligation to halt.

This is called semi-decidability. Positive answers can be confirmed. Negative answers may remain unresolved forever.

Decidable Versus Recursively Enumerable

Every decidable set is recursively enumerable.

If $A$ is decidable, then we can enumerate it by checking:

0,1,2,3,\dots

For each number $n$ , run the decision procedure for $A$ . If it says yes, print $n$ .

So:

A \text{ decidable} \quad \Longrightarrow \quad A \text{ recursively enumerable}

The converse fails. Some r.e. sets are not decidable.

The standard example is the halting set:

K = {e : \text{program } e \text{ halts on input } e}

This set is r.e. because we can simulate programs step by step. Whenever program $e$ halts on input $e$ , we eventually discover that and print $e$ .

But $K$ is not decidable. There is no algorithm that always decides whether an arbitrary program halts on its own code.

Thus:

K \text{ is r.e.}

but:

K \text{ is not computable}

Why the Halting Set Is Enumerable

The enumeration of $K$ uses dovetailing.

Instead of running one program forever, we run many computations in stages:

stage $0$ : run program $0$ for $0$ steps
stage $1$ : run programs $0,1$ for $1$ step
stage $2$ : run programs $0,1,2$ for $2$ steps
stage $3$ : run programs $0,1,2,3$ for $3$ steps

Whenever a computation halts, we print its program index.

This guarantees that every halting computation is eventually found. A nonhalting computation simply never contributes an output.

Complements

If $A$ is decidable, then both $A$ and its complement are r.e.

The complement is:

\overline{A} = \mathbb{N} \setminus A

If we can decide membership in $A$ , then we can also decide membership in $\overline{A}$ .

A key theorem says the converse is true:

A \text{ is computable} \quad \Longleftrightarrow \quad A \text{ is r.e. and } \overline{A} \text{ is r.e.}

The idea is simple. Run the enumerator for $A$ and the enumerator for $\overline{A}$ in parallel. Given input $x$ , wait until $x$ appears in one of the two lists. Since every number belongs to exactly one of them, it must eventually appear in one list. Then we can decide correctly.

This theorem shows why r.e. is weaker than decidable. An r.e. set gives a way to eventually confirm membership, but it may give no way to confirm nonmembership.

Domains of Partial Computable Functions

Recursively enumerable sets also arise as domains.

A partial computable function may be defined on some inputs and undefined on others:

\varphi(x)\downarrow

means that $\varphi(x)$ is defined, or equivalently, the computation halts.

The domain is:

$$ \operatorname{dom}(\varphi)

{x : \varphi(x)\downarrow} $$

Every such domain is r.e. We can enumerate the inputs on which the computation halts.

Conversely, every r.e. set is the domain of some partial computable function.

So r.e. sets are exactly the possible halting domains of partial computable functions.

Relation to Turing Degrees

R.e. sets are central in degree theory because they form a natural class of noncomputable sets.

The computable r.e. sets have degree:

\mathbf{0}

The halting set has degree:

\mathbf{0'}

Between them, there can be r.e. sets of intermediate Turing degree:

\mathbf{0} <_T \deg(A) <_T \mathbf{0'}

This is the content of Post’s problem, discussed next.

12.3 Recursively Enumerable Sets