In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turingacceptable) 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 type0 languages in the Chomsky hierarchy of formal languages. All regular, contextfree, contextsensitive and recursive languages are recursively enumerable.
The class of all recursively enumerable languages is called RE.
Contents

Definitions 1

Example 2

Closure properties 3

References 4

External links 5
Definitions
There exist three equivalent major definitions for the concept of a recursively enumerable language.

A recursively enumerable language is a recursively enumerable subset in the set of all possible words over the alphabet of the language.

A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language. Note that if the language is infinite, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number n is "already" produced for a number which is less than n. If it already is produced, use the output for input n+1 instead (recursively), but again, test whether it is "new".

A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases.
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.
Example
The Halting problem is recursively enumerable but not recursive. Indeed one can run the Turing Machine and accept if the machine halts, hence it is r.e. On the other hand the problem is undecidable.
Some other r.e. languages that are not recursive:
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.
References

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

Kozen, D.C. (1997), Automata and Computability, Springer.
External links




Each category of languages, except those marked by a ^{*}, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.


This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.