(
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:
- There exists a Turing machine M such that x∈X (x is a member of X) iff M halts when given x as input.
- There exists a Turing machine M' which outputs exactly the list of members of X, delimited in some suitable fashion.
- 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!)