Recursive language

Definitions

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

1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accepts if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a decider and is said to decide the recursive language.

By the second definition, any decision problem can be shown to be decidable by exhibiting an algorithm for it that terminates on all inputs. An undecidable problem is a problem that is not decidable.

Examples

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\,\}}$

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^{cn}}}$, for some constant c>0 (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 ${\displaystyle c^{n}}$ for some constant c^{[citation needed]}, the set of valid formulas in Presburger arithmetic is not context-sensitive. On 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 (Oppen 1978). Thus, this is an example of a language that is decidable but not context-sensitive.

Closure properties

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^{*}}$
• The image φ(L) under an e-free homomorphism φ
• The concatenation ${\displaystyle L\circ P}$
• The union ${\displaystyle L\cup P}$
• The intersection ${\displaystyle L\cap P}$
• The complement of ${\displaystyle L}$
• The set difference ${\displaystyle L-P}$

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

See also

• Recursively enumerable language
• Recursion

References

• Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:.
• 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.