There is an algorithm such that the set of input numbers for which the algorithm halts is exactly 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: s1, s2, s3,.... 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. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase. 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.
Formal definition
A set S of natural numbers is called recursively enumerable if there is a partial recursive function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.
Equivalent formulations
The following are all equivalent properties of a set S of natural numbers: The equivalence of semidecidability and enumerability can be obtained by the technique of dovetailing. The Diophantine characterizations of a recursively enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative solution to Hilbert's Tenth Problem. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets.
Examples
Every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive. For recursive sets, the algorithm must also say if an input is not in the set – this is not required of recursively enumerable sets.
Given a Gödel numbering of the computable functions, the set is recursively enumerable. This set encodes the problem of deciding a function value.
Given a partial functionf from the natural numbers into the natural numbers, f is a partial recursive function if and only if the graph of f, that is, the set of all pairs such that f is defined, is recursively enumerable.
Properties
If A and B are recursively enumerable sets then A ∩ B, A ∪ B and A × B are recursively enumerable sets. The preimage of a recursively enumerable set under a partial recursive function is a recursively enumerable set. A set is recursively enumerable if and only if it is at level of the arithmetical hierarchy. A set is called co-recursively enumerable or co-r.e. if its complement is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level of the arithmetical hierarchy. The complexity class of co-recursively enumerable sets is denoted co-RE. A set A is recursive if and only if both A and the complement of A are recursively enumerable. A set is recursive if and only if it is either the range of an increasing total recursive function or finite. Some pairs of recursively enumerable sets are effectively separable and some are not.
Remarks
According to the Church–Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus 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 informalconjecture 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.
