Editing Recursively enumerable language (section)

{{short description|Formal language}}
{{inline citations|date=December 2024}}
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 set|recursively enumerable subset]] in the [[set (mathematics)|set]] of all possible words over the [[alphabet (computer science)|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 language|regular]], [[context-free grammar|context-free]], [[context-sensitive language|context-sensitive]] and [[recursive language|recursive]] languages are recursively enumerable.

The class of all recursively enumerable languages is called '''[[RE (complexity)|RE]]'''.