Problema Del Paro

PROBLEMA DE LA PARADA

El problema de parada para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Fue además el primer problema que se demostró formalmente que no tenía solución.

El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe un algoritmo que nos permita determinar si el problema tiene solución.

Una de las razones por la que es importante conocer que el problema de la parada no tiene solución, es que nos permite decidir si otros problemas son resolubles o no

definicion

Sea M una máquina de Turing arbitraria con un alfabeto de entrada Σ. Sea . ¿Puede decidirse si la máquina M se detendrá con la entrada w?

Solución

La respuesta a esta pregunta es negativa. No se puede determinar si una máquina de Turing se detiene con una entrada arbitraria.

Demostración

Para demostrarlo, supongamos que el problema de la parada tiene solución, es decir, supondremos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing para con una entrada determinada.

Consideremos una máquina de Turing P, que recibe como entrada una máquina de Turing M y una cadena w codificadas en la cinta y una a continuación de la otra (Mw), y que se encarga de ejecutar M sobre la cadena w. La máquina P parará y aceptará la entrada si M para con w, y parará y rechazará la entrada si M no para con w.

Modificamos la máquina P, creando una máquina P’ equivalente. Esta máquina no parará si M para con w, y parará si M no para con w.

Ahora crearemos una máquina D, cuya función es la siguiente. Recibe una máquina M, la pasa por una máquina que se encarga de copiar la máquina M a continuación. Por lo tanto, a la salida de la máquina copia, la cinta contendrá MM (la codificación de la máquina repetida). A continuación, D coge este resultado y lo pasa a través de P’. Con esto intentamos decidir si la máquina M para con la entrada M. Es decir, si M para con la entrada M, entonces D no para, y si M no para con la entrada M, entonces D para.

Por último, tomaremos una máquina D (denominaremos SD), y le aplicaremos como entrada una máquina D. SD aplica como entrada a la máquina que recibe, la misma máquina. Por lo tanto, esta máquina en principio parará si D no para con entrada D, y no parará si D para con entrada D. Pero si SD no para y si D para con entrada D, sabiendo que D=SD, llegamos a una contradicción, por que aplicar D a SD debería dar como resultado

...