Lenguaje recursivamente enumerable

Lenguaje formal

En matemáticas , lógica e informática , 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 de el idioma, es decir, si existe una máquina de Turing que enumere 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 enumerables recursivamente se llama RE .

Definiciones

Hay 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 idioma .
2. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing (u otra función computable ) que enumerará todas las cadenas válidas del lenguaje. Tenga en cuenta que si el lenguaje es infinito , el algoritmo de enumeración proporcionado se puede elegir de manera que evite repeticiones, ya que podemos probar si la cadena producida para el número n "ya" está producida para un número menor que n . Si ya está producido, use la salida para la entrada n +1 (recursivamente), pero nuevamente, pruebe si es "nuevo".
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 realizar un bucle indefinido cuando se le presente una cadena. no en el idioma. Compare 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 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 recursiva. De hecho, uno puede ejecutar la máquina de Turing y aceptar si la máquina se detiene, por lo que es recursivamente enumerable. Por otra parte, el problema es indecidible.

Algunos otros lenguajes recursivamente enumerables que no son recursivos incluyen:

• Problema de correspondencia postal
• Mortalidad (teoría de la computabilidad)
• problema de entscheidung

Propiedades de cierre

Los lenguajes enumerables recursivamente (REL) se cierran mediante 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 de L ${\displaystyle L^{*}}$
• la concatenación de L y P ${\displaystyle L\circ P}$
• la Union ${\displaystyle L\cup P}$
• la intersección . ${\displaystyle L\cap P}$

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

Ver también

• Conjunto computablemente enumerable
• recursividad

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 Complejidad : Clase RE
• Diapositivas de conferencias