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) Detención La máquina Detención recibe como entrada un par (T’,α), el problema Palguna solo tiene como entrada una máquina de Turing, por lo que necesitamos un proceso adicional que combine T’ y α de manera que las respuestas de Alguna, respondan el problema 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’ y la cadena α. b. Construye una máquina de Turing T tal que: i. Para la cadena α se comporta como la máquina de Turing T’. j. Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla indefinidamente.
Combinando las máquinas universales Alguna y ΔX, tenemos la máquina universal Detención que tiene el siguiente comportamiento:
1. Detención recibe como entrada el par (T’, α).
2. La máquina universal Detención utiliza ΔX, la cual a partir de T’ y α construye la nueva máquina de Turing T.
3. La máquina de Turing T obtenida en el paso anterior es ingresada a la máquina universal Alguna.
4. Si la respuesta de Alguna es 1 entonces T se detiene para alguna cadena. De la manera en la que construimos T esa cadena necesariamente es la cadena α (ya que para el resto sabemos que la máquina siempre cicla) como el comportamiento de T frente a la cadena α es el mismo que tiene la máquina T’ entonces podemos afirmar que T’ se detiene sobre α y que por lo tanto Detención emite un 1
5. Si la respuesta de Alguna es 0 entonces T no se detiene para ninguna cadena. De la manera en la que construimos T la única cadena sobre la que T podía detenerse era α y que el comportamiento frente a esta cadena era el mismo que el de la máquina T’. Podemos entonces afirmar, que la máquina de Turing T’ tampoco se detiene frente a la cadena y que por lo tanto la respuesta que emite Detención es igual a 0.
