Incomputability theory, a setS ofnatural numbers is calledcomputably enumerable (c.e.),recursively enumerable (r.e.),semidecidable,partially decidable,listable,provable orTuring-recognizable if:

• There is analgorithm such that the set of input numbers for which the algorithm halts is exactlyS.

Or, equivalently,

• There is analgorithm that enumerates the members ofS. That means that its output is a list of all the members ofS:s₁,s₂,s₃, ... . IfS 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 termsemidecidable is sometimes used. More precisely, if a number is in the set, one candecide 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 acomputable set. The second condition suggests whycomputably enumerable is used. The abbreviationsc.e. andr.e. are often used, even in print, instead of the full phrase.

Incomputational complexity theory, thecomplexity class containing all computably enumerable sets isRE. In recursion theory, thelattice of c.e. sets under inclusion is denoted${\displaystyle \mathcal{E}}$.

A setS of natural numbers is calledcomputably enumerable if there is apartial computable function whosedomain is exactlyS, meaning that the function is defined if and only if its input is a member ofS.

The following are all equivalent properties of a setS of natural numbers:

Semidecidability:

• The setS is computably enumerable. That is,S is the domain (co-range) of a partial computable function.
• The setS is${\displaystyle {\mathrm{\Sigma }}_1^0}$ (referring to thearithmetical hierarchy).^[1]
• There is a partial computable functionf such that:

Enumerability:

• The setS is the range of a partial computable function.
• The setS is the range of a total computable function, or empty. IfS is infinite, the function can be chosen to beinjective.
• The setS is the range of aprimitive recursive function or empty. Even ifS is infinite, repetition of values may be necessary in this case.

Diophantine:

• There is a polynomialp with integer coefficients and variablesx,a,b,c,d,e,f,g,h,i ranging over the natural numbers such that$${\displaystyle x\in S\iff \mathrm{\exists }a,b,c,d,e,f,g,h,i(p(x,a,b,c,d,e,f,g,h,i)=0).}$$ (The number of bound variables in this definition is the best known so far; it might be that a lower number can be used to define all Diophantine sets.)
• There is a polynomial from the integers to the integers such that the setS contains exactly the non-negative numbers in its range.

The equivalence of semidecidability and enumerability can be obtained by the technique ofdovetailing.

The Diophantine characterizations of a computably enumerable set, while not as straightforward or intuitive as the first definitions, were found byYuri Matiyasevich as part of the negative solution toHilbert's Tenth Problem. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of computably enumerable sets).

• Everycomputable set is computably enumerable, but it is not true that every computably enumerable set is computable. For computable sets, the algorithm must also say if an input isnot in the set – this is not required of computably enumerable sets.
• Arecursively enumerable language is a computably enumerable subset of aformal language.
• The set of all provable sentences in an effectively presented axiomatic system is a computably enumerable set.
• Matiyasevich's theorem states that every computably enumerable set is aDiophantine set (the converse is trivially true).
• Thesimple sets are computably enumerable but not computable.
• Thecreative sets are computably enumerable but not computable.
• Anyproductive set isnot computably enumerable.
• Given aGödel numbering${\displaystyle \varphi }$ of the computable functions, the set${\displaystyle \{⟨i,x⟩\mid {\varphi }_i(x)\downarrow \}}$ (where${\displaystyle ⟨i,x⟩}$ is theCantor pairing function and${\displaystyle {\varphi }_i(x)\downarrow }$ indicates${\displaystyle {\varphi }_i(x)}$ is defined) is computably enumerable (cf. picture for a fixedx). This set encodes thehalting problem as it describes the input parameters for which eachTuring machine halts.
• Given a Gödel numbering${\displaystyle \varphi }$ of the computable functions, the set${\displaystyle \{⟨x,y,z⟩\mid {\varphi }_x(y)=z\}}$ is computably enumerable. This set encodes the problem of deciding a function value.
• Given a partial functionf from the natural numbers into the natural numbers,f is a partial computable function if and only if the graph off, that is, the set of all pairs${\displaystyle ⟨x,f(x)⟩}$ such thatf(x) is defined, is computably enumerable.

IfA andB are computably enumerable sets thenA ∩B,A ∪B andA ×B (with the ordered pair of natural numbers mapped to a single natural number with theCantor pairing function) are computably enumerable sets. Thepreimage of a computably enumerable set under a partial computable function is a computably enumerable set.

A set${\displaystyle T}$ is calledco-computably-enumerable orco-c.e. if itscomplement${\displaystyle \mathbb{N}\setminus T}$ is computably enumerable. Equivalently, a set is co-r.e. if and only if it is at level${\displaystyle {\mathrm{\Pi }}_1^0}$ of the arithmetical hierarchy. The complexity class of co-computably-enumerable sets is denoted co-RE.

A setA iscomputable if and only if bothA and the complement ofA are computably enumerable.

Some pairs of computably enumerable sets areeffectively separable and some are not.

According to theChurch–Turing thesis, any effectively calculable function is calculable by aTuring machine, and thus a setS is computably enumerable if and only if there is somealgorithm which yields an enumeration ofS. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom.

The definition of a computably enumerable set as thedomain of a partial function, rather than therange of a total computable function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such asα-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for computably enumerable sets.

• RE (complexity)
• Recursively enumerable language
• Arithmetical hierarchy

• Rogers, H.The Theory of Recursive Functions and Effective Computability,MIT Press.ISBN 0-262-68052-1;ISBN 0-07-053522-1.
• Soare, R. Recursively enumerable sets and degrees.Perspectives in Mathematical Logic.Springer-Verlag, Berlin, 1987.ISBN 3-540-15299-7.
• Soare, Robert I. Recursively enumerable sets and degrees.Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.

• Computability theory
• Theory of computation

• Articles with short description
• Short description is different from Wikidata