Problemas insolubles

Universidad Nacional del Sur Fundamentos de Ciencias de la Computación

Departamento de Cs. e Ing. de la Computación 1er Cuatrimestre de 2005

Problemas Insolubles Ejemplos
A continuación enunciaremos una serie de problemas y demostraremos, mediante la técnica de reducibilidad, que los mismos son indecidibles (no solubles a través de una máquina de Turing o de un procedimiento efectivo) Através de Pdet, haremos referencia al problema de la detención, ya conocido: Pdet: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre una determinada cadena α? Ahora consideremos los problemas que queremos demostrar insolubles.

Ejemplo 1:
Sea el problema Pacept el siguiente problema: Pacept: ¿Existe un procedimiento efectivo capaz de determinar si unamáquina de Turing acepta una determinada cadena α? Otra manera de formular el problema sería: Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una determinada cadena, α, pertenece al lenguaje que reconoce la máquina de Turing T? Para demostrar que Pacept no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a quela solubilidad de Pacept implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Pacept. Demostración: Supongamos que Pacept es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), X, que resuelve Pacept. X toma como datos de entrada la descripción de una máquina de Turing T y unacadena α y determina en un tiempo finito si T acepta o no a la cadena α. Es decir X recibe como entrada al par (T,α) y retorna un 1 si T acepta α, mientras que devuelve la salida 0 si T no acepta α. T

1 si T acepta α
X

α

0 si T no acepta α

Construyamos a partir de X, un procedimiento efectivo (o máquina universal de Turing) Y

-1-

Universidad Nacional del Sur Fundamentos deCiencias de la Computación

Departamento de Cs. e Ing. de la Computación 1er Cuatrimestre de 2005

T’

∆X

T

1

1 si T’ se detiene
sobre α

X
α

0

detiene sobre α

0 si T’ no se

Y
La máquina Y recibe como entrada un par (T’,α), la cadena de ambos problemas es la misma, lo que necesitamos es un proceso adicional que modifique T’ de manera que las respuestas de X, respondan elproblema de la detención. Este proceso adicional se lleva a cabo en la máquina universal ∆X que realiza lo siguiente: a. Recibe como dato de entrada la máquina de Turing T’. b. Modifica T’ manteniendo su definición de quíntuplas pero indicando que todos los estados son aceptadores. c. Retorna la máquina modificada con el nombre T. Combinando las máquinas X y ∆X, tenemos la máquina universal Y quetiene el siguiente comportamiento: 1. 2. 3. 4. Y recibe como entrada el par (T’, α). La máquina universal Y utiliza ∆X, la cual a partir de T’ construye T. El par (T, α) es ingresado a la máquina universal X. Si la respuesta de X es 1 entonces T acepta α pero entonces T’ se detiene sobre α. Dado que T se comporta como T’ solo que siempre que se detiene acepta, podemos afirmar que T’ se detienesobre α y que por lo tanto Y emite un 1 5. Si la respuesta de X es 0 entonces T no acepta α pero entonces T’ no se detiene sobre α. Dado que T tiene a todos sus estados como aceptadores, significa que para no aceptar la cadena, la única posibilidad es que T no se haya detenido. Como T se comporta como T’, podemos afirmar que esta tampoco se detiene y por lo tanto Y emite un 0, ya que T’ no sedetiene sobre α.

Conclusión: • La máquina universal Y retorna 1 (T’ se detiene sobre α) si X retorna 1 (T acepta α). • La máquina universal Y retorna 0 (T’ no se detiene sobre α) si X retorna 0 (T no acepta α). Hemos mostrado como construir la máquina universal Y que resuelve el problema de la detención a partir de la máquina universal X que resuelve un problema que supusimos soluble.

-2-...