Recursive language: Difference between revisions

Revision as of 08:48, 8 May 2025

Revision as of 02:17, 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 language''' is a [[formal language]] that is a [[recursive set|recursive subset]] of the [[Kleene closure]] of itsan [[Alphabet (formal languages)|alphabet]]. Equivalently, a [[formal language]] is '''recursive''' if there exists a Turing machine that, for[[Decider every(Turing finitemachine)|decides]] inputthe string, always halts and either accepts or rejects it based on whether it belongs to theformal 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''.

Line 51:

*{{cite journal | last1 = Oppen | first1 = Derek C. | year = 1978 | title = A 2^{2^{2^''pn''}} Upper Bound on the Complexity of Presburger Arithmetic | journal = J. Comput. Syst. Sci. | volume = 16 | issue = 3| pages = 323–332 | doi = 10.1016/0022-0000(78)90021-1 | doi-access = free }}

* {{Cite book |last=Sipser | first = Michael | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = [https://archive.org/details/introductiontoth00sips/page/151 151–170] | isbn = 978-0-534-94728-6 | author-link = Michael Sipser | chapter-url-access = registration | chapter-url = https://archive.org/details/introductiontoth00sips/page/151 }}

* {{Cite book | last=Sipser | first=Michael | year=2012 | title=Introduction to the Theory of Computation | publisher=Cengage Learning | chapter=The Church-Turing Thesis | pages=170 | isbn=978-1-133-18779-0 | author-link=Michael Sipser}}

{{Formal languages and grammars}}