5.2.- El problema de Halting
El problema de Halting o de paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada.
Es decir, si existe una máquina MTh capaz de determinar si cualquier otra máquina se va a detener o no. Es conocido que el problema del alto es indecidible.
Básicamente, Turing definió las bases de las computadoras modernas y planteo un problema sobre ellas, llegando a la conclusión de que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (problema de Halting); el problema de saber si un problema se cuelga cuando corre en la computadora. Turing demostró que el problema de la detención es indecidible, es decir, demostró que había problemas que una maquina no podía resolver.
El problema de la parada o problema de la detención para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Consiste en determinar si una máquina de Turing se detendrá con cierta entrada, o bien quedará en un ciclo infinito. Este fue 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. El razonamiento a seguir sería: si suponiendo que un problema es decidible, podemos demostrar que el problema de la parada tiene solución, entonces podemos llegar a la conclusión de que el problema en cuestión no la tiene, por reducción al absurdo.
* El método de la Diagonalización
La prueba de la indecidibilidad del problema de Halting utiliza una técnica llamada diagonalización, descubierta por el matemático Georg Cantor en 1873. Cantor estaba interesado con el problema de medir los tamaños de los conjuntos infinitos.
Si tenemos dos conjuntos infinitos, ¿cómo podemos decir si uno es más grande que el otro o si son del mismo tamaño? Para conjuntos finitos, por supuesto, responder a estas preguntas es fácil. Nosotros simplemente contamos los elementos de un conjunto finito, y el número resultante es su tamaño.
Pero, si tratamos de contar los elementos de un conjunto infinito, ¡nunca terminaríamos! Así que no podemos utilizar el método de conteo para determinar los tamaños relativos de los conjuntos infinitos.
Aquí dejo un link donde encontré un ejercicio con su respectiva explicación.
http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf
BIBLIOGRAFIA.
http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf
http://www.glyc.dc.uba.ar/santiago/charlas/SdC06.pdf
http://es.wikipedia.org/wiki/Problema_de_la_parada
gracias por el ejemplo
ResponderEliminar