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.

Contents

Definitions

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

References

  • 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
Bogosort
Concatenation
Atlas (topology)
Merge algorithm
Data integrity
Sharp-P-complete
Commutative diagram
Vector calculus
BQP
Sather
Nilpotent group
Symmetric tensor
Boundary (topology)
Interpreted language
Catalan's conjecture