El problema de halting

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 MThcapaz 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 unproblema 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 cuelgacuando 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 oproblema 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 unciclo

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, problemasa 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 nospermita 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 sonresolubles 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 queel 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,...