Sea el problema Y el siguiente:
P: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se
detiene sobre alguna cadena?
Para demostrar que Y 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 Y
implica la solubilidad de P. Expresado de otra manera, demostramos que P se reduce a
Y.
Demostración:
Supongamos que Y 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 Y. X 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
X 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 X, un procedimiento efectivo (o máquina universal de Turing)
Detención
La máquina Detención recibe como entrada un par (T’,α), el problema Y 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 X, 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:
Para la cadena α se comporta como la máquina de Turing T’.
Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla
indefinidamente.
Combinando la máquinas universales X 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 X.
4. Si la respuesta de X 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 X 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.
Conclusión:
• La máquina universal Detención retorna 1 (T’ se detiene sobre α) si X
retorna 1 (T se detiene sobre alguna cadena).
• La máquina universal Detención retorna 0 (T’ no se detiene sobre α) si X
retorna 0 (T se detiene sobre ninguna cadena).
Hemos mostrado como construir la máquina universal Detención que resuelve el
problema de la detención a partir de la máquina universal X que resuelve un
problema que supusimos soluble.
Sabemos por hipótesis que el problema de la detención es un problema insoluble, por
lo tanto la solución encontrada mediante la máquina universal Detención no puede
existir. Lo que implica que alguno de sus componentes no puede existir, es decir
X, o bien ΔX no existe. Como por construcción ΔX existe, luego X no
puede existir.
Podemos entonces concluir que Y es un problema no-soluble.