Recursively enumerable language

Summary

A recursively enumerable language is a formal language whose members are exactly the inputs on which some Turing machine halts and accepts. Such languages are also called Turing-recognizable or semi-decidable. On inputs outside the language, the machine may reject or run forever. Equivalently, some machine lists the members of the language one after another. These languages are the top level of the Chomsky hierarchy, generated by unrestricted grammars, and they correspond to the computably enumerable sets of natural numbers.