This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (January 2013) (Learn how and when to remove this template message)
In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable.
The class of all recursively enumerable languages is called RE.
There are three equivalent definitions of a recursively enumerable language:
The set of halting turing machines is recursively enumerable but not recursive. Indeed, one can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable. On the other hand, the problem is undecidable.
Some other recursively enumerable languages that are not recursive include:
Recursively enumerable languages (REL) 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:
Recursively enumerable languages are not closed under set difference or complementation. The set difference - is recursively enumerable if is recursive. If is recursively enumerable, then the complement of is recursively enumerable if and only if is also recursive.