Recursively enumerable set

Recursively enumerable set

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:

  • There is an algorithm such that the set of input numbers for which the algorithm halts is exactly the set of numbers in S.

Or, equivalently,

  • There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.

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 \mathcal{E}.

Contents

Formal definition

A set S of natural numbers is called recursively enumerable if there is a partial recursive function (synonymously, 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.

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 formulations

The following are all equivalent properties of a set S of natural numbers:

Semidecidability:
  • The set S is recursively enumerable. That is, S is the domain (co-range) of a partial recursive function.
  • There is a partial recursive function f such that:
f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \\
\mbox{undefined/does not halt}\ &\mbox{if}\ x \notin S
\end{matrix}\right.
Enumerability:
  • The set S is the range of a partial recursive function.
  • The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.
  • The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.
Diophantine:
  • There is a polynomial p with integer coefficients and variables x, a, b, c, d, e, f, g, h, i ranging over the natural numbers such that
x \in S \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0).
  • There is a polynomial from the integers to the integers such that the set S contains exactly the non-negative numbers in its range.

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

The Diophantine characterizations of a recursively enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative 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

  • Every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive.
  • A recursively enumerable language is a recursively enumerable subset of a formal language.
  • The set of all provable sentences in an effectively presented axiomatic system is a recursively enumerable set.
  • Matiyasevich's theorem states that every recursively enumerable set is a Diophantine set (the converse is trivially true).
  • The simple sets are recursively enumerable but not recursive.
  • The creative sets are recursively enumerable but not recursive.
  • Any productive set is not recursively enumerable.
  • Given a Gödel numbering ϕ 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 ϕ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.
  • Given a Gödel numbering ϕ of the computable functions, the set \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.
  • Given a partial function f from the natural numbers into the natural numbers, f is a partial recursive 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 recursively enumerable.

Properties

If A and B are recursively enumerable sets then AB, AB 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 \Sigma^0_1 of the arithmetical hierarchy.

A set T is called co-recursively enumerable or co-r.e. if its complement \mathbb{N} \setminus T is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level \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.

Remarks

According 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

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

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Recursively enumerable language — In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing acceptable. It is known as a type 0 language in the Chomsky hierarchy of formal… …   Wikipedia

  • co-recursively enumerable — adjective Describing a set for which there exists a deterministic algorithm that will list all items not in that set. Any recursively enumerable set which is also co recursively enumerable is a decidable set …   Wiktionary

  • recursively enumerable — adjective Of a set, such that there exists a deterministic algorithm which will list all the items in the set and no others …   Wiktionary

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Simple set — In recursion theory a simple set is an example of a set which is recursively enumerable but not recursive. Definition A subset S of the natural numbers N is called simple if it satisfies the following properties # N S is infinite and contains no… …   Wikipedia

  • Recursive set — In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A more… …   Wikipedia

  • Countable set — Countable redirects here. For the linguistic concept, see Count noun. Not to be confused with (recursively) enumerable sets. In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of… …   Wikipedia

  • Empty set — ∅ redirects here. For similar looking symbols, see Ø (disambiguation). The empty set is the set containing no elements. In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality… …   Wikipedia

  • Class (set theory) — In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) which can be unambiguously defined by a property that all its members share. The precise definition of class… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”