Editing Computably enumerable set (section)

{{Short description|Mathematical logic concept}}
{{Redirect|Enumerable set|the set-theoretic concept|Countable set}}
In [[computability theory]], a set ''S'' of [[natural numbers]] is called '''computably enumerable (c.e.)''', '''recursively enumerable (r.e.)''', '''semidecidable''', '''partially decidable''', '''listable''', '''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 [[enumeration algorithm|algorithm that enumerates]] the members of ''S''.  That means that its output is a list of all the members of ''S'':  ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ... .  If ''S'' is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time. Note that these elements do not have to be listed in a particular way, say from smallest to largest.

The first condition suggests why the term ''semidecidable'' is sometimes used. More precisely, if a number is in the set, one can ''decide'' this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no information is returned. A set that is "completely decidable" is a [[computable set]].  The second condition suggests why ''computably enumerable'' is used. The abbreviations '''c.e.''' and '''r.e.''' are often used, even in print, instead of the full phrase.

In [[computational complexity theory]], the [[complexity class]] containing all computably enumerable sets is [[RE (complexity)|RE]]. In recursion theory, the [[Lattice (order)|lattice]] of c.e. sets under inclusion is denoted <math>\mathcal{E}</math>.