Indecidibilidad y Reducibilidad en TOC – Part 1

Problemas
decidibles Un problema es decidible si podemos construir una máquina de Turing que se detenga en una cantidad finita de tiempo para cada entrada y responda como ‘sí’ o ‘no’. Un problema decidible tiene un algoritmo para determinar la respuesta para una entrada dada.

Ejemplos

• Equivalencia de dos idiomas regulares: dados dos idiomas regulares, existe un algoritmo y una máquina de Turing para decidir si dos idiomas regulares son iguales o no.
• Finitud del lenguaje regular: dado un lenguaje regular, existe un algoritmo y una máquina de Turing para decidir si el lenguaje regular es finito o no.
• Vacío del lenguaje libre de contexto: dado un lenguaje libre de contexto, hay un algoritmo, ya sea que CFL esté vacío o no.

Problemas indecidibles
Un problema es indecidible si no hay una máquina de Turing que siempre se detenga en un tiempo finito para dar una respuesta como ‘sí’ o ‘no’. Un problema indecidible no tiene un algoritmo para determinar la respuesta para una entrada dada.

Ejemplos

• Ambigüedad de los lenguajes libres de contexto: dado un lenguaje libre de contexto, no existe una máquina de Turing que siempre se detenga en un tiempo finito y dé una respuesta si el lenguaje es ambiguo o no.
• Equivalencia de dos lenguajes libres de contexto: dados dos lenguajes libres de contexto, no hay una máquina de Turing que siempre se detenga en un tiempo finito y responda si dos lenguajes libres de contexto son iguales o no.
• Todo o integridad de CFG: dado un CFG y un alfabeto de entrada, si CFG generará todas las strings posibles de alfabeto de entrada (∑*) es indecidible.
• Regularidad de CFL, CSL, REC y REC: dado un CFL, CSL, REC o REC, determinar si este idioma es regular es indecidible.

Nota: Dos problemas indecidibles populares son el problema de detención de TM y PCP (problema de correspondencia posterior). Problemas semidecidibles
Un problema semidecidible es un subconjunto de problemas indecidibles para los cuales la máquina de Turing siempre se detendrá en un tiempo finito para responder ‘sí’ y puede o no detenerse para responder ‘no’.
La relación entre el problema semidecidible y el decidible se muestra en la Figura 1 como:

Teorema de Rice
Todo problema no trivial (no se conoce la respuesta) en lenguajes Enumerables Recursivos es indecidible.eg; Si un lenguaje es Recursivo Enumerable, su complemento será recursivo enumerable o no es indecidible.

Reducibilidad e indecidibilidad
El lenguaje A es reducible al lenguaje B (representado como A≤B) si existe una función f que convertirá strings en A en strings en B como:

w ɛ A <=> f(w) ɛ B

Teorema 1: Si A≤B y B es decidible, entonces A también es decidible.
Teorema 2: Si A≤B y A es indecidible entonces B también es indecidible.

Pregunta: ¿Cuál de los siguientes es/son indecidibles?

1.  G es un CFG. ¿Es L(G)=ɸ?
2.  G es un CFG. ¿Es L(G)=∑*?
3. M es una máquina de Turing. ¿L(M) es regular?
4.  A es un DFA y N es un NFA. ¿Es L(A)=L(N)?

A. 3 solo
B. 3 y 4 solo
C. 1, 2 y 3 solo
D. 2 y 3 solo

Explicación:

• La opción 1 es si un CFG está vacío o no, este problema es decidible.
• La opción 2 es si un CFG generará todas las strings posibles (todo o la integridad de CFG), este problema es indecidible.
• La opción 3 es si el lenguaje generado por TM es regular es indecidible.
• La opción 4 es decidir si el lenguaje generado por DFA y NFA es el mismo. Entonces la opción D es correcta.

Pregunta: ¿Cuáles de los siguientes problemas son decidibles?

1.  ¿Un programa dado alguna vez produce una salida?
2.  Si L es un lenguaje libre de contexto, ¿entonces L’ también es libre de contexto?
3.  Si L es lenguaje regular, entonces L’ también es regular.
4.  Si L es un lenguaje recursivo, ¿entonces L’ también es recursivo?

A. 1,2,3,4
B. 1,2
C. 2,3,4
D. 3,4

Explicación:

• Como los lenguajes regulares y recursivos están cerrados bajo complementación, las opciones 3 y 4 son problemas decidibles.
• Los lenguajes libres de contexto no están cerrados bajo complementación, la opción 2 es indecidible.
• La opción 1 también es indecidible ya que no hay TM para determinar si un programa dado producirá una salida. Entonces, la opción D es correcta.

Pregunta: Considere tres problemas de decisión P1, P2 y P3. Se sabe que P1 es decidible y P2 es indecidible. ¿Cuál de las siguientes es VERDADERA?

A. P3 es indecidible si P2 es reducible a P3
B. P3 es decidible si P3 es reducible al complemento de P2
C. P3 es indecidible si P3 es reducible a P2
D. P3 es decidible si P1 es reducible a P3
Explicación:

• La opción A dice P2≤P3. De acuerdo con el teorema 2 discutido, si P2 es indecidible, entonces P3 es indecidible. Dado que P2 es indecidible, entonces P3 también será indecidible. Entonces la opción (A) es correcta .
• La opción C dice P3≤P2. De acuerdo con el teorema 2 discutido, si P3 es indecidible, entonces P2 es indecidible. Pero no se cuestiona la indecidibilidad de P3. Entonces la opción (C) no es correcta.
• La opción D dice P1≤P3. De acuerdo con el teorema 1 discutido, si P3 es decidible entonces P1 también es decidible. Pero no se cuestiona la decidibilidad de P3. Entonces la opción (D) no es correcta .
• La opción (B) dice P3≤P2′. Según el teorema 2 discutido, si P3 es indecidible entonces P2′ es indecidible. Pero no se cuestiona la indecidibilidad de P3. Entonces la opción (B) no es correcta .

Cuestionario sobre indecidibilidad

Este artículo es una contribución de Sonal Tuteja . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.