yawiki.org entry for Recursively enumerable set

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable or provable if:

There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of 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: s₁, s₂, s₃, ... . 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

    Recursively enumerable set
        Formal definition
        Equivalent formulations
        Examples
        Properties
        Remarks

top

Formal definition

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

top

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) =$

leftegin 0 &mbox x in S \ mbox &mbox x otin S end ight.

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.

top

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

phi

of the computable functions, the set

(where

langle i,x

angle is the Cantor pairing function and

phi_i(x)downarrow

indicates

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.

Given a Gödel numbering

phi

of the computable functions, the set

lbrace left langle x, y, z

ight angle mid phi_x(y)=z brace 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)

angle such that f(x) is defined, is recursively enumerable.

top

Properties

If 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

Sigma^0_1

of the arithmetical hierarchy.

A set

T

is called co-recursively enumerable or co-r.e. if its complement

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

top

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.

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Recursively enumerable set". link