Recursively enumerable set

(Redirected from Recursively enumerable)

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.

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

Definition

A subset S of the natural numbers is called recursively enumerable if there exists a computable function

$f:\subseteq \mathbb{N} \to \mathbb{N}$

with

$f(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \mbox{does not halt} &\mbox{if}\ x \notin S \end{matrix}\right.$

In other words the set S is recursively enumerable iff there exists a computable function f with domain(f) = S.

Notes

If A and B are recursively enumerable sets then 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.

Examples

every recursive set is recursively enumerable.
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 sets is recursively enumerable