Gödel, Alan Turing y el fin del sueño de Hilbert: los límites ocultos de las matemáticas, la lógica y la computación:
"Historia de las matemáticas · Lógica matemática · Computación teórica · Filosofía de la ciencia"
¿Es posible demostrar todas las verdades matemáticas? ¿Existe un algoritmo capaz de resolver cualquier problema? ¿Puede un sistema lógico comprender completamente su propia estructura?
Durante siglos, las matemáticas representaron uno de los mayores símbolos de certeza del pensamiento humano. Se consideraba que, mediante axiomas, reglas lógicas y demostraciones rigurosas, era posible construir un edificio de conocimiento capaz de proporcionar respuestas definitivas a cualquier cuestión matemática bien formulada.
Sin embargo, durante el siglo XX, tres figuras revolucionaron profundamente esta concepción: David Hilbert, Kurt Gödel y Alan Turing.
Sus ideas protagonizaron uno de los acontecimientos intelectuales más importantes de la historia de la ciencia: el descubrimiento de que existen límites fundamentales en lo que podemos demostrar, calcular y decidir mediante procedimientos matemáticos.
Lo verdaderamente fascinante es que estos límites no surgieron por falta de inteligencia, tecnología o conocimientos. Son limitaciones matemáticas demostrables que aparecen incluso cuando disponemos de sistemas lógicos perfectamente definidos.
Los teoremas de incompletitud de Gödel y el problema de la parada de Turing transformaron nuestra comprensión de las matemáticas y sentaron algunas de las bases conceptuales de la informática moderna, la inteligencia artificial, la teoría de la computabilidad y la filosofía de la mente.
Para comprender la profundidad de este descubrimiento, debemos regresar a una época en la que los matemáticos soñaban con encontrar un fundamento definitivo para todo el conocimiento matemático.
David Hilbert y el ambicioso sueño de encontrar una matemática perfecta
A comienzos del siglo XX, las matemáticas atravesaban un momento extraordinario. Habían conseguido desarrollar teorías cada vez más sofisticadas, pero también estaban apareciendo dificultades relacionadas con sus propios fundamentos.
La aparición de paradojas en la teoría de conjuntos, las discusiones sobre la naturaleza del infinito y las contradicciones potenciales de determinados sistemas matemáticos provocaron una pregunta fundamental:
¿Cómo podemos estar seguros de que las matemáticas nunca conducirán a una contradicción?
Uno de los matemáticos que más profundamente se preocupó por esta cuestión fue David Hilbert (1862-1943).
Hilbert no pretendía simplemente resolver problemas matemáticos difíciles. Su ambición era mucho mayor: quería proporcionar a todas las matemáticas una estructura lógica rigurosa que permitiera estudiar sus fundamentos de manera completamente controlada.
Su proyecto recibió el nombre de programa de Hilbert.
¿En qué consistía el programa de Hilbert?
La propuesta se apoyaba en tres grandes objetivos.
Formalizar las matemáticas.
Hilbert quería expresar las teorías matemáticas mediante lenguajes formales, axiomas y reglas de inferencia perfectamente especificadas.
En lugar de depender de intuiciones personales, cada demostración debía poder verificarse mediante reglas explícitas.
Demostrar la consistencia de los sistemas matemáticos.
La consistencia significa que un sistema no permite demostrar simultáneamente una proposición y su negación.
Por ejemplo, si un sistema matemático pudiera demostrar que una afirmación es verdadera y también que es falsa, habría perdido su capacidad de servir como fundamento fiable.
Hilbert quería demostrar que los sistemas matemáticos fundamentales eran consistentes utilizando métodos finitistas, es decir, razonamientos matemáticos que consideraba especialmente seguros y concretos.
Estudiar la completitud y la decidibilidad.
También existía la ambición de determinar si las afirmaciones matemáticas podían resolverse sistemáticamente mediante procedimientos formales.
Aquí aparecen dos conceptos esenciales:
Completitud: un sistema demuestra todas las proposiciones expresables en su lenguaje o, en el contexto de la lógica clásica, demuestra cada oración o su negación.
Decidibilidad: existe un procedimiento efectivo que permite determinar, en un número finito de pasos, si una proposición pertenece a la clase que queremos decidir.
Estos conceptos están relacionados, pero no significan lo mismo.
Un sistema puede ser completo sin que exista un algoritmo general para decidir todas sus verdades, dependiendo del tipo de sistema considerado.
La ambición de Hilbert era construir unos fundamentos matemáticos cuya fiabilidad pudiera justificarse rigurosamente.
Sin embargo, el desarrollo posterior de la lógica demostraría que había obstáculos mucho más profundos de lo que inicialmente parecía.
Puedes profundizar en el contexto histórico y matemático del proyecto en la investigación de Stanford Encyclopedia of Philosophy sobre el programa de Hilbert .
Kurt Gödel: el matemático que descubrió límites dentro de la propia lógica
En 1931, un joven matemático austríaco llamado Kurt Gödel publicó uno de los trabajos más revolucionarios de la historia de las matemáticas:
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme.
En español, el título puede traducirse como Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas afines.
Su investigación contenía una demostración extraordinaria: determinados sistemas matemáticos suficientemente expresivos no podían ser simultáneamente consistentes, efectivamente axiomatizados y completos.
Esto significaba que, incluso cuando se dispone de reglas lógicas rigurosas y axiomas perfectamente definidos, pueden existir afirmaciones que el propio sistema no consigue demostrar ni refutar.
Pero ¿cómo llegó Gödel a semejante conclusión?
El primer teorema de incompletitud: existen límites en la demostración matemática
El primer teorema de incompletitud establece, en términos generales, que:
En cualquier sistema formal consistente, efectivamente axiomatizado y suficientemente potente para expresar una parte adecuada de la aritmética, existen proposiciones que no pueden demostrarse ni refutarse dentro de ese mismo sistema.
Una de las condiciones técnicas importantes es que el sistema pueda representar suficiente aritmética elemental. No se trata de una limitación de cualquier sistema lógico imaginable.
La idea es mucho más profunda de lo que parece.
Imaginemos un sistema matemático que contiene:
Un conjunto de axiomas.
Reglas para obtener nuevas afirmaciones.
Un lenguaje formal.
Un mecanismo para verificar si una demostración es correcta.
Podríamos pensar que, si el sistema está suficientemente bien diseñado, tarde o temprano podremos demostrar todas las afirmaciones verdaderas.
Gödel demostró que esa expectativa no puede cumplirse bajo las condiciones de su teorema.
Siempre existirán proposiciones que escapen a la capacidad demostrativa del sistema.
La idea extraordinaria: una proposición que habla de su propia demostrabilidad
La genialidad de Gödel consistió en encontrar una manera de representar afirmaciones sobre demostraciones matemáticas utilizando números.
Este procedimiento se conoce como numeración de Gödel.
Su funcionamiento conceptual es el siguiente:
Cada símbolo matemático recibe una codificación numérica.
Las expresiones matemáticas completas se convierten en secuencias de números.
Las demostraciones también pueden representarse mediante números.
Las propiedades de esas demostraciones pueden expresarse mediante relaciones aritméticas.
De esta manera, las matemáticas pueden comenzar a hablar de sus propias demostraciones.
Esto constituye una transformación intelectual extraordinaria: un sistema aritmético puede representar afirmaciones sobre su propia estructura formal.
A partir de esta posibilidad, Gödel construyó una proposición autorreferencial cuyo significado intuitivo puede expresarse así:
«Esta proposición no puede demostrarse dentro de este sistema».
La afirmación no es una simple paradoja lingüística. Está construida mediante una codificación matemática rigurosa.
Si el sistema pudiera demostrarla, bajo las condiciones apropiadas se produciría una contradicción con su consistencia.
Y si el sistema pudiera demostrar su negación, también aparecerían problemas de consistencia, bajo las condiciones correspondientes.
Por tanto, la proposición queda fuera de la capacidad demostrativa del sistema.
¿Significa que existen verdades matemáticas imposibles de demostrar?
Aquí debemos introducir una precisión fundamental.
El teorema de Gödel no afirma que una proposición sea absolutamente indemostrable en todos los sistemas matemáticos.
Afirma que existen proposiciones que no pueden demostrarse dentro de un sistema formal determinado, siempre que se cumplan las condiciones del teorema.
Podemos imaginar que tenemos un sistema matemático llamado A.
Este sistema no puede demostrar una determinada proposición G.
Sin embargo, podríamos construir un sistema B incorporando G como un nuevo axioma.
Ahora G sí podría demostrarse en B.
Pero esto no significa que hayamos eliminado el problema: el nuevo sistema también puede tener sus propias limitaciones de incompletitud si cumple las condiciones de Gödel.
Es decir, ampliar un sistema puede permitir demostrar nuevas proposiciones, pero no proporciona una solución universal al problema de la completitud.
La frontera de lo demostrable puede desplazarse, pero no desaparecer mediante una simple ampliación de los axiomas.
Hay otro matiz importante: la versión original del primer teorema utilizaba condiciones técnicas de consistencia más fuertes; la formulación generalizada de Rosser permitió establecer la indecidibilidad de una proposición bajo una hipótesis ordinaria de consistencia.
En las formulaciones habituales, la proposición construida puede ser verdadera en la interpretación estándar de los números naturales, aunque no demostrable en el sistema considerado.
Por tanto, no debemos confundir independencia formal con ausencia de valor de verdad.
El segundo teorema de incompletitud: un sistema no puede justificar completamente su propia consistencia
Si el primer teorema ya era sorprendente, el segundo profundizó todavía más el problema.
El segundo teorema de incompletitud establece, de manera simplificada, que:
Un sistema formal consistente, suficientemente potente y que satisface determinadas condiciones técnicas no puede demostrar mediante sus propios recursos formalizados su propia consistencia.
Pensemos en un sistema matemático que pretende garantizar que nunca producirá contradicciones.
Podría intentar demostrar una afirmación que diga:
«No existe ninguna demostración de una contradicción dentro de este sistema».
Sin embargo, el segundo teorema establece que, bajo sus condiciones, el propio sistema no puede proporcionar esa demostración de consistencia.
Esto no significa que nadie pueda demostrar su consistencia desde fuera.
Significa que no puede hacerlo utilizando una formalización interna adecuada de sus propios recursos, tal como exige el teorema.
Por ejemplo, podemos estudiar un sistema desde una teoría matemática más potente. Pero entonces surge otra pregunta: ¿qué justifica la consistencia de esa teoría más potente?
El problema adquiere una dimensión filosófica fascinante.
La justificación de un sistema puede requerir recursos externos al propio sistema.
Así, Gödel puso de manifiesto una limitación fundamental en la aspiración de construir una fundamentación matemática absolutamente autosuficiente.
Para comprender los matices técnicos de ambos resultados, resulta especialmente valiosa la exposición académica de los teoremas de incompletitud de Gödel .
Alan Turing: cuando las matemáticas descubrieron que no todo puede calcularse
Si Gödel transformó nuestra comprensión de lo demostrable, Alan Turing revolucionó nuestra comprensión de lo calculable.
Turing fue un matemático británico cuya investigación permitió establecer fundamentos teóricos para la computación moderna.
En 1936 publicó un trabajo fundamental titulado On Computable Numbers, with an Application to the Entscheidungsproblem.
En esta investigación introdujo un modelo abstracto que hoy conocemos como máquina de Turing.
Su propósito no era construir una computadora física. Quería estudiar matemáticamente qué significa ejecutar un procedimiento mecánico.
¿Qué es una máquina de Turing?
Una máquina de Turing es un modelo matemático abstracto capaz de representar un procedimiento de cálculo.
Podemos imaginarla como un dispositivo que dispone de:
Una cinta dividida en casillas.
Un conjunto de símbolos que puede leer y escribir.
Un cabezal que se desplaza por la cinta.
Un conjunto finito de estados internos.
Unas reglas que determinan qué hacer en cada situación.
La máquina recibe información, aplica instrucciones y modifica su estado siguiendo reglas precisas.
Aunque este modelo parece sencillo, su importancia es enorme.
Una máquina de Turing permite representar cualquier procedimiento algorítmico que pueda ejecutarse mediante un método mecánico efectivo, de acuerdo con la tesis de Church-Turing.
Esto permitió transformar una pregunta filosófica en una cuestión matemática:
¿Qué problemas pueden resolverse mediante un algoritmo y cuáles están fuera de los límites de cualquier procedimiento computacional efectivo?
La máquina de Turing no solo ayudó a definir qué significa computar. También permitió demostrar que existen problemas que ninguna computadora algorítmica general puede resolver.
El problema de la parada: ¿podemos saber si cualquier programa terminará?
Uno de los resultados más famosos de Turing es el problema de la parada, conocido internacionalmente como Halting Problem.
La pregunta parece muy sencilla:
Si proporcionamos un programa y una entrada determinada, ¿podemos construir un algoritmo universal que determine siempre si ese programa terminará o continuará ejecutándose indefinidamente?
Por ejemplo, imaginemos dos programas.
Programa A:
python
numero = 10
while numero > 0:
print(numero)
numero -= 1
Este programa termina después de ejecutar un número finito de iteraciones.
Programa B:
python
while True:
print("Sigo ejecutándome")
Este programa no termina por sí mismo.
En estos dos ejemplos podemos identificar fácilmente el comportamiento.
Pero ahora imaginemos un programa extraordinariamente complejo que contiene miles de instrucciones, operaciones matemáticas, condiciones y procedimientos que dependen de sus entradas.
¿Podemos construir un algoritmo que determine correctamente, para cualquier programa posible y cualquier entrada, si terminará o no?
Turing demostró que la respuesta es negativa.
No existe un algoritmo general que resuelva correctamente todos los casos del problema de la parada.
La demostración conceptual: la autorreferencia vuelve a aparecer
El razonamiento de Turing guarda una relación profunda con la estrategia utilizada por Gödel.
Supongamos que existe un programa universal capaz de analizar cualquier otro programa y determinar si se detendrá.
Podemos imaginar que este programa funciona como un evaluador perfecto:
Si predice que el programa terminará, responde «se detendrá».
Si predice que no terminará, responde «no se detendrá».
Ahora imaginemos que construimos un programa especial que hace exactamente lo contrario de lo que predice ese evaluador cuando analiza su propio código.
Es decir:
Si el evaluador predice que terminará, el programa entra en un bucle infinito.
Si el evaluador predice que no terminará, el programa termina.
¿Qué sucede cuando el evaluador intenta analizar ese programa consigo mismo como entrada?
Aparece una contradicción.
Si predice que termina, no termina.
Si predice que no termina, sí termina.
Por tanto, la existencia de ese evaluador universal produciría una contradicción.
La conclusión es inevitable: no puede existir un algoritmo que resuelva todos los casos del problema de la parada.
Esta demostración constituye uno de los ejemplos más elegantes de cómo la autorreferencia puede revelar límites fundamentales en los sistemas formales y computacionales.
Es importante distinguirlo de una paradoja lógica convencional: no estamos ante un simple juego de palabras, sino ante una demostración matemática de indecidibilidad.
Gödel y Turing: dos descubrimientos diferentes que revelaron una misma frontera
A primera vista, los trabajos de Gödel y Turing parecen pertenecer a disciplinas diferentes.
Gödel estudiaba la lógica matemática, los axiomas y las demostraciones.
Turing investigaba los procedimientos mecánicos, los algoritmos y la computabilidad.
Sin embargo, sus investigaciones terminaron revelando una conexión extraordinaria.
Ambos demostraron que existen límites inherentes a los procedimientos formales.
Para comprenderlo, debemos distinguir dos preguntas:
Gödel: ¿podemos demostrar todas las afirmaciones matemáticas relevantes mediante un sistema formal determinado?
Turing: ¿podemos decidir mediante un algoritmo cualquier problema computacional bien definido?
Las respuestas generales son negativas.
La conexión mediante la autorreferencia
Uno de los elementos más interesantes de ambos descubrimientos es la utilización de estructuras autorreferenciales.
En Gödel, una proposición matemática se construye para expresar, de manera codificada, algo sobre su propia demostrabilidad.
En Turing, se construye un procedimiento computacional cuyo comportamiento contradice la predicción de un supuesto algoritmo universal.
En ambos casos, el razonamiento utiliza una estrategia relacionada con la diagonalización.
Esta técnica tiene antecedentes en los trabajos de Georg Cantor sobre la naturaleza del infinito.
Cantor demostró que existen conjuntos infinitos de distintos tamaños y que los números reales no pueden enumerarse mediante una correspondencia completa con los números naturales.
Gödel y Turing aprovecharon ideas relacionadas con la diagonalización para demostrar que determinados sistemas no pueden abarcar todas las posibilidades que intentan describir.
Es una conexión conceptual extraordinaria:
Cantor reveló límites en la enumeración de conjuntos infinitos.
Gödel reveló límites en la demostrabilidad formal.
Turing reveló límites en la computabilidad algorítmica.
Los tres resultados transformaron nuestra comprensión de las fronteras del conocimiento matemático.
La diferencia fundamental entre demostrar y calcular
Aquí aparece una distinción que suele pasar desapercibida.
No es exactamente lo mismo que una proposición no pueda demostrarse dentro de un sistema que afirmar que un problema no puede resolverse mediante un algoritmo.
Consideremos estos dos escenarios:
Estudia sistemas de axiomas y demostraciones.
Estudia máquinas y procedimientos computacionales.
Investiga la incompletitud formal.
Investiga la indecidibilidad algorítmica.
Construye proposiciones independientes de un sistema.
Demuestra que ciertos problemas no admiten algoritmos generales de decisión.
Su resultado depende de las propiedades del sistema formal.
Su resultado establece límites de los procedimientos computables.
La diferencia es importante porque una afirmación puede ser demostrable en un sistema más potente aunque no lo sea en otro.
En cambio, el problema de la parada establece que no existe un procedimiento algorítmico universal que resuelva todos sus casos.
¿Cómo se relacionan matemáticamente los dos descubrimientos?
La conexión no es solamente filosófica.
Las máquinas de Turing pueden representar demostraciones matemáticas, y los sistemas formales efectivos permiten enumerar sus demostraciones.
Imaginemos que tenemos un sistema formal cuyos axiomas y reglas pueden verificarse mecánicamente.
Podemos construir un procedimiento que examine las posibles demostraciones y busque una prueba de una proposición determinada.
Si encuentra la demostración, termina y responde afirmativamente.
Sin embargo, si la proposición no es demostrable, el procedimiento puede continuar buscando indefinidamente.
Esto significa que podemos reconocer mecánicamente determinados casos positivos sin necesariamente disponer de un procedimiento que determine siempre la respuesta.
Esta diferencia se expresa mediante dos conceptos:
Decidibilidad: podemos determinar siempre si una afirmación pertenece o no a una determinada clase.
Enumerabilidad computable: podemos generar o reconocer todos los elementos de una clase mediante un procedimiento efectivo, aunque no necesariamente podamos reconocer cuándo un elemento no pertenece a ella.
La distinción es esencial para comprender la computación teórica.
Los resultados de Gödel y Turing demostraron que no debemos confundir la posibilidad de encontrar una demostración con la posibilidad de decidir universalmente si existe.
El Entscheidungsproblem: la pregunta que conectó a Hilbert, Gödel y Turing
Para entender completamente la importancia histórica de estos descubrimientos debemos conocer un problema que desempeñó un papel central en el desarrollo de la lógica matemática.
Se trata del Entscheidungsproblem, expresión alemana que significa problema de decisión.
La cuestión consistía en determinar si existía un procedimiento mecánico general que permitiera decidir, para cualquier fórmula de la lógica de primer orden, si era lógicamente válida.
La pregunta estaba directamente relacionada con las aspiraciones de Hilbert y su colaborador Wilhelm Ackermann.
En 1928, Hilbert y Ackermann publicaron una obra fundamental sobre los principios de la lógica teórica, donde se planteaba el problema de encontrar un procedimiento general de decisión.
La pregunta parecía razonable:
Si disponemos de un lenguaje lógico perfectamente definido y de reglas formales, ¿por qué no podríamos construir un procedimiento que determinara la validez de cualquier expresión?
En 1936 llegaron dos respuestas negativas fundamentales.
Por un lado, Alonzo Church demostró la indecidibilidad del problema mediante el cálculo lambda.
Por otro, Turing presentó su modelo de máquina abstracta y demostró que tampoco existía un procedimiento general de decisión.
Estos trabajos fueron fundamentales para establecer los límites de la lógica matemática.
Una precisión histórica importante: el problema de decisión de la lógica de primer orden no es idéntico al problema de la parada, aunque Turing utilizó la indecidibilidad de la parada para demostrar un resultado relacionado con el problema de decisión.
De esta manera, el programa intelectual de Hilbert se encontró con dos obstáculos decisivos:
Gödel había demostrado que ciertos sistemas matemáticos no podían ser completos.
Church y Turing habían demostrado que no existía un procedimiento mecánico universal para resolver el problema general de decisión lógica.
Puedes consultar los detalles históricos en el estudio de Stanford sobre el ascenso y caída del Entscheidungsproblem .
¿Gödel y Turing destruyeron realmente el programa de Hilbert?
Esta pregunta requiere una respuesta más cuidadosa de lo que suele encontrarse en las explicaciones populares.
Es habitual afirmar que Gödel y Turing destruyeron completamente el programa de Hilbert.
Sin embargo, esa descripción simplifica demasiado el problema.
El programa de Hilbert tenía diferentes objetivos, y no todos quedaron refutados de la misma manera.
Lo que Gödel demostró que no era posible
Gödel estableció que no podía existir un sistema formal consistente, efectivamente axiomatizado y suficientemente potente para la aritmética que fuera completo en el sentido relevante.
Esto golpeaba directamente la aspiración de capturar todas las verdades aritméticas mediante un único sistema formal de esas características.
Su segundo teorema también establecía que determinados sistemas no podían demostrar formalmente su propia consistencia mediante sus propios recursos.
Esto afectaba especialmente al objetivo de justificar los fundamentos de las matemáticas mediante pruebas de consistencia formalizadas dentro de los propios sistemas.
Lo que Turing demostró que no era posible
Turing mostró que no existía un procedimiento mecánico general capaz de decidir todas las cuestiones del Entscheidungsproblem.
Esto significaba que no podíamos convertir toda la lógica matemática en una máquina universal de respuestas definitivas.
La idea de encontrar un algoritmo que resolviera automáticamente cualquier problema lógico de esa clase había encontrado una frontera matemática insuperable.
Lo que sobrevivió del programa de Hilbert
Sin embargo, Hilbert no estaba equivocado en todo.
La formalización matemática continuó desarrollándose.
La teoría de la demostración se convirtió en una disciplina extraordinariamente importante.
Se consiguieron demostrar resultados de consistencia para determinados sistemas utilizando métodos que no estaban disponibles dentro de esos mismos sistemas.
Un ejemplo destacado es el trabajo de Gerhard Gentzen, quien en 1936 presentó una demostración de consistencia para la aritmética de Peano utilizando inducción transfinita hasta el ordinal
Este resultado no contradice el segundo teorema de Gödel porque utiliza recursos que no pueden formalizarse dentro de la aritmética de Peano de la manera requerida para obtener una demostración interna de su propia consistencia.
Por tanto, la historia no consiste en que Hilbert desapareciera intelectualmente después de Gödel y Turing.
Lo que ocurrió fue una transformación de los objetivos y métodos de la investigación matemática.
La teoría de la demostración, la lógica matemática y el estudio de los fundamentos continuaron avanzando.
La propia investigación de Stanford sobre Gödel y el programa de Hilbert explica por qué el impacto de los teoremas requiere distinguir entre las diferentes metas originales del proyecto.
Las consecuencias de Gödel y Turing para la informática moderna
Una de las consecuencias más sorprendentes de estos descubrimientos es que sus implicaciones no se limitaron a la filosofía de las matemáticas.
La teoría de la computabilidad se convirtió en uno de los fundamentos conceptuales de la informática.
Actualmente, prácticamente todos los sistemas informáticos están relacionados con cuestiones que Turing ayudó a formalizar.
Los límites de los algoritmos
Un algoritmo es un conjunto definido de instrucciones que permite realizar una tarea mediante un procedimiento efectivo.
Los algoritmos permiten:
Ordenar grandes cantidades de información.
Realizar operaciones matemáticas.
Buscar información.
Analizar datos.
Procesar imágenes.
Ejecutar simulaciones.
Entrenar modelos de inteligencia artificial.
Sin embargo, no todos los problemas pueden convertirse en algoritmos que proporcionen una respuesta correcta para todos los casos.
El problema de la parada constituye la demostración más conocida de esta limitación.
No importa cuánta capacidad de procesamiento tenga una computadora: aumentar su velocidad no elimina una imposibilidad matemática.
Esto permite distinguir dos situaciones:
Problemas difíciles: pueden resolverse mediante algoritmos, pero quizá requieren cantidades extraordinarias de tiempo o memoria.
Problemas indecidibles: no existe un algoritmo general que resuelva correctamente todos los casos del problema.
Esta distinción es fundamental.
Un problema indecidible no es simplemente un problema que todavía no hemos conseguido resolver con suficiente potencia computacional.
Es un problema para el que se ha demostrado que el procedimiento general buscado no puede existir.
Las implicaciones para la verificación de software
En ingeniería informática, verificar que un programa cumple determinadas propiedades es una tarea esencial.
Por ejemplo:
¿Puede producir resultados incorrectos?
¿Puede entrar en un estado de ejecución infinito?
¿Puede acceder a una operación no permitida?
¿Puede bloquearse bajo determinadas condiciones?
¿Respeta siempre determinadas reglas?
Los métodos formales permiten demostrar propiedades de los programas mediante razonamientos matemáticos.
Pero los límites de la computabilidad indican que no podemos esperar construir un verificador automático perfecto que determine todas las propiedades semánticas posibles de cualquier programa.
Esto no significa que la verificación formal sea inútil.
Al contrario: es una de las herramientas más importantes para desarrollar sistemas fiables.
Significa que debemos definir cuidadosamente qué propiedades queremos verificar y bajo qué condiciones.
Las implicaciones para la inteligencia artificial
La relación entre Gödel, Turing y la inteligencia artificial es especialmente interesante.
La inteligencia artificial moderna utiliza algoritmos para reconocer patrones, generar información, realizar predicciones y resolver problemas.
Sin embargo, los teoremas de incompletitud y la indecidibilidad computacional establecen límites teóricos sobre lo que puede conseguir cualquier sistema algorítmico general.
Por ejemplo, una inteligencia artificial no puede disponer de un procedimiento universal que determine correctamente si cualquier programa arbitrario terminará.
Tampoco puede existir un sistema formal consistente y suficientemente potente que demuestre todas las verdades aritméticas mediante sus propios axiomas efectivos.
No obstante, debemos evitar una interpretación exagerada.
Los teoremas de Gödel no demuestran que la inteligencia humana sea superior a todas las máquinas.
Tampoco demuestran que una inteligencia artificial no pueda realizar razonamientos matemáticos sofisticados.
De hecho, los sistemas computacionales pueden descubrir demostraciones, verificar teoremas y explorar espacios matemáticos extraordinariamente complejos.
Lo que establecen estos resultados son límites concretos de los sistemas formales y los procedimientos computables.
La posibilidad de que la conciencia humana trascienda esos límites es una cuestión filosófica diferente, que no queda resuelta por los teoremas.
La dimensión filosófica: ¿existen límites al conocimiento humano?
Quizá la consecuencia más profunda de Gödel y Turing no sea tecnológica, sino filosófica.
Durante mucho tiempo, una parte importante del pensamiento científico estuvo influida por la idea de que el conocimiento podía organizarse en sistemas racionales completos.
La lógica proporcionaba reglas, las matemáticas ofrecían demostraciones y la ciencia buscaba explicaciones cada vez más generales.
Los descubrimientos de Gödel y Turing obligaron a reconsiderar esa visión.
La diferencia entre verdad y demostrabilidad
Una de las enseñanzas más importantes de Gödel es que la verdad matemática y la demostrabilidad formal no son conceptos idénticos.
Una proposición puede ser verdadera en una interpretación matemática y, sin embargo, no ser demostrable a partir de determinados axiomas.
Esto abre una cuestión fascinante:
¿La verdad matemática existe independientemente de nuestra capacidad para demostrarla?
Esta pregunta está relacionada con uno de los grandes debates de la filosofía de las matemáticas: el platonismo matemático.
Según una interpretación platonista, los objetos matemáticos y sus relaciones no dependen de que los seres humanos los descubran.
Desde esta perspectiva, las verdades matemáticas existen independientemente de nuestros sistemas formales.
Gödel simpatizaba con una posición realista de este tipo.
Sin embargo, sus teoremas no obligan a aceptar el platonismo. También pueden interpretarse desde otras perspectivas filosóficas.
Lo que sí establecen es que la demostrabilidad formal tiene límites precisos.
¿Podemos comprender algo que no podemos demostrar dentro de nuestro sistema?
Aquí aparece una de las preguntas más interesantes.
Si un sistema formal no puede demostrar una proposición determinada, ¿podemos comprender desde fuera por qué esa proposición es verdadera?
En ciertos casos, sí.
Podemos estudiar el sistema, analizar sus axiomas y utilizar razonamientos metamatemáticos para establecer propiedades que el propio sistema no puede demostrar.
Pero esos razonamientos también pueden formalizarse en otros sistemas, y estos últimos pueden presentar sus propias limitaciones.
Esto introduce la distinción entre:
Matemática interna: aquello que puede demostrarse utilizando los axiomas y reglas de un sistema.
Metamatemática: el estudio matemático de los sistemas formales, sus demostraciones y sus propiedades.
La metamatemática permite estudiar desde fuera aquello que un sistema no puede justificar internamente.
Esta distinción fue esencial para el desarrollo posterior de la lógica moderna.
El conocimiento matemático como una frontera que se desplaza
Una interpretación especialmente interesante de estos resultados es que el conocimiento matemático no se encuentra encerrado en una estructura definitiva.
Cuando incorporamos nuevos axiomas, podemos demostrar nuevas proposiciones.
Cuando desarrollamos nuevas técnicas de razonamiento, podemos abordar problemas que anteriormente parecían inaccesibles.
Pero cada ampliación suficientemente potente vuelve a enfrentarse a las limitaciones de los sistemas formales.
No significa que el conocimiento sea inútil o que todas las respuestas sean relativas.
Significa que no podemos identificar el conocimiento matemático completo con un único procedimiento formal capaz de resolver absolutamente todas las cuestiones.
La matemática sigue siendo rigurosa, pero su rigor no implica omnipotencia.
Cinco conceptos avanzados que permiten comprender la profundidad de estos descubrimientos
Para quienes quieran ir más allá de las explicaciones habituales, existen cinco conceptos especialmente importantes.
Diagonalización
La diagonalización es una técnica matemática que permite construir objetos que escapan a determinadas enumeraciones o clasificaciones.
Cantor la utilizó para demostrar que los números reales no son numerables.
Gödel la empleó en una construcción relacionada con la autorreferencia matemática.
Turing la utilizó para demostrar la indecidibilidad del problema de la parada.
Es una de las técnicas más poderosas de la lógica matemática.
Aritmetización de la sintaxis
Consiste en representar símbolos, fórmulas y demostraciones mediante números naturales.
Gracias a esta técnica, las propiedades sintácticas de un sistema formal pueden estudiarse mediante operaciones aritméticas.
Fue uno de los ingredientes fundamentales del primer teorema de incompletitud.
Indecidibilidad
Un problema es indecidible cuando no existe un algoritmo que pueda determinar correctamente la respuesta para todas las entradas posibles y terminar siempre.
La indecidibilidad no debe confundirse con la dificultad computacional.
Un problema puede ser extremadamente difícil y, aun así, decidible.
Tesis de Church-Turing
Esta tesis establece que la noción intuitiva de procedimiento efectivo o cálculo mecánico coincide con las funciones que pueden calcularse mediante los modelos formales equivalentes de computabilidad, como las máquinas de Turing y el cálculo lambda.
Es importante comprender que se trata de una tesis conceptual sobre la noción de computación efectiva, no de un teorema matemático que demuestre que todos los modelos imaginables de computación son equivalentes.
Jerarquía de sistemas formales
Los sistemas formales pueden compararse según su capacidad para demostrar proposiciones.
Un sistema más potente puede demostrar afirmaciones que otro más limitado no consigue demostrar.
Pero aumentar esa potencia no garantiza alcanzar una completitud absoluta.
Este concepto permite comprender por qué la incompletitud no desaparece simplemente añadiendo axiomas.
Gödel y Turing en la actualidad: por qué siguen siendo fundamentales
Más de nueve décadas después de los descubrimientos de Gödel, y casi un siglo después de los trabajos fundamentales de Turing, sus ideas continúan presentes en diferentes disciplinas.
Disciplina
Influencia de estos descubrimientos
Matemáticas
Estudio de axiomas, demostraciones e independencia de proposiciones.
Informática
Fundamentos de los algoritmos y límites de la computación.
Inteligencia artificial
Comprensión de las capacidades y limitaciones de los procedimientos algorítmicos.
Ciberseguridad
Límites de la verificación automática de determinadas propiedades de programas.
Filosofía
Diferencia entre verdad, conocimiento y demostrabilidad.
Lógica
Desarrollo de sistemas formales y teorías de la demostración.
Teoría de la computación
Clasificación de problemas decidibles e indecidibles.
Uno de los aspectos más importantes es que estos resultados no son descubrimientos históricos que hayan quedado superados por las computadoras modernas.
Son resultados matemáticos que continúan siendo válidos.
Una computadora más rápida puede resolver problemas que antes eran prácticamente inaccesibles.
Una inteligencia artificial más avanzada puede descubrir demostraciones que ningún matemático había encontrado.
Pero ninguna mejora tecnológica elimina por sí misma los límites matemáticos establecidos por Gödel y Turing.
Esta es una de las diferencias fundamentales entre los límites prácticos y los límites teóricos.
Un límite práctico puede desaparecer cuando mejoran nuestros recursos.
Un límite matemático demostrado no desaparece simplemente porque aumente nuestra capacidad tecnológica.
Conclusión: cuando las matemáticas descubrieron sus propios límites
La historia de Hilbert, Gödel y Turing representa uno de los episodios intelectuales más extraordinarios de la civilización científica.
Hilbert buscaba construir unos fundamentos matemáticos rigurosos, capaces de garantizar la seguridad de las demostraciones y proporcionar métodos generales para estudiar los problemas matemáticos.
Gödel demostró que los sistemas formales suficientemente potentes no pueden capturar todas las verdades aritméticas mediante demostraciones internas.
Turing demostró que existen problemas computacionales para los cuales no puede existir un algoritmo universal de decisión.
Sus investigaciones transformaron profundamente nuestra comprensión de las matemáticas.
Pero la verdadera enseñanza no consiste en que las matemáticas hayan fracasado.
Al contrario.
El mayor logro de estos descubrimientos fue demostrar matemáticamente que existen límites a lo que puede demostrarse y calcularse.
Las matemáticas consiguieron algo extraordinario: utilizar su propio rigor para descubrir que ningún sistema formal adecuado puede contener todas las verdades matemáticas dentro de sus propias reglas.
Esta paradoja aparente representa una de las mayores conquistas del pensamiento humano.
Nos enseña que la certeza matemática no implica que todo sea demostrable, que la computación no significa que todo sea calculable y que disponer de reglas perfectas no garantiza resolver cualquier problema.
Quizá la lección más profunda sea esta:
El conocimiento no pierde su valor porque tenga límites. Comprender esos límites es, precisamente, una de las formas más elevadas de conocimiento.
Preguntas frecuentes sobre Gödel, Turing y Hilbert
¿Qué demostraron los teoremas de incompletitud de Gödel?
Demostraron que los sistemas formales consistentes, efectivamente axiomatizados y suficientemente potentes para expresar aritmética no pueden demostrar todas las proposiciones de su lenguaje ni decidirlas todas mediante sus propios recursos.
¿Qué es el problema de la parada de Turing?
Es el problema de determinar si un programa informático, dada una entrada, terminará su ejecución o continuará indefinidamente. Turing demostró que no existe un algoritmo general capaz de resolver correctamente todos los casos.
¿Qué relación existe entre Gödel y Alan Turing?
Ambos descubrieron límites fundamentales de los sistemas formales y los procedimientos mecánicos. Gödel investigó la demostrabilidad matemática, mientras que Turing formalizó la computabilidad y demostró la indecidibilidad del problema de la parada.
¿Por qué los descubrimientos de Gödel afectaron al programa de Hilbert?
Porque demostraron que no podía existir una axiomatización efectiva, consistente y suficientemente potente que fuera completa para la aritmética. Además, el segundo teorema estableció limitaciones fundamentales para demostrar formalmente la consistencia de determinados sistemas mediante sus propios recursos.
¿Gödel demostró que las matemáticas son incompletas?
Demostró que determinados sistemas formales suficientemente potentes son necesariamente incompletos. No demostró que todas las teorías matemáticas sean incompletas ni que las matemáticas carezcan de rigor.
¿Puede una computadora resolver el problema de la parada?
No existe una computadora que, mediante un algoritmo general, pueda resolver correctamente todos los casos del problema de la parada. Sí pueden analizarse y resolverse muchos casos particulares.
¿Los teoremas de Gödel demuestran que la inteligencia humana supera a la inteligencia artificial?
No. Esta interpretación excede lo que demuestran los teoremas. Los resultados establecen limitaciones matemáticas sobre determinados sistemas formales y procedimientos computables, pero no resuelven por sí mismos la comparación entre inteligencia humana y artificial.
¿Las matemáticas pueden seguir avanzando después de Gödel?
Por supuesto. Los matemáticos pueden desarrollar nuevos axiomas, teorías y métodos de demostración. La incompletitud no impide el progreso matemático; demuestra que ningún sistema formal efectivo suficientemente potente puede abarcar todas las verdades aritméticas.