Problemas imposibles

Hay algunos problemas que son imposibles de resolver. No porque se necesite a alguien que sea un genio para resolverlos, sino porque simplemente no tienen solución. Estos problemas ponen un límite a lo que se puede resolver mediante el cómputo.

El más famoso de estos problemas es el Halting Problem (HP) o Problema de la detención en español.

El enunciado de este problema es: "Dada una descripción de un programa y una entrada inicial, determinar si el programa, cuando se ejecuta con esa entrada, se detiene".

En 1936 Alan Turing demostró que un algoritmo general para resolver este problema para todas las posibles entradas no podía existir.

Aunque las consecuencias de resolver este problema podrían parecer triviales a simple vista (un compilador que determine si el programa que estamos compilando tiene un loop infinito), son muy importantes.

Una de las más importantes es que no podemos construir un algoritmo para determinar si un enunciado acerca de los números naturales es verdadero. Esto está relacionado con la principal búsqueda de los matemáticos a principios del siglo XX: un algoritmo que dado un enunciado (posible teorema), determine si éste es verdadero. Si HP pudiera resolverse, entonces muchos teoremas podrían ser fácilmente probados mediante el sencillo procedimiento de hacer un algoritmo de fuerza bruta que pruebe todos los posibles valores y se detenga en el primer valor que no cumpla el enunciado. Luego determinamos si el algoritmo se detiene, si es así, entonces el teorema no se cumplía. La mayoría de los problemas abiertos de teoría de números, caerían ante este procedimiento. Los matemáticos de principios del siglo XX eran bastante ambiciosos.

De todas formas se puede argumentar que ese algoritmo sólo es teórico, ya que en la práctica las computadoras tienen un límite en la cantidad de números que pueden representar y sería imposible chequear todos los naturales.

Halting problem