Recursively enumerable language

<h2 id="definitions">Definitions</h2>
<p>There are three equivalent definitions of a recursively enumerable language:
</p>
<ol><li>A recursively enumerable language is a <a href="/facts/Recursively_enumerable_set/lpzr8jHn">recursively enumerable</a> <a href="/facts/Subset/SJGERmbA">subset</a> in the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of all possible words over the <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> of the <a href="/facts/Formal_language/crDTyP8q">language</a>.</li>
<li>A recursively enumerable language is a formal language for which there exists a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> (or other <a href="/facts/Computable_function/dzwBlLGn">computable function</a>) which will enumerate all valid strings of the language. Note that if the language is <a href="/facts/Infinity/cF506uD7">infinite</a>, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number <i>n</i> is "already" produced for a number which is less than <i>n</i>. If it already is produced, use the output for input <i>n</i>+1 instead (recursively), but again, test whether it is "new".</li>
<li>A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any <a href="/facts/Literal_string/Fj41vtVm">string</a> in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to <a href="/facts/Recursive_language/4R0zBWJE">recursive languages</a>, which require that the Turing machine halts in all cases.</li></ol>
<p>All <a href="/facts/Regular_language/ahxw67T1">regular</a>, <a href="/facts/Context-free_language/sHDxB5So">context-free</a>, <a href="/facts/Context-sensitive_language/01l81plI">context-sensitive</a> and <a href="/facts/Recursive_language/4R0zBWJE">recursive</a> languages are recursively enumerable.
</p><p><a href="/facts/Post%2527s_theorem/wPId3E7D">Post's theorem</a> shows that <a href="/facts/RE_(complexity)/lqtossYw">RE</a>, together with its <a href="/facts/Complement_(complexity)/FHLM6XGe">complement</a> <a href="/facts/Co-RE/lqtossYw">co-RE</a>, correspond to the first level of the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>.
</p>
<h2 id="example">Example</h2>
<p>The set of <a href="/facts/Halting_Problem/Xz1bac40">halting Turing machines</a> is recursively enumerable but not recursive. Indeed, one can run the Turing machine and accept if the machine halts, hence it is recursively enumerable. On the other hand, the problem is undecidable.
</p><p>Some other recursively enumerable languages that are not recursive include:
</p>
<ul><li><a href="/facts/Post_correspondence_problem/YjHh66CM">Post correspondence problem</a></li>
<li><a href="/facts/Mortality_(computability_theory)/UqlfLguC">Mortality (computability theory)</a></li>
<li><a href="/facts/Entscheidungsproblem/y8LDal2X">Entscheidungsproblem</a></li></ul>
<h2 id="closure-properties">Closure properties</h2>
<p>Recursively enumerable languages (REL) are <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> under the following operations. That is, if <i>L</i> and <i>P</i> are two recursively enumerable languages, then the following languages are recursively enumerable as well:
</p>
<ul><li>the <a href="/facts/Kleene_star/I6SX0f2Y">Kleene star</a> 
  
    
      
        
          L
          
            ∗
          
        
      
    
    {\displaystyle L^{*}}
  
 of <i>L</i></li>
<li>the <a href="/facts/Concatenation/1npYg6rc">concatenation</a> 
  
    
      
        L
        ∘
        P
      
    
    {\displaystyle L\circ P}
  
 of <i>L</i> and <i>P</i></li>
<li>the <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> 
  
    
      
        L
        ∪
        P
      
    
    {\displaystyle L\cup P}
  
</li>
<li>the <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> 
  
    
      
        L
        ∩
        P
      
    
    {\displaystyle L\cap P}
  
.</li></ul>
<p>Recursively enumerable languages are not closed under <a href="/facts/Set_difference/yWUePIYY">set difference</a> or complementation. The set difference 
  
    
      
        L
        −
        P
      
    
    {\displaystyle L-P}
  
 is recursively enumerable if 
  
    
      
        P
      
    
    {\displaystyle P}
  
 is recursive.  If 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is recursively enumerable, then the complement of 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is recursively enumerable <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is also recursive.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Computably_enumerable_set/lpzr8jHn">Computably enumerable set</a></li>
<li><a href="/facts/Recursion/CxSKxJoW">Recursion</a></li></ul>
<h2 id="sources">Sources</h2>
<ul><li><a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, Michael</a> (1997). <i><a href="/facts/Introduction_to_the_Theory_of_Computation/CXXk8vfj">Introduction to the Theory of Computation</a></i> (1st ed.). PWS Publishing. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-534-94728-6. (<a href="https://archive.org/details/introductiontoth00sips">accessible to patrons with print disabilities</a>)</li>
<li>Kozen, D.C. (1997), <i>Automata and Computability</i>, <a href="/facts/Springer-Verlag/nAesf6nT">Springer</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><i><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a></i>: <a href="https://complexityzoo.net/Complexity_Zoo:R#re">Class RE</a></li>
<li><a href="http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf">Lecture slides</a></li></ul>

Recursively enumerable language open-in-new

Recursively enumerable language