Recursive language: Difference between revisions

Revision as of 12:16, 2 May 2013

Revision as of 09:36, 5 May 2013

Line 1:

{{About|a class of formal languages as they are studied in mathematics and theoretical computer science. Recursive languages are also called '''decidable'''|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]] which halts for every given input) which when given a finite sequence of symbols w from the alphabet of the language as input (any string containing only characters in the language's alphabet) accepts only those w which are part of the language and rejects all other strings. 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".