Recursively enumerable set

In computability theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable or provable if:

There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S.

Or, equivalently,

There is an algorithm that "enumerates" the members of S. That means that its output is simply a list of the members of S: s₁, s₂, s₃, ... . If necessary, this algorithm may run forever.

The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used.

In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted $\mathcal{E}$ .

Formal Definition

A countable set S is called recursively enumerable if there is a computable function whose domain is exactly S, meaning that the function is defined (halts) if and only if its input is a member of S.

Equivalent formulations

The following are equivalent characterizations of a set S, and each is equivalent to S being recursively enumerable. The first two emphasize the semidecidability of S, while the last two emphasize the enumerability of S.

The set S is the domain of a partial computable function.
There is a partial computable function f such that:

f(x) =

\left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \mbox{undefined/does not halt}\ &\mbox{if}\ x \notin S \end{matrix}\right.

The set S is the range of a total computable function. If S is infinite, the function can be assumed to be injective.
The set S is the range of a primitive recursive function (which must a priori be total). If S is infinite, the function can be assumed to be injective.

Examples

Every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive.
A recursively enumerable language is a recursively enumerable subset of a formal language.
The set of all provable sentences in an effectively presented axiomatic system is a recursively enumerable set.
Matiyasevich's theorem states that every recursively enumerable set is a Diophantine set (the converse is trivially true).
The simple sets are recursively enumerable but not recursive.
The creative sets are recursively enumerable but not recursive.
Any productive set is not recursively enumerable.
Given a Gödel numbering $\phi$ of the computable functions, the set $\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}$ (where $\langle i,x \rangle$ is the Cantor pairing function and $\phi_i(x)\downarrow$ indicates $\phi_i(x)$ is defined) is recursively enumerable. This set encodes the halting problem as it describes the input parameters for which each Turing machine halts.
Given a Gödel numbering $\phi$ of the computable functions, the set $\lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace$ is recursively enumerable. This set encodes the problem of deciding a function value.
Given a (partial) function f from the natural numbers into the natural numbers, the graph of f, that is, the set of all pairs (x,f(x)) such that f(x) is defined, is recursively enumerable if and only if f is a partial computable function.

Properties

If A and B are recursively enumerable sets then A ∩ B, A ∪ B and A × B are recursively enumerable sets. A set A is recursive (synonym: computable) if and only if both A and the complement of A are recursively enumerable. The preimage of a recursively enumerable set under a computable function is a recursively enumerable set.

A set is recursively enumerable if and only if it is at level $\Sigma^0_1$ of the arithmetical hierarchy.

A set $T$ is called co-recursively enumerable or co-r.e. if its complement $\mathbb{N} \setminus T$ is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level $\Pi^0_1$ of the arithmetical hierarchy.

A recursively enumerable set S is recursive if and only if there is a computable enumeration of S that is nondecreasing.

Remarks

According to the Church-Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus the a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church-Turing thesis is an informal conjecture rather than a formal axiom.

The definition of a recursively enumerable set as the domain of a partial function, rather than the range of a total recursive function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for recursively enumerable sets.

Recursion theory | Theory of computation

Gourt Home::Gourt :: Recursively enumerable set

Formal Definition

Equivalent formulations

Examples

Properties

Remarks