Content deleted Content added
m Reverted edits by Programinfo (talk) to last revision by OAbot: addition of unnecessary/inappropriate external links |
mNo edit summary |
||
Line 3:
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"
The class of all recursive languages is often called '''[[R (complexity)|R]]''', although this name is also used for the class [[RP (complexity)|RP]].
| |||