Computably enumerable 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:

"Enumerable set" redirects here. For the set-theoretic concept, see Countable set.

Or, equivalently,

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 runs 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. In recursion theory, the lattice of c.e. sets under inclusion is denoted ${\mathcal {E}}$ .

Formal definition[edit]

A set S of natural numbers is called computably enumerable if there is a partial computable function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

Every 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.

computable set

A is a computably enumerable subset of a formal language.

recursively enumerable language

The set of all provable sentences in an effectively presented axiomatic system is a computably enumerable set.

states that every computably enumerable set is a Diophantine set (the converse is trivially true).

Matiyasevich's theorem

The are computably enumerable but not computable.

simple sets

The are computably enumerable but not computable.

creative sets

Any is not computably enumerable.

productive set

Given a $\phi$ of the computable functions, the set $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ (where $\langle i,x\rangle$ is the Cantor pairing function and $\phi _{i}(x)\downarrow$ indicates $\phi _{i}(x)$ 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.

Gödel numbering

Given a Gödel numbering $\phi$ of the computable functions, the set $\{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}$ 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 $\langle x,f(x)\rangle$ such that f(x) is defined, is computably enumerable.

Properties[edit]

If A and B are computably enumerable sets then A ∩ B, A ∪ B and A × B (with the ordered pair of natural numbers mapped to a single natural number with the Cantor pairing function) are computably enumerable sets. The preimage of a computably enumerable set under a partial computable function is a computably enumerable set.

A set $T$ is called co-computably-enumerable or co-c.e. if its complement $\mathbb {N} \setminus T$ is computably enumerable. Equivalently, a set is co-r.e. if and only if it is at level $\Pi _{1}^{0}$ of the arithmetical hierarchy. The complexity class of co-computably-enumerable sets is denoted co-RE.

A set A is computable if and only if both A and the complement of A are computably enumerable.

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

Remarks[edit]

According to the Church–Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is computably enumerable if and only if there is some algorithm which yields an enumeration of S. 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 the domain of a partial function, rather than the range 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, . ISBN 0-262-68052-1; ISBN 0-07-053522-1.

MIT Press

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. , Berlin, 1987. ISBN 3-540-15299-7.

Springer-Verlag

Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.