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.

*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.