Recursively Enumerable

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

S

is called recursively enumerable if there exists a of

f

:

:

\mathrm{rng}(f) = S

f

is called an enumerative function because it associates a '''rank''' in the enumeration to every element of

S

.

EQUIVALENT FORMULATIONS

The following are equivalent:

The set $S$ is recursively enumerable, i.e. the range of a partial recursive function.

The set $S$ is either empty or the range of a total recursive function.

The set $S$ is either empty or the range of a primative recursive function.

The set $S$ is the domain of a partial recursive function.

Or, there exists a partial computable function $f$ such that:

f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \
\mbox{undef/does not halt}\ &\mbox{if}\ x 
otin S
\end{matrix}
ight.

In other words if

S

is the Domain of

f

:
:

\mathrm{dom}(f) = S

(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

S

is called co-recursively enumerable or '''co-r.e.''' if the Complement ,

\mathbb{N} - S

, is recursively enumerable.

REMARKS

Since the Church-Turing Thesis states that computable functions are defined equivalently by Turing Machine s 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 .

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 Set s are recursively enumerable but not recursive.

Creative Set s 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>\lbrace \left \langle X, Y, Z Ight Angle \phi X(y)

z brace</math> is recursively enumerable This set encodes the problem of deciding a function value

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT RECURSIVELY ENUMERABLE SET

	recursion theory

	theory of computation

Information About

Recursively Enumerable