6.1 PROBLEMAS INSOLUBLES TEORIAS DE LENGUAJES

Sea el problema Palguna el siguiente problema:

Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre alguna cadena?

Para demostrar que Palguna no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Palguna. Demostración:

Supongamos que Palguna es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), Alguna, que resuelve Palguna. Alguna toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T se detiene sobre alguna cadena o no. Es decir Alguna recibe como entrada (T) y retorna un 1 si T se detiene para alguna cadena, mientras que devuelve la salida 0 si T no se detiene para ninguna cadena. Construyamos a partir de Alguna, un procedimiento efectivo (o máquina universal de Turing)