El complemento de los no decidibles

Anteriormente habíamos establecido que si un lenguaje era decidible entonces su complemento también lo era. Sin embargo, con el descubrimiento le lenguajes y máquinas no decidibles, surge la duda de cómo lucen sus complementos.

Fuera de lo computable #

El complemento de un lenguaje no decidible debe tener una naturaleza diferente hasta lo que hemos visto ahora. Un lenguaje no decidible tendrá una MT que lo acepte sin embargo no podemos garantizar que la máquina termine.

Como establecimos antes. Una MT eventualmente va a poder parar si la cadena que analiza pertenece al lenguaje, quiere decir para todas las cadenas del lenguaje las MT eventualmente pararán aceptando a las cadenas. Para las cadenas no aceptadas, algunas veces terminará o algunas veces se ciclará. En el complemento del lenguaje ocurrirá lo contrario, para todas las cadenas que no pertenecen al lenguaje la MT parará (ya que son las cadenas que en el complemento la MT aceptó y paró) y para las cadenas que debe aceptar se quedará ciclada o determinará aceptar.

Con esto en mente se determina que el complemento de los lenguajes RE conforman a los lenguajes co-RE, es decir aquellos lenguajes para los cuales no podemos determinar para una cadena su pertenencia al lenguaje, pero si su no pertenencia.

Visualizando #

La relación entre estos tipos de lenguajes se puede apreciar en la siguiente figura.

Relación entre RE, co-RE y Rec

Vemos que en el caso de los lenguajes Recursivos (R)/decidibles se trata de la intersección entre los lenguajes RE y co-RE.

¿Qué hay afuera de RE y co-RE? #

Resulta que hay problemas que no se pueden verificar la pertenencia de las cadenas ya sea aceptadas o rechazadas. Por ejemplo el problema:

\[REGULAR = \{ \text{<m>} | L(M) \text{ es un lenguaje regular}\}\]

Es decir \(REGULAR\) contiene todas las descripciones de máquinas de Turing que representan a un lenguaje regular. Resulta que este lenguaje no es ni RE ni co-RE cae fuera de lo computable. Y por lo tanto el complemento también \(\overline{REGULAR}\)

Recursivo pero no Depediente del Contexto #

Hasta ahora los ejemplos de MT o han sido Dependientes del Contexto, es decir se podrían implementar con un ALF o son no decidibles (es decir RE pero no Recursivos). Un ejemplo trivial de una MT que es decidible es una MT universal MUt que decide si otra MT acabará antes de cierto tiempo o número de pasos. Como vemos esta MT debe ser en su naturaleza una MT porque tiene que simular a todas las MT, pero además sabemos que es decidible porque eventualmente para, una vez pasado el tiempo o alcanzado el número de pasos.

La Jerarquía de Chomsky #

Lenguaje Gramática Máquina Ejemplo
NCNR \(REGULAR, \overline{REGULAR} \)
co-RE/R \( \alpha \rightarrow \beta \) MT,ADP,MTₖ,… A̅M̅T, L̅h/L ̅U̅t
RE/R \( \alpha \rightarrow \beta \) MT,ADP,MTₖ,… AMT, Lh/LUt
Lenguaje Dependientes del Contexto \( \gamma A \beta \rightarrow \gamma \alpha \beta \) Autómata Lineal con Frontera \( a^nb^nc^n \)
Lenguaje Independiente del Contexto \( A \rightarrow \alpha \) Autómata de Pila \( a^nb^n \)
Lenguaje Regular \( A \rightarrow bC | d \) AF, AFND y AFND-ε \( a^n \)
comments powered by Disqus