Lenguaje recursivamente enumerable

Lenguaje formal

En matemáticas , lógica y ciencias de la computación , un lenguaje formal se llama 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 lenguaje, es decir, si existe una máquina de Turing que enumerará todas las cadenas válidas del lenguaje.

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

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

Definiciones

Hay tres definiciones equivalentes de un lenguaje enumerable recursivamente:

1. Un lenguaje enumerable recursivamente es un subconjunto enumerable recursivamente en el conjunto de todas las palabras posibles sobre el alfabeto del lenguaje .
2. Un lenguaje enumerable recursivamente es un lenguaje formal para el que existe una máquina de Turing (u otra función computable ) que enumerará todas las cadenas válidas del lenguaje. Nótese que si el lenguaje es infinite , el algoritmo de enumeración proporcionado puede elegirse de modo que evite repeticiones, ya que podemos probar si la cadena producida para el número n "ya" se produjo para un número que es menor que n . Si ya se produjo, use la salida para la entrada n +1 en su lugar (de manera recursiva), pero nuevamente, pruebe 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 detendrá y aceptará cuando se le presente cualquier cadena en el lenguaje como entrada, pero puede detenerse y rechazar o repetirse indefinidamente cuando se le presente una cadena que no esté en el lenguaje. Contraste esto 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 .

Ejemplo

El conjunto de máquinas de Turing que se detienen es recursivamente enumerable, pero no recursiva. De hecho, se puede ejecutar la máquina de Turing y aceptar que la máquina se detenga, por lo que es recursivamente enumerable. Por otra parte, el problema es indecidible.

Algunos otros lenguajes enumerables recursivamente que no son recursivos incluyen:

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

Propiedades del cierre

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

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

Los lenguajes recursivamente enumerables no están cerrados bajo la diferencia de conjuntos o la complementación. La diferencia de conjuntos es recursivamente enumerable si es recursiva. Si es recursivamente enumerable, entonces el complemento de es recursivamente enumerable si y solo si también es recursivo. ${\displaystyle L-P}$ ${\displaystyle P}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

Véase también

• Conjunto computablemente enumerable
• Recursión

Fuentes

• Sipser, M. (1996), Introducción a la teoría de la computación , PWS Publishing Co.
• Kozen, DC (1997), Autómatas y computabilidad , Springer .

Enlaces externos

• Zoológico de la complejidad : Clase RE
• Diapositivas de la conferencia