Main Page | See live article | Alphabetical index

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.

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.