Content deleted Content added
No edit summary |
MrRaindrop75 (talk | contribs) m added a missing comma |
||
Line 4:
In [[mathematics]], [[logic]] and [[computer science]], a [[formal language]] (a [[set (mathematics)|set]] of finite sequences of [[symbol (formal)|symbol]]s taken from a fixed [[alphabet (computer science)|alphabet]]) is called '''recursive''' if it is a [[recursive set|recursive subset]] of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a [[total Turing machine]] (a [[Turing machine]] that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise. Recursive languages are also called '''decidable'''.
The concept of '''decidability''' may be extended to other [[models of computation]]. For example, one may speak of languages decidable on a [[non-deterministic Turing machine]]. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" is '''Turing-decidable language''', rather than simply ''decidable''.
The class of all recursive languages is often called '''[[R (complexity)|R]]''', although this name is also used for the class [[RP (complexity)|RP]].
| |||