Editing Recursively enumerable language (section)

==Definitions==
There are three equivalent definitions of a recursively enumerable language:

# A recursively enumerable language 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 [[formal language|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 [[Infinity|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 [[literal string|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 language]]s, which require that the Turing machine halts in all cases.

All [[regular language|regular]], [[context-free language|context-free]], [[context-sensitive language|context-sensitive]] and [[recursive language|recursive]] languages are recursively enumerable.

[[Post's theorem]] shows that '''[[RE (complexity)|RE]]''', together with its [[complement (complexity)|complement]] [[co-RE]], correspond to the first level of the [[arithmetical hierarchy]].