La idea clave del teorema de Gödel puede ser explicada con la ayuda de un relato. En un país lejano un grupo de matemáticos que no habían sentido nunca hablar de Gödel se convenció de que existía de veras un procedimiento sistemático para determinar infaliblemente la verdad o falsedad de cualquier proposición sensata, y se propuso demostrarlo. Su procedimiento podía ser ejecutado por una persona, o por un grupo de personas, o por una máquina, o por cualquier combinación de estas tres posibilidades. Nadie sabía con certeza qué combinación hubieran elegido los matemáticos, porque el sistema estaba situado en un gran edificio universitario, bastante parecido a un templo, y la entrada estaba prohibida al público. En todo caso, el sistema viene llamado Tom. Para controlar la habilidad de Tom le venían sometidas complejas aserciones lógicas y matemáticas de todo tipo y, después del tiempo necesario para la elaboración, llegaron puntualmente las respuestas: verdadero, verdadero, falso, verdadero, falso…. No mucho después la fama de Tom se difundió en todo el país. Muchos venían a visitar el laboratorio y aguzaban siempre más el ingenio para formular problemas cada vez más difíciles en la tentativa de poner en dificultad el sistema. Nadie lo logró. La confianza de los matemáticos en la infalibilidad de Tom creció tanto que persuadieron a sus reyes a ofrecer un premio a quienquiera que lograra derrotar su increíble poder analítico. Un día, un viajero que venía de otro país llegó a la universidad con un sobre e pide desafiar a Tom. En el sobre había un pedazo de papel con una proposición para hacerle. La proposición, que podemos indicar con «P» («P» está por «proposición» o por «paradoja»), decía sencillamente: «Tom no puede demostrar que esta proposición es verdadera».
P viene propuesta a Tom. Habían pasado a penas pocos segundos cuando el sistema entró en una especie de convulsión. Después de medio minuto un técnico llegó corriendo del laboratorio con la noticia de que Tom había sido desactivado a causa de problemas técnicos. ¿Qué había ocurrido? Suponemos que Tom tuviera que llegar a la conclusión de que P es verdadero. Esto significaría que la proposición «Tom no puede demostrar que esta proposición es verdadera» habría sido falsificada. Pero si P es falsificada, no puede ser verdadera. Así si Tom contesta «verdadero» a P, habrá alcanzado una conclusión falsa, contradiciendo su ostentada infalibilidad. Entonces Tom no puede contestar «verdadero». Hemos llegado entonces a la conclusión de que P es efectivamente verdadero. Pero al llegar a esta conclusión hemos demostrado que Tom no puede llegar a esta conclusión. Eso significa que nosotros conocemos la verdad de una proposición que Tom no puede demostrar. Ésta es la esencia de la demostración de Gödel: que siempre babrá algunas proposiciones verdaderas que no pueden ser demostradas. El viajero, naturalmente, lo sabía y no tuvo alguna dificultad para construir P y ganar el premio.
Es importante, sin embargo, darse cuenta del hecho de que las limitaciones destacadas por el teorema de Gödel conciernen al mismo método axiomático de demostración lógica y no a una propiedad de las proposiciones que se trata de demostrar (o de refutar). Siempre se puede transformar una proposición verdadera que es indemostrable dentro de un dado sistema de axiomas en un axioma de cualquier sistema extenso. Pero entonces habrá otras proposiciones indemostrables en este sistema extenso, etc.
El teorema de Gödel fue una desoladora parada para el programa formalista, pero la idea de un procedimiento mecánico para indagar las proposiciones matemáticas no fue abandonada completamente. ¿Quizás las proposiciones indecidibles sólo son extrañezas que pueden ser eliminadas por la lógica y por las matemáticas? Si se encontrara un modo para distinguir las proposiciones decidibles de aquellas indecidibles, entonces determinar si una proposición cualquiera perteneciente al primer grupo sea verdadera o falsa incluso podría ser siempre factible. ¿Pero es posible formular un procedimiento sistemático para reconocer de modo infalible las proposiciones indecidibles y eliminarlas? El desafío fue aceptado por Alonzo Church, un colaborador de von Neumann en Princeton, el cual demostró pronto que incluso esta meta más modesta era inalcanzable, al menos en un número determinado de pasos. En otras palabras: se podrían hacer aserciones matemáticas potencialmente verdaderas o falsas, y se podría emprender un procedimiento sistemático para controlar su verdad o falsedad, pero este procedimiento no tendría nunca final: el resultado no podría ser nunca conocido.
