Revision as of 03:50, 9 May 2025 edit Nyngwang (talk \| contribs) 437 edits m chore: move the alias to the first line. ← Previous edit		Revision as of 04:00, 9 May 2025 edit undo Nyngwang (talk \| contribs) 437 edits m fix: use italic font for "decidable", since it might cause confusion that is explained in the second paragraph (at the time of this editing). Next edit →
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 '''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}} 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''.

Recursive language: Difference between revisions