Recursively Enumerable Set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:
- There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.
Or, equivalently,
- There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.
The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase.
In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted .
Read more about Recursively Enumerable Set: Formal Definition, Equivalent Formulations, Examples, Properties, Remarks
Famous quotes containing the word set:
“What these perplexities of my uncle Toby were,—’tis impossible for you to guess;Mif you could,—I should blush ... as an author; inasmuch as I set no small store by myself upon this very account, that my reader has never yet been able to guess at any thing. And ... if I thought you was able to form the least ... conjecture to yourself, of what was to come in the next page,—I would tear it out of my book.”
—Laurence Sterne (1713–1768)