Recursive language: Difference between revisions

Revision as of 03:21, 9 May 2025

Latest revision as of 08:12, 14 July 2025

(7 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Formal language in mathematics and computer science}}

{{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''.

Line 16 ⟶ 17:

# A recursive language is a [[formal language]] for which there exists a [[Turing machine]] that [[decider (Turing machine)|decides]] it.

ByOn the secondother definitionhand, anywe can show that a [[decision problem]] canis bedecidable shownby toexhibiting bea decidableTuring bymachine exhibitingrunning an [[algorithm]] for it that terminates on all inputs. An [[undecidable problem]] is a problem that is not decidable.

== Examples ==

Line 25 ⟶ 26:

is context-sensitive and therefore recursive.

Examples of decidable languages that are not context-sensitive are more difficult to describe. For one such example, some familiarity with [[mathematical logic]] is required: [[Presburger arithmetic]] is the first-order theory of the natural numbers with addition (but without multiplication). While the set of [[First-order_logic#Formulas|well-formed formulas]] in Presburger arithmetic is context-free, every deterministic Turing machine accepting the set of true statements in Presburger arithmetic has a worst-case runtime of at least <math>2^{2^{cnpn}}</math>, for some constant ''cp''>0.{{sfnp|Fischer|Rabin|1974}} Here, ''n'' denotes the length of the given formula. Since every context-sensitive language can be accepted by a [[linear bounded automaton]], and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most <math>cq^n</math> for some constant ''cq'' ,{{citation neededsfnp|date=March 2015Book|1974}}, the set of valid formulas in Presburger arithmetic is not context-sensitive. On a positive side, it is known that there is a deterministic Turing machine running in time at most triply exponential in ''n'' that decides the set of true formulas in Presburger arithmetic.{{sfnp|Oppen|1978}} Thus, this is an example of a language that is decidable but not context-sensitive.

== Closure properties ==

Line 45 ⟶ 46:

*[[Recursion]]

== ReferencesNotes ==

{{reflist}}

==References==

*{{cite journal

| last = Book | first = Ronald V. | author-link = Ronald V. Book

| doi = 10.1016/S0022-0000(74)80008-5

| journal = [[Journal of Computer and System Sciences]]

| mr = 366099

| pages = 213–229

| title = Comparing complexity classes

| volume = 9

| year = 1974}}

* {{cite journal | last = Chomsky | first = Noam | year = 1959 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167 | doi = 10.1016/S0019-9958(59)90362-6 | doi-access = }}

* {{cite journal | first1=Michael J. | last1=Fischer | authorlink1=Michael J. Fischer | first2=Michael O. | last2=Rabin | authorlink2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41 }}