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.
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.
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- Kozen, D.C. (1997), Automata and Computability, Springer.
Full article ▸