Recursively enumerable set
From Wikipedia, the free encyclopedia
|
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:
Or, equivalently,
The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase. In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{E} .
Formal definitionA set S of natural numbers is called recursively enumerable if there is a partial recursive (i.e. computable) function whose domain (co-range) is exactly S, meaning that the function is defined if and only if its input is a member of S. The definition can be extended to an arbitrary countable set A by using Gödel numbers to represent elements of the set and declaring a subset of A to be recursively enumerable if the set of corresponding Gödel numbers is recursively enumerable. Equivalent formulationsThe following are all equivalent properties of a set S of natural numbers:
These last equivalences, while not as straight forward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative solution to solution to Hilbert'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 recursively enumerable sets). The number of bound variables in the above definition of the Diophantine set is the best known so far; it might be that a lower number can be used to define all diophantine sets. Examples
of the computable functions, the set Failed to parse (Missing texvc executable; please see math/README to configure.): \{\langle i,x \rangle \mid \phi_i(x) \downarrow \}
(where Failed to parse (Missing texvc executable; please see math/README to configure.): \langle i,x \rangle
is the Cantor pairing function and Failed to parse (Missing texvc executable; please see math/README to configure.): \phi_i(x)\downarrow
indicates Failed to parse (Missing texvc executable; please see math/README to configure.): \phi_i(x)
is defined) is recursively enumerable. This set encodes the halting problem as it describes the input parameters for which each Turing machine halts.
of the computable functions, the set Failed to parse (Missing texvc executable; please see math/README to configure.): \lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace is recursively enumerable. This set encodes the problem of deciding a function value.
such that f(x) is defined, is recursively enumerable. PropertiesIf A and B are recursively 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 recursively enumerable sets. The preimage of a recursively enumerable set under a partial recursive function is a recursively enumerable set. A set is recursively enumerable if and only if it is at level Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma^0_1 of the arithmetical hierarchy. A set Failed to parse (Missing texvc executable; please see math/README to configure.): T is called co-recursively enumerable or co-r.e. if its complement Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{N} \setminus T is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level Failed to parse (Missing texvc executable; please see math/README to configure.): \Pi^0_1 of the arithmetical hierarchy. A set A is recursive (synonym: computable) if and only if both A and the complement of A are recursively enumerable. A set is recursive if and only if it is either the range of an increasing total recursive function or finite. Some pairs of recursively enumerable sets are effectively separable and some are not. RemarksAccording to the Church-Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is recursively 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 recursively enumerable set as the domain of a partial function, rather than the range of a total recursive 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 recursively enumerable sets. References
es:Conjunto recursivamente enumerable fr:Récursivement énumérable it:Insieme ricorsivamente enumerabile he:קבוצה ניתנת למנייה רקורסיבית ja:帰納的可算集合 ru:Перечислимое множество |
