Recursive language

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.^[1] In theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms.^[2]

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.^[3] All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

There are two equivalent major definitions for the concept of a recursive language:

1. A recursive language is a recursive subset of the set of all possible finite-length words over an alphabet.
2. A recursive language is a formal language for which there exists a Turing machine that decides it.

On the other hand, we can show that a decision problem is decidable by exhibiting a Turing machine running an algorithm that terminates on all inputs. An undecidable problem is a problem that is not decidable.

As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set L={abc, aabbcc, aaabbbccc, ...}; more formally, the set

${\displaystyle L=\{,円w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1,円\}}${\displaystyle L=\{,円w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 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 ${\displaystyle 2^{2^{pn}}}${\displaystyle 2^{2^{pn}}}, for some constant p>0.^[4] 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 ${\displaystyle q^{n}}${\displaystyle q^{n}} for some constant q,^[5] 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.^[6] Thus, this is an example of a language that is decidable but not context-sensitive.

Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:

• The Kleene star ${\displaystyle L^{*}}${\displaystyle L^{*}}
• The image φ(L) under an e-free homomorphism φ
• The concatenation ${\displaystyle L\circ P}${\displaystyle L\circ P}
• The union ${\displaystyle L\cup P}${\displaystyle L\cup P}
• The intersection ${\displaystyle L\cap P}${\displaystyle L\cap P}
• The complement of ${\displaystyle L}${\displaystyle L}
• The set difference ${\displaystyle L-P}${\displaystyle L-P}

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

• Recursively enumerable language
• Computable set
• Recursion

• Book, Ronald V. (1974). "Comparing complexity classes". Journal of Computer and System Sciences . 9: 213–229. doi:10.1016/S0022-0000(74)80008-5. MR 0366099.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.
• Oppen, Derek C. (1978). "A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic". J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1 .
• Sipser, Michael (1997). "Decidability" . Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.
• Sipser, Michael (2012). "The Church-Turing Thesis". Introduction to the Theory of Computation. Cengage Learning. p. 170. ISBN 978-1-133-18779-0.

• Computability theory
• Formal languages
• Theory of computation
• Recursion

• Articles with short description
• Short description is different from Wikidata