Recursive language

<h2 id="definitions">Definitions</h2>
There are two equivalent major definitions for the concept of a recursive language:

<ol><li>A recursive language is a <a href="/facts/Recursive_set/rsnT9cLn">recursive</a> subset of the set of all possible finite-length <a href="/facts/Formal_language/crDTyP8q">words</a> over an <a href="/facts/Alphabet_(formal_languages)/6KW9qYRW">alphabet</a>.</li>
<li>A recursive language is a <a href="/facts/Formal_language/crDTyP8q">formal language</a> for which there exists a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> that <a href="/facts/Decider_(Turing_machine)/lGTrkxDE">decides</a> it.</li></ol>
On the other hand, we can show that a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> is decidable by exhibiting a Turing machine running an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that terminates on all inputs. An <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable problem</a> is a problem that is not decidable.

<h2 id="examples">Examples</h2>
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

L
        =
        {
        
        w
        ∈
        {
        a
        ,
        b
        ,
        c
        
          }
          
            ∗
          
        
        ∣
        w
        =
        
          a
          
            n
          
        
        
          b
          
            n
          
        
        
          c
          
            n
          
        
        
          
             for some 
          
        
        n
        ≥
        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 <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a> is required: <a href="/facts/Presburger_arithmetic/9R0WMG3h">Presburger arithmetic</a> is the first-order theory of the natural numbers with addition (but without multiplication). While the set of <a href="/facts/First-order_logic/lcISqWIg">well-formed formulas</a> 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
 
 c
 n
 
 
 
 
 
 
 {\displaystyle 2^{2^{cn}}}
 
, for some constant c>0.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Here, n denotes the length of the given formula. Since every context-sensitive language can be accepted by a <a href="/facts/Linear_bounded_automaton/l0ybKuwE">linear bounded automaton</a>, and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most 
 
 
 
 
 c
 
 n
 
 
 
 
 {\displaystyle c^{n}}
 
 for some constant c , 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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Thus, this is an example of a language that is decidable but not context-sensitive.

<h2 id="closure-properties">Closure properties</h2>
Recursive languages are <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:

<ul><li>The <a href="/facts/Kleene_star/I6SX0f2Y">Kleene star</a> 
 
 
 
 
 L
 
 ∗
 
 
 
 
 {\displaystyle L^{*}}
 
</li>
<li>The image φ(L) under an <a href="/facts/Homomorphism/0gyqdEse">e-free homomorphism</a> φ</li>
<li>The concatenation 
 
 
 
 L
 ∘
 P
 
 
 {\displaystyle L\circ P}
 
</li>
<li>The union 
 
 
 
 L
 ∪
 P
 
 
 {\displaystyle L\cup P}
 
</li>
<li>The intersection 
 
 
 
 L
 ∩
 P
 
 
 {\displaystyle L\cap P}
 
</li>
<li>The complement of 
 
 
 
 L
 
 
 {\displaystyle L}
 
</li>
<li>The set difference 
 
 
 
 L
 −
 P
 
 
 {\displaystyle L-P}
 
</li></ul>
The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Recursively_enumerable_language/yBV2vFoC">Recursively enumerable language</a></li>
<li><a href="/facts/Computable_set/rsnT9cLn">Computable set</a></li>
<li><a href="/facts/Recursion/CxSKxJoW">Recursion</a></li></ul>

<ul><li>Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0019-9958%2859%2990362-6">10.1016/S0019-9958(59)90362-6</a>.</li>
<li><a href="/facts/Michael_J._Fischer/22ojkBNd">Fischer, Michael J.</a>; <a href="/facts/Michael_O._Rabin/M6NHIb5J">Rabin, Michael O.</a> (1974). <a href="http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps">"Super-Exponential Complexity of Presburger Arithmetic"</a>. Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.</li>
<li>Oppen, Derek C. (1978). <a href="https://doi.org/10.1016%2F0022-0000%2878%2990021-1">"A 222pn Upper Bound on the Complexity of Presburger Arithmetic"</a>. J. Comput. Syst. Sci. 16 (3): 323–332. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0022-0000%2878%2990021-1">10.1016/0022-0000(78)90021-1</a>.</li>
<li><a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, Michael</a> (1997). <a href="https://archive.org/details/introductiontoth00sips/page/151">"Decidability"</a>. Introduction to the Theory of Computation. PWS Publishing. pp. <a href="https://archive.org/details/introductiontoth00sips/page/151">151–170</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-534-94728-6.</li>
<li><a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, Michael</a> (2012). "The Church-Turing Thesis". Introduction to the Theory of Computation. Cengage Learning. p. 170. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-133-18779-0.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sipser (2012). - Sipser, Michael (2012). "The Church-Turing Thesis". Introduction to the Theory of Computation. Cengage Learning. p. 170. ISBN 978-1-133-18779-0. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sipser (1997). - Sipser, Michael (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6. <a href="https://archive.org/details/introductiontoth00sips/page/151" target="_blank">https://archive.org/details/introductiontoth00sips/page/151</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Chomsky (1959). - Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6. <a href="https://doi.org/10.1016%2FS0019-9958%2859%2990362-6" target="_blank">https://doi.org/10.1016%2FS0019-9958%2859%2990362-6</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Fischer & Rabin (1974). - 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. <a href="http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps" target="_blank">http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Oppen (1978). - Oppen, Derek C. (1978). "A 222pn Upper Bound on the Complexity of Presburger Arithmetic". J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1. <a href="https://doi.org/10.1016%2F0022-0000%2878%2990021-1" target="_blank">https://doi.org/10.1016%2F0022-0000%2878%2990021-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Recursive language open-in-new

Recursive language