Recursively enumerable set

From Free net encyclopedia

Current revision

In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if

• There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if and only if the input is an element of S.

Or, equivalently,

• There is an algorithm that "generates" the members of S. That means that its output is simply a list of the members of S: s₁, s₂, s₃, ... If necessary it runs forever.

The complexity class containing all recursively enumerable sets is RE.

Common-programming-sense should suggest how to convert either of these algorithms to the other, thus showing the equivalence of the existence of either with the existence of the other. The first condition suggests why the term semi-decidable is sometimes used; the second suggests why computably enumerable is used.

Definition

A countable set <math>S</math> is called recursively enumerable if there exists a partial computable function <math>f : \mathbb{N} \to S</math> such that <math>S</math> is the range of <math>f</math> :

<math>\mathrm{rng}(f) = S</math>

<math>f</math> is called an enumerative function because it associates a rank in the enumeration to every element of <math>S</math>.

Equivalent formulations

The following are equivalent:

• The set <math>S</math> is recursively enumerable, i.e. the range of a partial recursive function.
• The set <math>S</math> is either empty or the range of a total recursive function.
• The set <math>S</math> is either empty or the range of a primative recursive function.
• The set <math>S</math> is the domain of a partial recursive function.
• Or, there exists a partial computable function <math>f</math> such that:

<math>f(x) =

\left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \mbox{undef/does not halt}\ &\mbox{if}\ x \notin S \end{matrix}\right. </math>

In other words if <math>S</math> is the domain of <math>f</math> :

<math>\mathrm{dom}(f) = S</math>

(Note that this is one of two possible senses of the domain of a partial function, but the one preferred in recursion theory. See the discussion at partial function.)

A set <math>S</math> is called co-recursively enumerable or co-r.e. if the complement, <math>\mathbb{N} - S</math>, is recursively enumerable.

Remarks

Since the Church-Turing thesis states that computable functions are defined equivalently by Turing machines and other models of computation, we can state the definition as

A countable set <math>S</math> is called recursively enumerable if there exists a Turing machine that always halts when given an element of <math>S</math> as input, and that never halts when given an input that does not belong to <math>S</math>.

This is also a very common definition of recursively enumerable set.

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 recursive enumerable set in the set of all possible words over the alphabet of the language.
• The set of all provable sentences in an axiomatic system is a recursively enumerable set.
• Matiyasevich's theorem states that every Diophantine set is recursively enumerable.
• simple sets are recursively enumerable but not recursive.
• creative sets are recursively enumerable but not recursive.
• a productive set is not recursively enumerable.
• Given a Gödel numbering <math>\phi</math> of the computable functions then the set <math>\{\langle i,x \rangle | \phi_i(x) \quad \mathrm{exists}\}</math> (with <math>\langle i,x \rangle</math> the Cantor pairing function) 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 <math>\phi</math> of the computable functions then the set <math>\lbrace \left \langle x, y, z \right \rangle | \phi_x(y)=z \rbrace</math> is recursively enumerable. This set encodes the problem of deciding a function value.
• Given a function f, the graph of f, i.e. {(x,f(x))|x in the domain of f}, is recursively enumerable iff f is partial recursive.

Properties

If A and B are recursively enumerable sets then A ∩ B, A ∪ B and A × B are recursively enumerable sets. A set A is a recursive set if and only if both A and the complement of A are recursively enumerable sets. The preimage of a recursively enumerable set under a computable function is a recursively enumerable set.de:Rekursive Aufzählbarkeit fr:Récursivement énumérable he:קבוצה ניתנת למנייה רקורסיבית it:Insieme ricorsivamente enumerabile zh:递归可枚举集合