In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turingacceptable. It is known as a type0 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, contextfree, contextsensitive and recursive languages are recursively enumerable.
Post's theorem shows that RE, together with its complement coRE, 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 ▸
