Los límites de las matemáticas

Kurt Gödel
The same post in English

A finales del siglo XIX, Friedrich Ludwig Gottlob Frege, profesor de la universidad de Viena, emprendió un programa ambicioso: formalizar la aritmética mediante unos pocos axiomas y unas pocas reglas de deducción, de modo que todo teorema verdadero pudiese deducirse de los axiomas mediante cierto número de aplicaciones de las reglas de deducción. El resultado fue un libro monumental, Grundgesetze der Arithmetike (1893-1903), que entre otras cosas formalizó la teoría de conjuntos con una notación engorrosa, que pronto fue sustituida por la de Peano, que es la que usamos ahora.

Desgraciadamente para Frege, cuando estaba a punto de publicarse el segundo tomo de su libro, Bertrand Russell le envió una carta en la que demostraba que su formulación de la teoría de conjuntos daba pie a una inconsistencia. En la teoría de Frege, un conjunto puede pertenecer a otro conjunto. En particular, algunos conjuntos no pertenecen a sí mismos (como el conjunto de los números enteros, que no es un número entero), mientras otros sí pertenecen a sí mismos (como el conjunto de todos los conjuntos infinitos, que es infinito). Russell señaló que es posible definir el conjunto de todos los conjuntos que no pertenecen a sí mismos. Este conjunto lleva a una paradoja: si pertenece a sí mismo, no pertenece, y viceversa. La paradoja de Russell acabó con la obra de Frege, que tuvo que añadir apresuradamente un apéndice a su libro y abandonó la investigación sobre los fundamentos de las matemáticas.

Bertrand Russell y Alfred North Whitehead trataron de completar la obra de Frege en su libro Principia mathematica (1910-13), que estaba destinado a sufrir el mismo fin que el de Frege. En 1931, Kurt Gödel demostró su famoso primer teorema de incompletitud (Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme), que intuitivamente puede resumirse así: todo sistema formal consistente, con potencia similar a la aritmética, no es completo (contiene proposiciones verdaderas indecidibles). O sea: si partimos de un conjunto de axiomas y reglas de deducción, o bien acabaremos con un resultado inconsistente (como la paradoja de Russell), o habrá algún teorema verdadero que no podremos demostrar.

Informalmente, la demostración del teorema de Gödel se reduce a formular con notación matemática el siguiente teorema G: este teorema no se puede demostrar partiendo de los axiomas y reglas del sistema S. Si el teorema G fuese falso (o sea, sí se puede demostrar a partir de S) entonces S demuestra teoremas falsos, luego no es consistente. Por lo tanto, si S es consistente, el teorema debe ser verdadero, o sea, no se puede demostrar en S (eso es, precisamente, lo que afirma el teorema).

Alan Turing

El teorema de Gödel fue el primero de una serie de teoremas más o menos equivalentes. Uno de ellos es el problema de la parada, formulado y demostrado por Alan Turing, que se aplica a una familia de máquinas abstractas, que en su honor se llaman máquinas de Turing. Con estas máquinas se puede resolver cualquier problema abordable mediante un computador digital. De hecho, las máquinas de Turing son más potentes que los ordenadores, pues se supone que tienen memoria infinita, aunque con los tamaños de memoria actuales esta restricción casi siempre puede ignorarse.

Turing formuló así el problema de la parada: supongamos que conocemos la descripción de una máquina de Turing, que consta de dos partes: el programa que va a ejecutar la máquina y los datos de entrada que recibe. Antes de ponerla en marcha, ¿es siempre posible predecir si llegará a pararse, o si se meterá en un bucle cerrado que nunca termine?

Parece un problema sencillo, pero Turing demostró que no siempre es posible hacer esa predicción. Por supuesto, para máquinas poco complejas sí se puede. Pero el problema de la parada pregunta si la predicción puede hacerse siempre. Turing lo demostró por reducción al absurdo: supuso que el problema de la parada tiene solución y llegó a una contradicción. Por lo tanto, la hipótesis es falsa.

El hecho de que existan problemas no computables conmocionó a los informáticos, pues es una limitación teórica de la tecnología informática, muy diferente de los límites prácticos que hacen que algunos problemas intrínsecamente difíciles sean imposibles de resolver. Estos problemas se pueden resolver en teoría, pero haría falta un ordenador tan grande como el universo, funcionando durante toda la vida del universo. Uno de los problemas de este grupo tiene por objeto calcular la solución perfecta de una partida de ajedrez. En teoría, ese programa podría escribirse, pero su tiempo de ejecución sería inaceptable.

Roger Penrose

Durante los años sesenta, el matemático Gregory Chaitin demostró otro teorema parecido: la aleatoriedad de un conjunto de números enteros es indecidible. Esto se puede ilustrar con los dígitos de π, que cumplen las pruebas de aleatoriedad, pero no son aleatorios.

En 1989, Roger Penrose (en The emperor’s new mind) propuso la siguiente cuestión, inspirada en el teorema de Gödel: ¿cómo es que podemos demostrar que un teorema es verdadero, si no se puede demostrar matemáticamente a partir de un conjunto razonable de axiomas? Según él, esto podría indicar que la inteligencia humana es cualitativamente distinta de la de las máquinas computadoras.

Hilo Temático sobre Matemáticas: Anterior Siguiente

Manuel Alfonseca

29 comentarios:

  1. Doy mi opinión como matemático católico.
    Recuerdo uno de los resultados que me impactaron sobre manera en mi época de estudiante de Lógica Matemática –El Teorema de Gödel- y que reforzó aún más en mi fe en Dios y mi desconfianza en la Ciencia y particularmente en el uso abusivo de la razón. Fue un gran golpe para mi mentalidad racionalista en la que estaba siendo formado, en la que había llegado a creer que a base de Matemáticas se podía modelizar y explicar toda la creación.

    Muchos rankings consideran este resultado como el más importante de la Filosofía del siglo XX y el "Times" incluso propuso a Gödel como a uno de los 100 hombres más influyentes del pasado siglo XX. Y estoy de acuerdo en ello. Me sorprende mucho que tan poca gente lo conozca.

    Pues bien, en 1931 Kurtz Gödel mostró su teorema de incompletidud de la Lógica.

    Demostró que dentro de la Lógica de segundo orden - la que usamos casi todos, pues es la Lógica clásica añadiéndole el uso de cuantificadores universales (para todo, existe), EXISTEN afirmaciones (fórmulas lógicas) que son indemostrables, es más; existen afirmaciones que si se las supone ciertas se llega a una contradicción, y si se las supone falsas, también. (De ahí que muchos matemáticos no acepten las demostraciones por reducción al absurdo).


    Hay una versión mas refinada de este teorema, en la que se afirma que basta solamente con que cualquier sistema de Lógica que contenga sólamente los axiomas de los números enteros -la existencia del cero, y todo número entero tiene un siguiente - (piedra angular de nuestra ciencia y de la Aritmética) y que llega a los mismos resultados. Y a ningún lógico, por muy lógico por muy loco que estuviese, se le ocurriría formular otra axiomática en la que no figurasen esos dos axiomas.

    Estos resultados nos conducen directamente a la incompletitud de la actual ciencia humana basada en los principios de la Lógica. Con tan prepotentes que nos creemos, siempre habrá algo que no vamos a poder demostrar. Y además nuestra ciencia que se enorgullece de estar sobre sólidos pilares, ni siquiera nos garantiza que, aunque alguien demuestre que algo sea cierto pueda llegar otro y demuestre lo contrario ¡Nunca llegaremos a ser Dios!

    Hay otro resultado “el problema de la parada” (Halting Problem -Alan Turing, 1936) que también da que pensar. Aquí se demuestra que es imposible que exista un algoritmo o programa informático que decida si ante una determinada entrada el programa se va a “parar” o va a entrar en bucle. ¡Oh! . ¡Qué pequeños y limitados somos! ¡lo que falta para llegar a ser dioses! ¡Si ni siquiera nunca nadie va a ser posible lograr esto tan fácil de enunciar! ¡Sólo Dios!

    Estos teoremas también deberían ser un lastre inexorable para aquellos que solo mediante la razón pura pretenden llegar a probar o negar la existencia de Dios. O para los que pretenden llevar al racionalismo hasta límites insospechados sin tener en cuenta la fe.

    Cuento todo esto, para argumentar un poco las limitaciones del razonamiento humano. Cierto es con que la razón se han conseguido resultados y conocimientos formidables, pero para mi, esta debe estar supeditada a la fe.
    Los filósofos deberían quedarse con esta conlusión del Teorema de Completitud de Gödel "La verdad y lo demostrable son dos categorías esencialmente distintas"

    ResponderEliminar
    Respuestas
    1. Maranatha, comparto en buena medida tus experiencias y punto de vista.

      >> Estos teoremas también deberían ser un lastre inexorable para aquellos que solo mediante la razón pura pretenden llegar a probar o negar la existencia de Dios.

      A mi modo de ver, el empeño por demostrar racionalmente la existencia de Dios se presenta a menudo como un intento para salvar la fe, pero yo lo veo más bien como un intento de capturar o encerrar a Dios en la limitada razón humana. Demostrar su existencia es una forma de someterlo a nuestra razón.

      Por cierto, supongo que sabes que Gödel también tiene su versión del argumento ontológico de Anselmo y Leibniz.

      Eliminar
    2. Hablé de la prueba ontológica de Gödel aquí: Teología matemática

      Eliminar
  2. Gracias por este artículo. He leído muchas exposiciones del teorema de Gödel y el de Turing, pero pocas tan sencillas y claras como esta.

    Ahora bien, me surge una duda. Tengo claro que el teorema de Gödel afirma que un sistema formal consistente contiene proposiciones indecidibles (no es completo).

    Ahora bien, no solo se afirma esto, sino también que hay proposiciones verdaderas indecidibles. Es como si se dijera: "toda proposición tiene que ser verdadera o falsa, lo que ocurre es que hay algunas que no podemos demostrar si son una cosa o la otra".

    Pero quizás la premisa es equivocada, y no podemos afirmar con rotundidad que toda proposición es verdadera o falsa. Así, una proposición indecidible no es ni verdadera ni falsa. Las proposiciones entonces se clasifican en tres categorías, no dos: verdaderas, falsas, e indecidibles.

    A mi modo de ver el matiz no es irrelevante. He oído exposiciones del teorema de Gödel en las que se da a entender que hay proposiciones que sabemos que son verdaderas, pero no podemos demostrarlo. Si yo tengo razón, entonces esta última explicación es equivocada.

    ResponderEliminar
    Respuestas
    1. Como dices al final de tu comentario, el teorema de Gödel afirma que hay proposiciones verdaderas indecidibles (no demostrables a partir de los axiomas y las reglas de transformación), pero sabemos que son verdaderas, porque su negación es falsa.

      Eliminar
    2. Recuerdo haber visto en mi época de estudiante de Lógica (hace 40 años) proposiciones que tanto ellas mismas como su negación podían ser tanto ciertas como falsas.
      De hecho, hay una corrientes o escuelas de pensamiento matemático que no aceptan las demostraciones por reducción al absurdo...
      Aquellas proposiciones que estaban en esa tesitura estaban por supuesto encuadradas dentro de la Lógica de Segundo Orden con un montón de cuantificadores sobre conjutos infinitos y sóbre la existencia de fórmulas... realmente complicadas...

      Me acuerdo en Teoría de la Computabilidad lo importante que era aceptar o no el axioma de elección en aquellas demostraciones en las que se encontraba una solución eligiendo infinitamente siempre el elemento que estaba en la diagonal... Si no se aceptaba, era realmente imposible demostrar un montón de cosas..

      Saludos al profesor Alfonseca... es un pozo de sabiduría multidisciplinar. No paro de aprender y de tapar agujeros leyéndole. Yo también pasé por el Centro de Cálculo de la Complutense :-)
      Un saludo entrañable
      Javier López

      Eliminar
  3. ¿Y no es esto lo mismo? Si la proposición es indecidible, no podemos saber que es verdadera porque su negación sea falsa. Si podemos saber que es verdadera (o falsa) entonces no es indecidible.

    PD. Me alegro de que estés mejor.

    ResponderEliminar
    Respuestas
    1. Gracias.

      No me he explicado bien. Lo que demuestra el teorema de Gödel es que el teorema G, que es verdadero (y la demostración de eso está en el propio teorema de Gödel), no se puede demostrar a partir de un conjunto de axiomas y reglas de deducción.

      No se trata de que el teorema G sea indecidible a secas. Su verdad es decidible. Pero no se puede demostrar (en el caso de la aritmética) a partir de los axiomas de Peano. Y si añadimos el teorema G como axioma a los de Peano, surge automáticamente otro teorema G' que no se puede deducir del nuevo conjunto de axiomas. Por eso la formalización de la aritmética es incompleta.

      Eliminar
    2. Entonces me parece que entiendo menos de lo que pensaba. ¿Cómo puede ser que el teorema G es verdadero, y se puede demostrar, pero no se puede demostrar a partir de un conjunto de axiomas y reglas de deducción? ¿A partir de qué se puede demostrar, entonces?

      Obviamente, no estoy pretendiendo que solo conocemos como verdadero lo que se puede demostrar formalmente. Estoy convencido que nuestro conocimiento no es solo formal.

      Pero en este caso se dice, según entiendo, que G se puede demostrar formalmente, pero no se puede demostrar formalmente.

      Eliminar
    3. Lo que demuestra el teorema de Gödel no es que hay teoremas que no se pueden demostrar, sino que cualquier formalización de la aritmética es incompleta (o sea, se deja fuera teoremas verdaderos que no se pueden demostrar a partir de esa formalización.

      He puesto en cursiva la última frase porque es crucial. Supongamos que partimos de los axiomas de Peano, formalización habitual de la aritmética. Entonces hay al menos un teorema aritmético que es verdadero, pero no se puede demostrar a partir de esos axiomas.

      Por qué ese teorema es verdadero está explicado en el cuarto párrafo de este artículo.

      Eliminar
  4. Usted cree que cambiaran las cosas nota. Algun cambio? Me refiero a si sabe de cientificos como usted que no comulgan con el nihilismo materialista? ya deberian de modificar el paradigma. Como dice juan arnau astrofisico y filosofo.Estamos ante un cambio de paradigma?

    Sin duda, lo necesitamos. ¡Pero este sistema lleva agonizando tantos años! Resulta increíble que aún no hayamos asimilado lo ocurrido en el siglo veinte y en muchos aspectos sigamos atados a los más rancios dogmas científicos del diecinueve. Al determinismo y pesimismo darwinianos, que afortunadamente ya empiezan a matizar muchos biólogos y filósofos, al espacio y tiempo absolutos de Newton, que ya fueron pulverizados por Einstein y la física cuántica hace casi un siglo. Y lo peor de todo, a la falsa y pobre idea, que ha invadido nuestro imaginario, de que somos una máquina y el universo una especie de mecanismo que sigue ciegamente leyes mecánicas. El materialismo ya no se sostiene. Hay infinidad de evidencias y teorías consensuadas que demuestran que su reduccionismo es ya inaceptable, y que ya no vale la fórmula de seguir echando las pelotas fuera. Ha llegado el momento de ampliar la visión de la realidad. La materia es una parte de la realidad, pero no la única. La otra es la experiencia psíquica. No se puede excluir la psique de la naturaleza y el cosmos. Es un mero acto de fe. En el «nuevo» (entre comillas) paradigma, la psique es la fuente de la realidad, no la materia. La mente ya no es un epifenómeno de la materia, sino la materia una representación de la mente. Existe, pero es indisociable de nuestra experiencia psíquica. Los nuevos paradigmas -porque no solo hay uno-no se limitan a ofrecer soluciones simples -como aquello de que sólo lo que tocas es lo real-sino que dan respuestas más complejas e integradoras. Pero además se ha de otorgar un sentido al mundo, porque en la ciencia clásica el azar y el determinismo ciego es el único sentido subyacente. La vida carece de sentido y de propósito. ¡Y a esto lo llaman madurez del pensamiento

    ResponderEliminar
    Respuestas
    1. No sólo tengo muchos amigos científicos creyentes, incluso le he dado una lista más de una vez.

      Eliminar
    2. ... y por añadir algo más, creo que tiene usted también un numero quizá menor, pero no despreciable, de amigos científicos no creyentes..

      Un abrazo.

      Eliminar
    3. Lo sé, pero Bruno preguntaba si yo conocía científicos creyentes, por eso le contesté así.

      Eliminar
  5. https://www.elconfidencial.com/amp/tecnologia/2021-05-14/inteligencia-artificial-aprende-olvidar_3081123/ esto que significa?

    ResponderEliminar
    Respuestas
    1. Sobre esto trabajé yo hace casi 20 años. Vea este artículo:

      The role of oblivion, memory size and spatial separation in dynamic language games. J.de Lara, M.Alfonseca. The Journal of Artificial Societies and Social Simulation (JASSS) (SCI JCR 0.019), 5:2, Apr. 2002.

      No tiene nada que ver con lo que a usted le preocupa.

      Eliminar
  6. Lo pregunto porque los neurocientificos suelen ser los mas reduccionistas y explican lo espiritual como errores del cerebro etc

    ResponderEliminar
    Respuestas
    1. Primero es la filosofía que tiene cada persona: reduccionista, emergentista, dualista integrada o dualista independiente. Después, cualquier descubrimiento científico se interpreta de acuerdo con la filosofía de cada cual.

      No es extraño que haya muchos neurocientíficos ateos, y por tanto materialistas. Desde el siglo XIX, la mayor proporción de científicos ateos se ha dado entre los médicos. Pero también hay muchos médicos (y neurocientíficos) creyentes, como le he dicho varias veces.

      Eliminar
  7. https://tendencias21.levante-emv.com/crean-un-circuito-organico-capaz-de-aprender-como-lo-hace-el-cerebro.html solo una duda esto no es relacionado con el monismo ?

    ResponderEliminar
    Respuestas
    1. No. De hecho, mi primer trabajo de investigación (hace más de 50 años), en el Centro de Cálculo de la Complutense, fue sobre esto.

      Eliminar
  8. https://www-elconfidencial-com.cdn.ampproject.org/v/s/www.elconfidencial.com/amp/tecnologia/novaceno/2021-05-17/skyborg-caza-combate-autonomo-estados-unidos_3083539/?amp_gsa=1&amp_js_v=a6&usqp=mq331AQFKAGwASA%3D#amp_tf=De%20%251%24s&aoh=16213276109453&csi=1&referrer=https%3A%2F%2Fwww.google.com&ampshare=https%3A%2F%2Fwww.elconfidencial.com%2Ftecnologia%2Fnovaceno%2F2021-05-17%2Fskyborg-caza-combate-autonomo-estados-unidos_3083539%2F solo aclareme esto cuando pueda y nada mas

    ResponderEliminar
    Respuestas
    1. Esto no es más que un programa más avanzado de guerra automática. Ha habido muchos predecesores, y este es un paso más. Lo de llamarlo cerebro es un eufemismo.

      Eliminar
  9. https://tendencias21.levante-emv.com/el-mundo-cuantico-puede-ser-hackeado.html

    ResponderEliminar
    Respuestas
    1. Muchas veces se ha dicho que cuando tuviéramos comunicaciones cuánticas sería imposible hackearlas. Aquí dicen que quizá no sea tan imposible. Era de esperar. Cualquier cosa que haga el hombre, otro hombre lo puede estropear. Lo que no sé es por qué le preocupa esta noticia.

      Eliminar
  10. Entiendo que el principio de incertidumbre no se refiere a las partículas propiamente, sino a la mente. Las partículas podrían seguir leyes deterministas aún no descubiertas.

    ResponderEliminar
    Respuestas
    1. Todas las interpretaciones de la Mecánica Cuántica que han intentado partir de esa hipótesis han fracasado. La de Copenhague, para la que el principio de incertidumbre no es un límite epistemológico, sino físico, sigue activa casi un siglo después.

      Eliminar
  11. https://tendencias21.levante-emv.com/descubren-la-puerta-de-entrada-a-la-consciencia-en-el-cerebro.html esto que significa?

    ResponderEliminar
    Respuestas
    1. Se refiere al paso de la información inconsciente (casi toda) al nivel consciente. Hay que filtrarla, si no nos ahogaría tanta información.

      Eliminar