Recursive language: Difference between revisions

Revision as of 00:48, 20 November 2022

Revision as of 22:55, 18 June 2023

Line 2:

{{Format footnotes|reason=Parenthetical referencing has been [[WP:PARREF|deprecated]]; convert to [[Help:Shortened footnotes|shortened footnotes]].|date=June 2022}}

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, always halts and accepts it if it belongs to the language and halts and rejects it otherwise. In [[Theoretical computer science]], such always-halting Turing machines are called [[total Turing machine]]s or '''algorithms''' (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''.