Computably 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 words in an alphabet, 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,