Editing Computably enumerable set (section)

==Examples==
* Every [[computable 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 is ''not'' in the set – this is not required of computably enumerable sets.
* A [[recursively enumerable language]] is a computably enumerable subset of a [[formal 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 a [[Diophantine set]] (the converse is trivially true).
* The [[simple set]]s are computably enumerable but not computable.
* The [[creative set]]s are computably enumerable but not computable.
* Any [[productive set]] is '''not''' computably enumerable.
* Given a [[Gödel numbering]] <math>\phi</math> of the computable functions, the set <math>\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}</math> (where <math>\langle i,x \rangle</math> is the [[Cantor pairing function]] and <math>\phi_i(x)\downarrow</math> indicates <math>\phi_i(x)</math> is defined) is computably enumerable (cf. picture for a fixed ''x''). This set encodes the [[halting problem]] as it describes  the input parameters for which each [[Turing machine]] halts.
* Given a Gödel numbering <math>\phi</math> of the computable functions, the set <math>\{ \left \langle x, y, z \right \rangle \mid \phi_x(y) = z \}</math> is computably enumerable. This set encodes the problem of deciding a function value.
* Given a partial function ''f'' from the natural numbers into the natural numbers, ''f'' is a partial computable function if and only if the graph of ''f'',  that is, the set of all pairs <math>\langle x,f(x)\rangle</math> such that ''f''(''x'') is defined, is computably enumerable.