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: s1, s2, s3, ... If necessary it runs forever.
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.