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 en el conjunto de todas las palabras posibles sobre el alfabeto del idioma, es decir, si existe una máquina de Turing que enumerará todas las cadenas válidas del idioma.

Los lenguajes recursivamente enumerables se conocen como lenguajes de tipo-0 en la jerarquía de lenguajes formales de Chomsky. 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.

Definiciones

Hay tres definiciones equivalentes de un lenguaje recursivamente enumerable:

1. Un lenguaje recurrentemente enumerable es un subconjunto repetitivamente enumerable en el conjunto de todas las palabras posibles sobre el alfabeto del idioma.
2. Un lenguaje recurrentemente enumerable es un lenguaje formal para el cual existe una máquina de Turing (o otra función computable) que enumerará todas las cadenas válidas del idioma. Tenga en cuenta que si el lenguaje es infinito, el algoritmo de enumeración proporcionado puede ser elegido para evitar las repeticiones, ya que podemos probar si la cadena producida para el número n es "ya" producido para un número que es menor que n. Si ya se produce, utilice la salida para la entrada n+1 en su lugar (recursivamente), pero de nuevo, prueba si es "nuevo".
3. Un lenguaje recurrentemente enumerable es un lenguaje formal para el cual existe una máquina de Turing (o otra función computable) que se detendrá y aceptará cuando se presenta con cualquier cadena en el idioma como entrada pero puede detenerse y rechazar o bucle para siempre cuando se presenta con una cuerda no en el idioma. Contraste esto a idiomas 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 recursivamente enumerables.

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

Ejemplo

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

Algunos otros lenguajes recursivamente enumerables que no son recursivos incluyen:

• Problema de correspondencia postal
• Mortalidad (teoría de responsabilidad)
• Entscheidungsproblem

Propiedades de cierre

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

• la estrella Kleene LAlternativa Alternativa {displaystyle L^{*} de L
• la concatenación L∘ ∘ P{displaystyle Lcirco P} de L y P
• el sindicato L∪ ∪ P{displaystyle Lcup P}
• la intersección L∩ ∩ P{displaystyle Lcap P}.

Los lenguajes enumerables Recursivamente no están cerrados bajo diferencia de conjunto o complementación. La diferencia del juego L{displaystyle L. − P{displaystyle P} es recurrentemente enumerable si P{displaystyle P} es recursivo. Si L{displaystyle L. es recurrentemente enumerable, entonces el complemento de L{displaystyle L. es recurrentemente enumerable si y sólo si L{displaystyle L. también es recursivo.