Recursively enumerable set

From Exampleproblems

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 it is a member of S. Otherwise, there is no guarantee that the algorithm will halt.

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.

Contents 1 Definition 2 Remarks 3 Examples 4 Properties 5 See also

Definition

A countable set S is called recursively enumerable if there exists a partial computable function f such that S is the image of f:

img(f) = S

f is called enumerative function, because it associates to every element of S (the output), its rank (the input, a natural number) in the enumeration.

Alternatively a countable set S is called recursively enumerable if there exists a partial function computable function f such that

In other words if S is the domain of f:

dom(f) = S

A set S is called co-recursively enumerable or co-r.e. if the complement of S 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 S is called recursively enumerable if there exists a Turing machine that always halts when given an element of S as input, and that never halts when given an input that does not belong to S.

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.
• 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
• Given a gödel numbering φ of the computable functions then the set (with 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 φ of the computable functions then the set is recursively enumerable. This set encodes the problem of deciding a function value.

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

See also

• recursive set
• computable function
• Matiyasevich's theoremde:Rekursive Aufzählbarkeit

fr:Récursivement énumérable it:Insieme ricorsivamente enumerabile he:קבוצה ניתנת למנייה רקורסיבית