Recursive language

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, logic and computer science, a recursive (or decidable) language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the formal language. In theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms. 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. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy. All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

In mathematics, logic and computer science, a recursive (or decidable) language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the formal language. In theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms. 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. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy. All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive. As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set L={abc, , , ...}; more formally, the set L=\{\,w \in \{a,b,c\}^* \mid w=a^nb^nc^n \mbox{ for some } n\ge 1 \,\} 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 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 2^{2^{pn}} , for some constant p>0. 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 q^n for some constant q, 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. Thus, this is an example of a language that is decidable but not context-sensitive.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1300431324 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.