¿Por qué un algoritmo no puede entender la incompletitud?

Sobre el teorema de incompletitud de Gödel, primero debemos entender con razonable precisión lo que establece; ver Torkel Franzén, el teorema de Gödel Una guía incompleta para su uso y abuso (2005):

Primer teorema de incompletitud (Gödel-Rosser) . Cualquier sistema formal consistente S dentro del cual pueda llevarse a cabo una cierta cantidad de aritmética elemental es incompleto con respecto a los enunciados de la aritmética elemental: hay tales enunciados que no pueden ser probados ni refutados en S.

Los conceptos clave son: sistema formal , consistencia y "cierta cantidad de aritmética elemental".

Sobre el primero:

En las formulaciones populares del teorema de Gödel, una condición de este tipo (en lo que se refiere a los axiomas) [sobre la "mecanizabilidad del razonamiento en un sistema formal] se incluye a veces en forma de estipulación de que los axiomas de un sistema formal son finito en número. Esto implica que un axioma puede ("en principio") ser reconocido como tal mirando a través de una tabla finita. Pero esta condición no es satisfecha por muchos de los sistemas formales estudiados en lógica, como PA y ZF. Estos sistemas tienen un número infinito de axiomas, pero aún es una cuestión mecánica verificar si una oración en particular es o no un axioma.

Sobre "cierta cantidad de aritmética elemental", se puede precisar esta idea; apenas :

Cualquier sistema cuyo lenguaje incluya el lenguaje de la aritmética elemental, y cuyos teoremas incluyan algunos hechos básicos sobre los números naturales, es ciertamente uno que satisface la condición.

Lo que prueba el teorema es que, bajo los supuestos anteriores, podemos construir "efectivamente" una fórmula G en el lenguaje del sistema formal S (es decir, una fórmula "hecha de" números y operaciones sobre ellos, es decir, + y x) tales que ni la fórmula anterior es demostrable en el sistema (es decir, derivable con las reglas habituales de inferencia a partir de los axiomas del sistema), ni su negación no-G.

Esta fórmula "extraña" está fabricada de tal manera que su "interpretación" es un enunciado verdadero, porque la fórmula "dice por sí misma" que es indemostrable, y es realmente indemostrable; por lo tanto, si el sistema funciona como queremos, la fórmula debe ser verdadera.

Y qué ? Gödel no "hizo un cálculo" que nuestros algoritmos no puedan realizar. Hizo una prueba matemática, con la técnica habitual de las matemáticas: perspicacia y razonamiento.

Lo que implica su teorema, sobre el tema que estamos discutiendo, es que la capacidad de la lógica matemática de "reproducir" en un solo sistema formal S trabajando algorítmicamente el razonamiento habitual que la mente matemática (es decir, humana) es capaz de realizar no puede "comprimirse". en un solo sistema formal.

Para formalizar la construcción de la prueba de Gödel en un sistema formal, tenemos que construir un nuevo (más potente) sistema S'; pero entonces, podemos reproducir la construcción de la fórmula anterior produciendo una nueva fórmula G' de S', y así sucesivamente.

¿Podemos concluir acerca de la inagotabilidad de nuestro conocimiento matemático? Así parece [ver Franzén, página 56].

El teorema de incompletitud de Gödel a menudo se malinterpreta gravemente cuando se discute el tema de la inteligencia y la inteligencia artificial.

Su teorema establece que hay enunciados matemáticos que no se pueden probar ni refutar. Una computadora que busque una prueba no la encontrará. Una computadora que busca una prueba y no se da por vencida se quedaría atascada. Pero un matemático brillante que busca una demostración tampoco la encontrará. Y si ese matemático no se daba por vencido, él o ella también estaría atrapado para siempre.

Encontró que son problemas que son imposibles de resolver para cualquier computadora. Sin embargo, los mismos problemas son imposibles de resolver para un ser humano. Algunas personas parecen pensar que un problema irresoluble causaría problemas a una inteligencia artificial. Pero seguramente cualquier inteligencia artificial que valga ese nombre sería capaz de darse cuenta de que un problema es difícil, demasiado difícil de resolver, y luego, como harían los humanos, el único recurso es darse por vencido.

Tienes razón, esa no es la mejor expresión del resultado de Gödel. Su resultado es que no existe una teoría de la aritmética finitamente axiomatizable. Para desglosar algunos (pero no todos, porque desempaquetar todo nos hará estar aquí un tiempo y no tengo un Snickers), una "teoría de la aritmética" es cualquier conjunto de oraciones involucradas por un lenguaje de primer orden junto con un conjunto de axiomas no lógicos que implican exactamente las verdaderas igualdades aritméticas. Una teoría de la aritmética "finitamente axiomatizable" es cualquier teoría de la aritmética para la cual el conjunto de axiomas no lógicos es de tamaño finito.

Si tuviera que ponerlo en mi propia expresión, lo más cercana posible al lenguaje natural, diría: "Si a una computadora se le diera un programa diseñado para producir todas y solo las verdaderas igualdades aritméticas, no habría habrá siempre alguna verdadera igualdad que sistemáticamente se perderá".