# Recursively enumerable set

In the theory of computability (often less suggestively called

recursion theory), a set

*S* of natural numbers or tuples of natural numbers, or of literal strings, is

**recursively enumerable** or

**computably enumerable** or

**semi-decidable** if it satisfies either (and therefore both) of the following equivalent conditions.

- There is an algorithm that, when given a natural number
*n* (or tuple of natural numbers, or word, as the case may be) eventually halts if *n* is a member of *S* and otherwise runs forever.

- There is an algorithm that "generates" the members of
*S*. That means that its output is simply a list of the members of *S*: *s*_{1}, *s*_{2}, *s*_{3}, ... If necessary it runs forever.

Common-programming-sense should suggest how to convert either of these algorithms to the other, thus showing the equivalence of the existence of either with the existence of the other. The first condition suggests why the term

*semi-decidable* is sometimes used; the second suggests why

*computably enumerable* is used. The word

*recursive* is in this context taken to be synonymous with

*computable*; see

recursive function.

It may be fairly readily seen that any set *S* is recursive (i.e., decidable) if and only if both *S* and the complement of *S* are recursively enumerable.