Recursive language: Difference between revisions

Revision as of 07:18, 14 July 2025

Revision as of 07:51, 14 July 2025

Line 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^{cn}}</math>, for some constant ''c''>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>c^n</math> for some constant ''c'',{{sfnp|Book|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 ==