Recursive language: Difference between revisions

Revision as of 03:21, 9 May 2025

Revision as of 03:50, 9 May 2025

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 '''recursive''' or language'''decidable''' language is a [[recursive set|recursive subset]] of the [[Kleene closure]] of an [[Alphabet (formal languages)|alphabet]]. Equivalently, a [[formal language]] is '''recursive''' if there exists a Turing machine that [[Decider (Turing machine)|decides]] the formal language.{{sfnp|Sipser|2012}} In [[theoretical computer science]], such always-halting Turing machines are called [[total Turing machine]]s or '''algorithms'''.{{sfnp|Sipser|1997}} 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''.