 | This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(December 2024) (Learn how and when to remove this message) |
Inmathematics,logic andcomputer science, aformal language is calledrecursively enumerable (alsorecognizable,partially decidable,semidecidable,Turing-acceptable orTuring-recognizable) if it is arecursively enumerable subset in theset of all possible words over thealphabet of the language, i.e., if there exists aTuring machine which will enumerate all valid strings of the language.
Recursively enumerable languages are known astype-0 languages in theChomsky hierarchy of formal languages. Allregular,context-free,context-sensitive andrecursive languages are recursively enumerable.
The class of all recursively enumerable languages is calledRE.
There are three equivalent definitions of a recursively enumerable language:
Allregular,context-free,context-sensitive andrecursive languages are recursively enumerable.
Post's theorem shows thatRE, together with itscomplementco-RE, correspond to the first level of thearithmetical hierarchy.
The set ofhalting 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) areclosed under the following operations. That is, ifL andP are two recursively enumerable languages, then the following languages are recursively enumerable as well:
Recursively enumerable languages are not closed underset difference or complementation. The set difference is recursively enumerable if is recursive. If is recursively enumerable, then the complement of is recursively enumerableif and only if is also recursive.