Editing Enumeration (section)

== Computability and complexity theory ==

In [[computability theory]] one often considers countable enumerations with the added requirement that the mapping from <math>\mathbb{N}</math> (set of all natural numbers) to the enumerated set must be [[computable function|computable]]. The set being enumerated is then called [[recursively enumerable]] (or computably enumerable in more contemporary language), referring to the use of [[recursion theory]] in formalizations of what it means for the map to be computable.

In this sense, a subset of the natural numbers is [[computably enumerable]] if it is the range of a computable function. In this context, enumerable may be used to mean computably enumerable. However, these definitions characterize distinct classes since there are uncountably many subsets of the natural numbers that can be enumerated by an arbitrary function with domain &omega; and only countably many computable functions. A specific example of a set with an enumeration but not a computable enumeration is the complement of the [[halting problem|halting set]].

Furthermore, this characterization illustrates a place where the ordering of the listing is important. There exists a computable enumeration of the halting set, but '''not''' one that lists the elements in an increasing ordering. If there were one, then the halting set would be [[Decidable language|decidable]], which is provably false. In general, being recursively enumerable is a weaker condition than being a [[decidable set]].

The notion of enumeration has also been studied from the point of view of [[computational complexity theory]] for various tasks in the context of [[enumeration algorithm]]s.