Decidibilidad e Indecidibilidad en TOC – Part 1

Identificar lenguajes (o problemas*) como decidibles, indecidibles o parcialmente decidibles es una pregunta muy común en GATE. Con el conocimiento correcto y una amplia experiencia, esta pregunta se vuelve muy fácil de resolver. Comencemos con algunas definiciones:- Lenguaje decidible: se dice que un problema de decisión P es decidible (es decir, tiene un algoritmo) si el lenguaje L de todas las instancias sí a P es decidible. Ejemplo- (I) (Problema de aceptación para DFA) Dado un DFA, ¿acepta una palabra determinada? (II) (Problema de vacío para DFA) Dado un DFA, ¿acepta alguna palabra? (III) (Problema de equivalencia para DFA) Dados dos DFA, ¿aceptan el mismo idioma?   lenguaje indecidible–– Se dice que un problema de decisión P es indecidible si la lengua L de todas las instancias sí a P no es decidible o una lengua es indecidible si no es decidible. Un lenguaje indecidible tal vez un lenguaje parcialmente decidible o algo más pero no decidible. Si un idioma no es ni siquiera parcialmente decidible, entonces no existe una máquina de Turing para ese idioma.   Lenguaje parcialmente decidible o semidecidible : se dice que un problema de decisión P es semidecidible (es decir, tiene un semialgoritmo) si el lenguaje L de todas las instancias de sí a P es RE. Una lengua ‘L’ es parcialmente decidible si ‘L’ es una lengua RE pero no REC.     Lenguaje recursivo (REC)– Se dice que un lenguaje ‘L’ es recursivo si existe una máquina de Turing que aceptará todas las strings en ‘L’ y rechazará todas las strings que no estén en ‘L’. La máquina de Turing se detendrá cada vez y dará una respuesta (aceptada o rechazada) para todas y cada una de las entradas de string. Un lenguaje ‘L’ es decidible si es un lenguaje recursivo. Todos los lenguajes decidibles son lenguajes recursivos y viceversa.   Lenguaje recursivamente enumerable (RE)– Se dice que un lenguaje ‘L’ es un lenguaje recursivamente enumerable si existe una máquina de Turing que aceptará (y por lo tanto se detendrá) para todas las strings de entrada que están en ‘L’ pero puede o no detenerse para todas las strings de entrada que no están en ‘L’. Por definición, todos los idiomas REC también son idiomas RE, pero no todos los idiomas RE son idiomas REC. Ahora resolvamos algunos ejemplos: una forma de resolver problemas de decidibilidad es tratar de reducir un problema indecidible ya conocido al problema dado. Al reducir un problema P1 a P2, queremos decir que estamos tratando de resolver P1 usando el algoritmo usado para resolver P2. Si podemos reducir un problema indecidible P1 ya conocido a un problema P2 dado, entonces seguramente podemos decir que P2 también es indecidible. Si P2 fuera decidible, entonces P1 también sería decidible pero eso se convierte en una contradicción porque se sabe que P1 es indecidible. Por ej.1. Dada una máquina de Turing ‘M’, necesitamos averiguar si alguna vez se alcanza un estado ‘Q’ cuando se ingresa una string ‘w’ en ‘M’. Este problema también se conoce como el ‘problema de entrada de estado’.Ahora intentemos reducir el problema de la detención al problema de la entrada del estado. ¿Una máquina de Turing solo se detiene cuando una función de transición? (qi, a) no está definido. Cambie cada función no definida ?(qi,a) a ?(qi,a) = (Q, a, L o R). Tenga en cuenta que el estado Q solo se puede alcanzar cuando la máquina de Turing se detiene. Supongamos que tenemos un algoritmo para resolver el problema de entrada de estado que se detendrá cada vez y nos dirá si se puede alcanzar o no el estado Q. Al decirnos que podemos o no alcanzar el estado Q cada vez, nos está diciendo que la máquina de Turing se detendrá o no, cada vez. Pero sabemos que eso no es posible porque el problema de la detención es indecidible. Eso significa que nuestra suposición de que existe un algoritmo que resuelve el problema de entrada de estado y se detiene y nos da una respuesta cada vez, es falsa. Por lo tanto, el problema de la entrada del estado es indecidible.   2. Dados dos lenguajes regulares L1 y L2, es el problema de encontrar si una string ‘w’ existe tanto en L1 como en L2, un problema decidible o no.Primero hacemos dos máquinas de Turing TM1 y TM2 que simulan los DFA de los lenguajes L1 y L2 respectivamente. Sabemos que un DFA siempre se detiene, por lo que una máquina de Turing que simula un DFA también se detendrá siempre. Ingresamos la string ‘w’ en TM1 y TM2. Ambas máquinas de Turing se detendrán y nos darán una respuesta. Podemos conectar las salidas de las máquinas de Turing a una puerta ‘Y’ modificada que generará ‘sí’ solo cuando ambas máquinas de Turing respondan ‘sí’. De lo contrario, generará ‘no’. Dado que este sistema de dos máquinas de Turing y una puerta AND modificada siempre se detendrá, este problema es un problema decidible. Hay muchas preguntas sobre este tema. No existe un algoritmo universal para resolverlos. La mayoría de las preguntas requieren pruebas únicas e ingeniosas. Aquí es donde se necesita experiencia. Al resolver muchos de estos problemas, uno puede llegar a ser muy rápido en encontrar pruebas para estos problemas en el acto. Entonces, sigue practicando. *Las palabras ‘lenguaje’ y ‘problema’ pueden usarse como sinónimos en Teoría de la computación. Por ej. El ‘problema de la detención’ también se puede escribir como ‘L = {<M, w> | La máquina de Turing ‘M’ se detiene en la entrada ‘w’}’. Aquí ‘L’ es un lenguaje. Este artículo ha sido aportado porNitish Joshi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.