title: Lenguaje recursivamente enumerable
text: # Lenguaje recursivamente enumerable
  
  En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.
  
  ## Definición
  
  Aunque existen varias definiciones equivalentes, ésta es una de las principales:
  
  * Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.
  
  Todos los lenguajes regulares, independientes de contexto, dependientes de contexto y recursivos son recursivamente enumerables.
  
  ## Propiedades de cierre
  
  Los lenguajes recursivamente enumerables son cerrados con las siguientes operaciones. Esto es, si $L$ y $P$ son dos lenguajes recursivamente enumerables, entonces los siguiente lenguajes son recursivamente enumerables también:
  
  * el cierre estrella $L^{*}$ de $L$
  * la concatenación $L\circ P$ de $L$ y $P$
  * la unión $L\cup P$ de $L$ y $P$
  * la intersección $L\cap P$ de $L$ y $P$
  
  Nótese que los lenguajes recursivamente enumerables no son cerrados con la diferencia ni el complementario.
  
  * $L\setminus P$ puede no ser recursivamente enumerable
  * ${\bar {L}}$ es recursivamente enumerable si y solo si $L$ es también recursivo.
  