recursively enumerable

(recursive function theory, mathematical logic, some computer science):
The following conditions are all equivalent; a set X (a subset of possible inputs to a Turing machine) is called recursively enumerable (commonly shortened to "r.e.") if it satisfies any (and therefore all) of them:

1. There exists a Turing machine M such that x∈X (x is a member of X) iff M halts when given x as input.
2. There exists a Turing machine M' which outputs exactly the list of members of X, delimited in some suitable fashion.
3. X is the image of a Turing machine M'' (that is, X is exactly the set of possible outputs of M'').

Other equivalent formulations also exist; the first above is usually given as the definition.

Recursively enumerable sets are sometimes called semidecidable.

There's an analogy between the classes "recursively enumerable" and "NP"; it's a special case of something that occurs in other places in mathematical logic.

Examples

A recursively enumerable set whose complement is also recursively enumerable is recursive; I won't bother with giving all recursive sets as examples. Recursively enumerable sets with non-recursively enumerable complements include these:

The set of all Turing machines that halt on null input.

(Just simulate the run of the Turing machine on null input!)

The set of all provable theorems of arithmetic.

(Just iterate over all valid proofs and print the last line of each!)

A stronger version of countable (unless you only believe in constructive mathematics).

A set is countable if it has a numbering (a one-to-one correspondence with the natural numbers).

A set is recursively enumerable if there exist instructions for numbering them.

Huh, wait - what's the difference? An example:

1. Consider some notational convention for Turing machines that uses only ASCII symbols and supports at least two states and at least two tape symbols, and supports
   • mechanical validation: instructions to verify, given any sequence of ASCII symbols, whether it denotes a Turing machine;
   • normalization: instructions to rewrite any denotation of a Turing machine into a unique form (e.g. such that any two denotations of the same machine produce the same result).
   Any textbook notation will do, as long as you specify exactly how to denote it with ASCII (even whitespace matters, if you're going to allow that). You can probably normalize by removing all whitespace and putting the elements of all sets in lexicographical order.
2. There are 128 (or 256, whatever) ASCII characters, pre-numbered for your convenience; this gives us a way to effectively number all ASCII strings in lexicographical order, which proves that they are recursively enumerable.
3. The set of normalized notations of Turing machines according to your convention is also recursively enumerable: for instance, generate all ASCII strings in lexicographical order, but number only those that denote Turing machines and normalize to themselves. This numbering effectively numbers the Turing machines themselves (over your chosen alphabet) because there is a one-to-one correspondence between the machines and their normalized notations.
4. Now consider the numbering that numbers, in the same order, the normalized notations of all Turing machines that do not halt on the empty input. It defines a one-to-one correspondence between the natural numbers and this set of notations, and because they are normalized, with the set of such machines itself, proving that these sets are both countable - while (as ariels correctly writes) the latter set is not recursively enumerable. We've found a numbering that is well-defined (according to standard mathematics) but cannot be effectively executed, nor can any other numbering of the same set.

Don't worry: Kronecker and Brouwer are dead. Do feel a little guilty.