 | Este artículo incluye una lista de referencias , lecturas relacionadas o enlaces externos , pero sus fuentes siguen sin estar claras porque carece de citas en línea . ( Enero de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) |
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 de el 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 Chomsky de lenguajes formales. Todos los regulares , libres de contexto , sensibles al contexto y recursivos lenguas son recursivamente enumerables.
La clase de todos los lenguajes enumerables de forma recursiva se llama RE .
Definiciones [ editar ]
Hay tres definiciones equivalentes de un lenguaje enumerable recursivamente:
- Un idioma recursivamente enumerable es un subconjunto recursivamente enumerable en el conjunto de todas las palabras posibles sobre el alfabeto del idioma .
- Un lenguaje recursivamente enumerable 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. Tenga en cuenta que si el lenguaje es infinito , 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 ha producido para un número menor que n . Si ya está producido, use la salida para la entrada n + 1 en su lugar (recursivamente), pero nuevamente, pruebe si es "nuevo".
- Un lenguaje recursivamente enumerable es un lenguaje formal para el que existe una máquina de Turing (u otra función computable) que se detendrá y aceptará cuando se le presente cualquier cadena en el idioma como entrada, pero puede detenerse y rechazar o repetir para siempre 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 regulares , libres de contexto , sensibles al contexto y recursivos lenguas 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 [ editar ]
El conjunto de máquinas de detención de turing 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 enumerables recursivamente que no son recursivos incluyen:
- Problema de correspondencia postal
- Mortalidad (teoría de la computabilidad)
- Entscheidungsproblem
Propiedades de cierre [ editar ]
Los lenguajes recursivamente enumerables (REL) se cierran en 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 de Kleene de L
- la concatenación de L y P
- el sindicato
- la intersección .
Los lenguajes recursivamente enumerables no se cierran bajo diferencia de conjuntos o 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.
Referencias [ editar ]
- 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 [ editar ]
- Complejidad Zoo : Clase RE
- Diapositivas de conferencias
