Content deleted Content added
Pjboonstra (talk | contribs) m added missing word |
|||
Line 1:
{{About|a class of formal languages as they are studied in mathematics and theoretical computer science|computer languages that allow a function to call itself recursively |Recursion (computer science)}}
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 for "recursive language" used is '''Turing-decidable language''', rather than simply ''decidable''.
| |||