La frase en cuestión dice: "el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente". Ahora bien, en referencia a ella, en su mensaje privado Hernán agrega: eso aplica más para el teorema de Turing pero se entiende el punto. Quiero aprovechar este comentario de Hernán para hacer un agregado a la entrada original, un agregado que en aquel momento preferí omitir para no desviarme del tema central.
Es verdad que se le atribuye a Alan Turing (con justicia hay que decir) el descubrimiento de que existen problemas matemáticos que no son resolubles algorítmicamente; concretamente Turing probó que el Halting Problem es irresoluble. Pero no es menos cierto que la existencia de problemas matemáticos que no son resolubles algorítmicamente también se deduce (como dije en la entrada original) del teorema de incompletitud de Gödel. Veamos...
El teorema de Gödel dice que no es posible dar un sistema de axiomas para la Aritmética que sea al mismo tiempo consistente, recursivo y completo. "Consistente" significa que no existe un enunciado P tal que tanto P como su negación sean demostrables. "Recursivo" significa que existe un algoritmo que reconoce si un enunciado es, o no, un axioma. "Completo" es que para todo enunciado P, o bien él, o bien su negación, es demostrable.
Supongamos ahora que propongo como sistema de axiomas a todos los enunciados aritméticos verdaderos. No es difícil probar que este sistema es consistente y completo (ambas características se deducen del hecho de que todos los enunciados verdaderos, y sólo los verdaderos, resultan ser demostrables). Por el teorema de Gödel, entonces, el sistema no puede ser recursivo. En otras palabras, no existe un algoritmo que permita decidir si un enunciado es, o no, un axioma; es decir: no existe un algoritmo que permita decidir si un enunciado aritmético es, o no, verdadero. El problema de determinar la verdad de un enunciado aritmético no es resoluble algorítmicamente.
Ahora bien, si Gödel demostró su teorema en 1931 y el trabajo de Turing es de 1937 ¿por qué se le atribuye a Turing el descubrimiento? Porque en su artículo Gödel propone una definición posible de la idea de algoritmo "aritmético", pero reconoce que no está claro que su definición abarque todos los algoritmos posibles (de hecho, según se vio después, no los abarca). El gran mérito de Turing fue el haber dado una definición (una "modelización matemática", según la idea de la entrada anterior) de la idea de algoritmo lo suficientemente amplia como para abarcar (hasta donde se sabe) a todos los algoritmos posible. Es por eso que, recién después del trabajo de Turing pudo darse por demostrado la existencia de problemas no resolubles algorítmicamente; y fue asimismo después del trabajo de Turing (según Gödel reconoció en una posdata a su artículo) que pudo establecerse el alcance real del teorema de Gödel.
Un último comentario: así como la definición que dio Gödel para la idea de algoritmo resultó ser insuficiente, en el sentido de que hay algoritmos que la definición de Gödel no abarca, del mismo modo nada asegura que no haya algoritmos que queden "fuera" de la definición de Turing, aunque hasta el día de hoy nadie ha sido capaz de dar ni siquiera la insinuación de un ejemplo concreto.
