Lenguaje recursivamente enumerable

En matemáticas , lógica e informática , un lenguaje formal se denomina recursivamente enumerable (también reconocible , parcialmente decidible , semidecidible , Turing-aceptable o Turing-reconocible ) si es un subconjunto recursivamente enumerable del conjunto de todas las palabras posibles sobre el alfabeto del lenguaje, es decir, si existe una máquina de Turing que enumerará todas las cadenas válidas del lenguaje. Estas se generan mediante gramáticas no restringidas .

En la jerarquía de lenguajes formales de Chomsky , los lenguajes recursivamente enumerables se conocen como lenguajes de tipo 0. Todos los lenguajes regulares , libres de contexto , sensibles al contexto y recursivos son recursivamente enumerables.

La clase de todos los lenguajes recursivamente enumerables se llama RE .

Existen tres definiciones equivalentes de un lenguaje recursivamente enumerable:

1. Un lenguaje recursivamente enumerable es un subconjunto recursivamente enumerable en el conjunto de todas las palabras posibles sobre el alfabeto del lenguaje .
2. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing (u otra función computable ) que enumera todas las cadenas válidas del lenguaje. Cabe destacar que, si el lenguaje es infinito , el algoritmo de enumeración proporcionado puede elegirse de manera que evite repeticiones, ya que podemos comprobar si la cadena producida para el número n ya se ha producido para un número menor que n . Si ya se ha producido, se utiliza la salida para la entrada n + 1 (de forma recursiva), pero nuevamente se comprueba si es "nueva".
3. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing (u otra función computable) que se detiene y acepta cuando se le presenta como entrada cualquier cadena del lenguaje, pero puede detenerse y rechazar o entrar en un bucle infinito cuando se le presenta una cadena que no pertenece al lenguaje. Esto contrasta con los lenguajes recursivos , que requieren que la máquina de Turing se detenga en todos los casos.

Todos los lenguajes regulares , libres de contexto , sensibles al contexto y recursivos son enumerables recursivamente.

El teorema de Post muestra que RE , junto con su complemento co-RE , corresponden al primer nivel de la jerarquía aritmética .

El conjunto de máquinas de Turing que se detienen es recursivamente enumerable, pero no recursivo. De hecho, se puede ejecutar la máquina de Turing y aceptar su parada, por lo que es recursivamente enumerable. Por otro lado, el problema es indecidible.

Otros lenguajes recursivamente enumerables que no son recursivos incluyen:

• Problema de correspondencia postal
• Mortalidad (teoría de la computabilidad)
• Problema de decisión

Los lenguajes recursivamente enumerables (REL) son cerrados bajo las siguientes operaciones. Es decir, si L y P son dos lenguajes recursivamente enumerables, entonces los siguientes lenguajes también lo son:

• la estrella Kleene${\displaystyle L^{*}}$de L
• la concatenación${\displaystyle L\circ P}$de L y P
• el sindicato${\displaystyle L\cup P}$
• la intersección${\displaystyle L\cap P}$.

Los lenguajes recursivamente enumerables no son cerrados bajo la diferencia de conjuntos ni bajo la complementación. La diferencia de conjuntos${\displaystyle LP}$es recursivamente enumerable si${\displaystyle P}$es recursivo. Si${\displaystyle L}$es recursivamente enumerable, entonces el complemento de${\displaystyle L}$es recursivamente enumerable si y solo si${\displaystyle L}$También es recursivo.

• Conjunto enumerable computacionalmente
• Recursión

• Sipser, Michael (1997). Introducción a la teoría de la computación (1.ª  ed.). PWS Publishing. ISBN 978-0-534-94728-6.( Accesible para usuarios con discapacidades visuales )
• Kozen, DC (1997), Autómatas y computabilidad , Springer .

• Zoológico de la complejidad : Clase RE