Recursive language: Difference between revisions

Revision as of 15:11, 3 November 2013

Revision as of 19:26, 26 February 2015

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 from the alphabet of the language as input (any string containing only characters in the language's alphabet), accepts onlyit thoseif thatbelongs are part ofto the language and rejects all otherit stringsotherwise. 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''.