Karl Jones: Created page with "In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semi..."

2016-09-11T19:26:54Z

Created page with "In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semi..."

New page

In [[computability theory]], traditionally called recursion theory, a set S of [[Natural number|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 [[Enumeration|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 (complexity)|RE]].

In recursion theory (also known as [[Computability theory]]), the [[Lattice (order)|lattice]] of r.e. sets under inclusion is denoted E.

== See also ==

* [[Algorithm]]
* [[Computability theory]]
* [[Enumeration]]
* [[Lattice (order)]]
* [[Natural number]]
* [[RE (complexity)]]

== External links ==

* [https://en.wikipedia.org/wiki/Recursively_enumerable_set Recursively enumerable set] @ Wikipedia.org

[[Category:Computer science]]
[[Category:Computing]]
[[Category:Mathematics]]

Recursively enumerable set - Revision history

Karl Jones: Created page with "In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semi..."