Definición y concepto
En el ámbito de las matemáticas, la lógica y la informática, un lenguaje recursivamente enumerable constituye un tipo fundamental de lenguaje formal. Este concepto es también conocido bajo los sinónimos de parcialmente decidible o Turing-computable. Dentro de la clasificación establecida por la Jerarquía de Chomsky, estos conjuntos de cadenas se identifican específicamente como lenguajes tipo-0, ocupando así la categoría más amplia en dicha taxonomía formal.
Caracterización mediante la máquina de Turing
La definición formal de un lenguaje recursivamente enumerable se basa intrínsecamente en el comportamiento de una máquina de Turing. Un lenguaje formal se considera recursivamente enumerable si existe al menos una máquina de Turing que lo acepta. Esto implica que para cualquier cadena que pertenezca al lenguaje, la máquina de Turing asociada procesará la entrada y eventualmente se detendrá en un estado de aceptación. Esta propiedad garantiza que la pertenencia de una cadena al lenguaje puede ser verificada mediante un proceso computacional finito.
Una característica distintiva de los lenguajes recursivamente enumerables, en contraste con los lenguajes recursivos completamente decidibles, radica en el comportamiento de la máquina frente a las cadenas que no pertenecen al lenguaje. Si se presenta a la máquina de Turing una cadena que no forma parte del lenguaje, la máquina puede iterar indefinidamente. Es decir, la máquina puede continuar procesando la entrada sin llegar nunca a un estado de aceptación ni necesariamente a un estado de rechazo explícito en un tiempo finito. Esta posibilidad de iteración infinita define la naturaleza de la "parcial" decidibilidad de estos conjuntos.
Relación con otras clases de lenguajes
La clase de los lenguajes recursivamente enumerables posee una propiedad de inclusión abarcadora dentro de la teoría de la computación. Todos los lenguajes regulares, los lenguajes independientes de contexto, los lenguajes dependientes de contexto y los lenguajes recursivos son, por definición, subconjuntos de los lenguajes recursivamente enumerables. Esta jerarquía demuestra que la capacidad de ser enumerado por una máquina de Turing es una propiedad fundamental que comparten las clases gramaticales inferiores de la Jerarquía de Chomsky, consolidando al lenguaje tipo-0 como el conjunto más extenso en esta estructura teórica.
¿Qué diferencia a los lenguajes recursivamente enumerables de los recursivos?
La distinción fundamental entre un lenguaje recursivo y uno recursivamente enumerable radica en el comportamiento de la máquina de Turing que los acepta. Mientras que ambos tipos de lenguajes son aceptados por máquinas de Turing, la condición de detención varía significativamente según si el lenguaje pertenece a la clase recursiva o a la clase recursivamente enumerable.
Comportamiento de la máquina de Turing
En el caso de los lenguajes recursivos, la máquina de Turing asociada debe detenerse para cualquier cadena de entrada, independientemente de si la cadena pertenece o no al lenguaje. Esto significa que existe un algoritmo que, dado cualquier símbolo o secuencia de símbolos, devolverá un resultado definitivo (aceptación o rechazo) en un tiempo finito. Esta propiedad garantiza que la decidibilidad es total sobre el alfabeto del lenguaje.
Por el contrario, para los lenguajes recursivamente enumerables, la máquina de Turing solo está garantizada de detenerse y aceptar cuando la cadena de entrada pertenece al lenguaje. Si la cadena no pertenece al lenguaje, la máquina puede continuar iterando indefinidamente sin llegar a un estado de aceptación ni necesariamente a un estado de rechazo explícito. Esta característica define la naturaleza de "parcialmente decidible" o "Turing-computable" de estos lenguajes, también conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.
Tabla comparativa de propiedades de decisión
| Propiedad | Lenguaje Recursivo | Lenguaje Recursivamente Enumerable |
|---|---|---|
| Decidibilidad | Totalmente decidible | Parcialmente decidible |
| Comportamiento en cadenas pertenecientes | La máquina de Turing se detiene y acepta | La máquina de Turing se detiene y acepta |
| Comportamiento en cadenas no pertenecientes | La máquina de Turing se detiene y rechaza | La máquina de Turing puede iterar indefinidamente |
| Clasificación en la Jerarquía de Chomsky | Incluye tipos más altos (tipo-1, tipo-2, tipo-3) | Tipo-0 |
| Relación de inclusión | Subconjunto de los recursivamente enumerables | Incluye a los lenguajes recursivos |
Esto implica que la clase de los lenguajes recursivamente enumerables es más amplia, abarcando aquellos casos donde la decisión no siempre se resuelve en un tiempo finito para todas las posibles entradas, sino solo para aquellas que efectivamente pertenecen al conjunto definido por el lenguaje formal.
Clasificación en la Jerarquía de Chomsky
Los lenguajes recursivamente enumerables ocupan la posición más amplia en la Jerarquía de Chomsky, siendo clasificados formalmente como lenguajes tipo-0. Esta clasificación establece un marco estructurado para entender la complejidad sintáctica de los lenguajes formales en teoría de la computación y lingüística formal. La ubicación del tipo-0 en la cúspide de esta jerarquía implica que abarca a todas las demás categorías de lenguajes definidos en el modelo, actuando como el conjunto supremo dentro de esta taxonomía formal.
Estructura de la Jerarquía de Chomsky
La Jerarquía de Chomsky organiza los lenguajes formales en cuatro niveles principales, donde cada nivel es un subconjunto del siguiente. Los lenguajes tipo-0, o recursivamente enumerables, representan el nivel más general. Esto significa que cualquier lenguaje que pertenezca a las categorías inferiores —regulares, independientes de contexto y dependientes de contexto— pertenece automáticamente a la categoría de lenguajes recursivamente enumerables. Además, incluso los lenguajes recursivos, que son un subconjunto propio de los recursivamente enumerables, se encuentran contenidos dentro de este tipo-0.
| Tipo | Nombre del Lenguaje | Relación con Tipo-0 |
|---|---|---|
| Tipo-3 | Regular | Subconjunto |
| Tipo-2 | Independiente de contexto | Subconjunto |
| Tipo-1 | Dependiente de contexto | Subconjunto |
| Tipo-0 | Recursivamente enumerable | Conjunto total |
Esta inclusión jerárquica refleja la capacidad de las máquinas de Turing para reconocer estos lenguajes. Mientras que los lenguajes de tipos superiores tienen restricciones más estrictas en su estructura y reconocimiento, los lenguajes tipo-0 permiten la máxima flexibilidad computacional, donde la máquina puede aceptar cadenas del lenguaje deteniéndose, mientras que para las cadenas fuera del lenguaje, puede iterar indefinidamente. Esta propiedad los convierte en la clase más amplia de lenguajes formales decidibles parcial o totalmente por máquinas de Turing.
Propiedades de cierre
Los lenguajes recursivamente enumerables poseen propiedades de cierre fundamentales que definen su comportamiento bajo operaciones formales estándar. Estas propiedades son esenciales para comprender la estructura de la clase de lenguajes tipo-0 en la jerarquía de Chomsky. El análisis de estas operaciones revela qué combinaciones de lenguajes mantienen la propiedad de ser aceptados por una máquina de Turing que se detiene al menos para las cadenas pertenecientes al lenguaje.
Operaciones bajo las cuales están cerrados
Esta clase de lenguajes es cerrada bajo varias operaciones básicas. Si se consideran dos lenguajes recursivamente enumerables, denotados como L y P, las siguientes operaciones producen resultados que también son recursivamente enumerables:
- Unión: La unión de dos lenguajes recursivamente enumerables es recursivamente enumerable. Esto significa que si L y P pertenecen a esta clase, entonces L ∪ P también lo hace. Una máquina de Turing puede aceptar la unión ejecutando las máquinas correspondientes a L y P en paralelo o de forma intercalada.
- Concatenación: La concatenación de L y P, denotada como LP o L · P, resulta en un lenguaje recursivamente enumerable. Esto implica que cualquier cadena formada por una subcadena de L seguida de una subcadena de P pertenece a la clase.
- Cierre estrella (Estrella de Kleene): El cierre estrella de un lenguaje recursivamente enumerable L, denotado como L*, es también recursivamente enumerable. Esto abarca todas las concatenaciones finitas de cadenas de L, incluyendo la cadena vacía.
Estas propiedades de cierre permiten construir lenguajes complejos a partir de componentes más simples sin salir de la clase de los lenguajes parcialmente decidibles o Turing-computables.
Operaciones bajo las cuales NO están cerrados
A diferencia de otras clases en la jerarquía, los lenguajes recursivamente enumerables no son cerrados bajo todas las operaciones booleanas o de complemento. Es crucial distinguir estas limitaciones:
- Complemento: La clase no es cerrada bajo complemento. Si L es recursivamente enumerable, su complemento L' no necesariamente lo es. Solo si tanto L como L' son recursivamente enumerables, entonces L es recursivo (totalmente decidible).
- Intersección: Aunque la intersección de dos lenguajes recursivamente enumerables es recursivamente enumerable, es importante notar que la intersección de un lenguaje recursivamente enumerable y el complemento de otro puede no serlo, debido a la falta de cierre bajo complemento. Sin embargo, la intersección directa L ∩ P sí es recursivamente enumerable.
La falta de cierre bajo complemento es una propiedad distintiva que separa a los lenguajes recursivamente enumerables de los lenguajes recursivos, donde la decisión es siempre definitiva para toda cadena.
| Operación | Resultado | Notación |
|---|---|---|
| Unión | Cerrado | L ∪ P |
| Concatenación | Cerrado | LP |
| Cierre estrella | Cerrado | L* |
| Intersección | Cerrado | L ∩ P |
| Complemento | No cerrado | L' |
Estas propiedades de cierre son fundamentales para el análisis de la complejidad computacional y la clasificación de lenguajes formales en teoría de la computación. La comprensión de estas operaciones permite determinar la naturaleza decidible o parcialmente decidible de lenguajes compuestos.
¿Por qué no son cerrados bajo diferencia ni complementario?
Propiedades de cierre y límites computacionales
La clase de los lenguajes recursivamente enumerables presenta limitaciones estructurales fundamentales respecto a las operaciones de conjunto. A diferencia de los lenguajes regulares o independientes de contexto, esta clase no es cerrada bajo la operación de diferencia. Esto significa que, dados dos lenguajes recursivamente enumerables, el resultado de restar uno del otro no garantiza que el lenguaje resultante mantenga la propiedad de ser recursivamente enumerable. Esta falta de cierre tiene implicaciones profundas para la decidibilidad y la estructura de la Jerarquía de Chomsky.
La razón fundamental radica en la naturaleza de la aceptación por parte de las máquinas de Turing. Un lenguaje es recursivamente enumerable si existe una máquina de Turing que acepta todas las cadenas pertenecientes a él, deteniéndose en un número finito de pasos. Sin embargo, para las cadenas que no pertenecen al lenguaje, la máquina puede iterar indefinidamente sin detenerse. Esta asimetría entre la aceptación (siempre finita) y el rechazo (potencialmente infinita) impide que las operaciones que requieren verificar la ausencia de elementos funcionen de manera predecible dentro de la clase.
El caso del lenguaje complementario ilustra claramente esta restricción. El complementario de un lenguaje recursivamente enumerable es recursivamente enumerable si y solo si el lenguaje original es también recursivo. Esta condición necesaria y suficiente establece una distinción crítica entre los lenguajes parcialmente decidibles y los completamente decidibles. Si un lenguaje es recursivo, existe una máquina de Turing que se detiene para toda cadena, aceptando o rechazando explícitamente. En este caso, el complementario también será recursivamente enumerable, ya que la misma máquina puede invertirse para aceptar lo que antes rechazaba.
Si el lenguaje no es recursivo, su complementario puede dejar de ser recursivamente enumerable. Esto ocurre porque la capacidad de enumerar los elementos de un lenguaje no implica la capacidad de enumerar los elementos que faltan, a menos que exista un procedimiento de decisión completa. Por lo tanto, la propiedad de ser recursivamente enumerable no es suficiente para garantizar que el complementario mantenga la misma clasificación, revelando la complejidad inherente a los lenguajes tipo-0 en la teoría de la computación.
Ejercicios resueltos
Ejercicio 1: Cierre bajo la unión de lenguajes RE
Se demuestra que la clase de lenguajes recursivamente enumerables (RE) es cerrada bajo la operación de unión. Sean L1 y L2 dos lenguajes RE. Por definición, existen máquinas de Turing M1 y M2 tales que M1 acepta L1 y M2 acepta L2. Esto implica que si una cadena w pertenece al lenguaje, la máquina correspondiente se detiene en un estado de aceptación.
Construimos una máquina de Turing M que acepta L1 ∪ L2 utilizando la técnica de doyle (intercalación de pasos). La máquina M recibe una cadena w y ejecuta alternadamente un paso de M1 y un paso de M2 sobre copias de w. El algoritmo es el siguiente:
- Paso 1: Ejecutar un paso de M1 sobre w. Si M1 acepta, M acepta.
- Paso 2: Ejecutar un paso de M2 sobre w. Si M2 acepta, M acepta.
- Repetir los pasos 1 y 2 hasta que alguna máquina acepte.
Si w ∈ L1, M1 eventualmente se detiene y acepta, por lo que M acepta. Lo mismo ocurre si w ∈ L2. Si w pertenece a ambos, M también acepta. Si w no pertenece a ninguno, ambas máquinas pueden iterar indefinidamente, y M también iterará indefinidamente. Por lo tanto, L1 ∪ L2 es RE.
Ejercicio 2: El complementario de un lenguaje RE no es necesariamente RE
Se analiza por qué la clase de lenguajes RE no es cerrada bajo complementación. Un lenguaje L es recursivo si tanto L como su complementario L' son RE. Sin embargo, existen lenguajes RE cuyo complementario no es RE. Consideremos el lenguaje de la aceptación de la máquina de Turing, LA = { <M, w> | M es una máquina de Turing que acepta la cadena w }. Se sabe que LA es RE porque existe una máquina universal que simula M sobre w y acepta si M acepta.
Supongamos por contradicción que el complementario LA' también es RE. Entonces, existiría una máquina de Turing M' que acepta LA'. Si ambos LA y LA' fueran RE, podríamos decidir LA ejecutando ambas máquinas en paralelo (como en el ejercicio anterior). Una de ellas tendría que aceptar necesariamente, lo que haría a LA recursivo (totalmente decidible). Sin embargo, se demuestra mediante la reducción del problema de la parada que LA es parcialmente decidible pero no totalmente decidible. Por lo tanto, LA' no puede ser RE. Esto confirma que la propiedad de ser recursivamente enumerable no garantiza que el complementario sea también recursivamente enumerable.
Aplicaciones en informática y lingüística formal
Su estudio es fundamental para comprender los límites de la computabilidad y la estructura de los sistemas formales. La definición establece que un lenguaje es recursivamente enumerable si existe una máquina de Turing que acepta y se detiene para cualquier cadena perteneciente al mismo. Esta propiedad de aceptación finita contrasta con el comportamiento ante las cadenas ajenas al lenguaje, donde la máquina puede iterar indefinidamente sin detenerse. Esta característica define la naturaleza de la decisión parcial o Turing-computable.
Relación con la teoría de la computación
En el ámbito de la teoría de la computación, estos lenguajes representan el conjunto de problemas semi-decidibles. La existencia de una máquina de Turing aceptora implica que la pertenencia de una cadena al lenguaje puede ser verificada en tiempo finito si la respuesta es afirmativa. Sin embargo, la ausencia de garantía de parada para las cadenas no pertenecientes introduce la noción de iteración indefinida. Esta distinción es crucial para diferenciar entre lenguajes recursivos, donde la máquina siempre se detiene, y los meramente recursivamente enumerables. Todos los lenguajes regulares, independientes de contexto, dependientes de contexto y recursivos son subconjuntos de los lenguajes recursivamente enumerables, lo que demuestra su capacidad abarcadora dentro de la jerarquía formal.
Aplicaciones en lingüística formal y lógica
En lingüística formal, la clasificación tipo-0 proporciona un marco para analizar estructuras sintácticas complejas que superan las capacidades de los autómatas finitos o las pilas. La capacidad de la máquina de Turing para iterar indefinidamente permite modelar dependencias léxicas y estructurales que requieren memoria ilimitada o acceso aleatorio. En lógica matemática, estos lenguajes se asocian con conjuntos enumerables por una función computable. La relación entre la aceptación de cadenas y la verdad de enunciados lógicos permite utilizar máquinas de Turing como modelos de demostración. El análisis de estos lenguajes facilita el estudio de la completitud y la consistencia en sistemas formales, donde la decisión parcial refleja la posibilidad de verificar teoremas sin garantizar la refutación de axiomas en tiempo finito.