Recursively enumerable language

related topics
{math, number, function}
{language, word, form}

In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages. The class of all recursively enumerable languages is called RE.



There exist three equivalent major definitions for the concept of a recursively enumerable language.

All regular, context-free, context-sensitive and recursive languages are recursively enumerable.

Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy.

Closure properties

Recursively enumerable languages are closed under the following operations. That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:

Note that recursively enumerable languages are not closed under set difference or complementation. The set difference L - P may or may not be recursively enumerable. If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.

See also

External links


  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Kozen, D.C. (1997), Automata and Computability, Springer.

Full article ▸

related documents
Removable singularity
Bucket sort
Symbolic logic
Directed set
Axiom of extensionality
Hilbert's basis theorem
Addition of natural numbers
Haar wavelet
Generating set of a group
Snake lemma
Finitely generated abelian group
Equality (mathematics)
Unique factorization domain
Wreath product
Cauchy's integral theorem
Atlas (topology)
Merge algorithm
Data integrity
Commutative diagram
Vector calculus
Nilpotent group
Symmetric tensor
Boundary (topology)
Interpreted language
Catalan's conjecture