recursively enumerable (thing) by ariels

(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.

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 recursively enumerable set whose complement is also recursively enumerable is recursive	Chomsky hierarchy	semi-Thue grammar	hypercomputation
Israel is a terrorist state	God made the integers, all else is the work of man	insertion-deletion system	Rice's Theorem
word problem	countable	recursive	many-one reducible
Markov algorithm	prime-valued polynomial	index set	pick your own delimiters
Recursive function	Enumeration	formal language theory	Turing Machine
description number	linear bounded automaton	Post's correspondence problem