Recursive language

This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science).

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.

Definitions

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.

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. ^[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 c^{n}}$ for some constant c^{[ citation needed ]}, 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. ^[5] 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
• Computable set
• Recursion

References

1. Sipser (2012).
2. Sipser (1997).
3. Chomsky (1959).
4. Fischer & Rabin (1974).
5. Oppen (1978).

• 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.