Recursively enumerable language
a formal language that can be output (enumerated) by an algorithm (mathematical logic, computability theory)
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. These are generated by unrestricted grammars.
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.
Definitions
There are three equivalent definitions 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.
The public source identifies “Recursively enumerable language” as a formal language that can be output (enumerated) by an algorithm (mathematical logic, computability theory). This brief keeps that definition visible, then builds a research path around Recursively, enumerable and language.
Why this record matters
A short description can identify a subject without explaining its stakes. For “Recursively enumerable language”, the useful work is to connect “a formal language that can be output (enumerated) by an algorithm (mathematical logic, computability theory)” to the records capable of establishing context and consequence.
Vocabulary and entity names are the principal evidence signals here, because they determine the precision of every later search. The source revision retrieved here is dated Apr 13, 2026. The linked authority identifier is Q1073063. None of the 0 selected statements returned an explicit reference.
The absence of detail may reflect summary conventions rather than a lack of surviving documentation. The source lead contains qualifying language; that uncertainty should survive quotation, summary and reuse. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Recursively enumerable language”, its source revision and the description used here.
- Expand the search: follow Recursively enumerable language primary sources, Recursively enumerable language archive and Recursively research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Recursively enumerable language”?
- Which cited source is closest to the event, object or claim?
- Which institution is responsible for the underlying evidence?
Search terms from this dossier
This entry incorporates text from “Recursively enumerable language” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.