miércoles, 6 de marzo de 2013

Entendiendo el teorema de incompletitud de Gödel

Este teorema es uno de los más importantes del siglo XX. Aquí tenéis una selección de textos de distintos científicos que os ayudarán a entenderlo.

Jones & Wilson, Una educación incompleta
En 1931, el matemático checo Kurt Gödel demostró que dentro de cualquier rama de las matemáticas, siempre habría algunas proposiciones que no se podrían probar como verdaderas o falsas usando las reglas y axiomas de la propia rama matemática. Podrías ser capaz de probar cada afirmación concebible sobre números dentro de un sistema, saliendo fuera del mismo con el fin de obtener nuevos axiomas o reglas, pero haciendo eso, solo creearías un sistema más grande con sus propias afirmaciones no probadas. La implicación es que todo sistema lógico de cualquier complejidad es, por definición, incompleto; cada uno de ellos contiene, en cualquier momento, más afirmaciones ciertas de las que pueden ser probadas de acuerdo con su propia definición del conjunto de reglas.

El Teorema de Gödel ha sido usado para argumentar que una computadora nunca podrá ser más inteligente que un humano, ya que la extensión de su conocimiento está limitada por un conjunto fijo de axiomas, mientras que las personas pueden descubrir verdades inesperadas. Juega un papel en las teorías linguísticas modernas, las cuales enfatizan el poder del idiona para encontrar nuevas formas de expresar ideas. Y esto se ha tomado para implicar que nunca te comprenderás completamente a ti mismo, ya que tu mente, como cualquier otro sistema cerrado, solo puede estar segura de lo que sabe sobre si misma basándose en lo que sabe de si misma.

Boyer, Historia de las Matemáticas
Gödel mostró dentro de un rígido sistema lógico tal y como Russell y Whitehead lo habían desarrollado para la aritmética, que las proposiciones pueden formularse de manera indecidible o indemostrable dentro de los axiomas de un sistema. Esto es, dentro del sistema, ahí existen ciertas afirmaciones bien definidas que nunca pueden ser probadas o desmentidas. Por tanto, uno no puede, usando los métodos habituales, asegurarse de que los axiomas de la aritmética no darán lugar a contradicciones... Parece condenar la esperanza acerca de la certeza matemática a través del uso de los métodos obvios. Tal vez condenando también, como consecuencia, el ideal de la ciencia: establecer un conjunto de axiomas del que todos los fenómenos del mundo externo se pueden deducir.

Nagel & Newman, La prueba de Gödel
Él probó que es imposible establecer la consistencia lógica interna de una enorme clase de sistemas deductivos - aritmética elemental, por ejemplo - a menos que uno adopte principios de razonamiento tan complejos que su consistencia interna sea tan abierta como para dudar que los propios sistemas. La segunda conclusión principal es que que Gödel mostró que el Principia, o cualquier otro sistema dentro del cual puede desarrollarse aritmética, es esencialmente incompleto. En otras palabras, dado cualquier conjunto consistente de axiomas, hay afirmaciones matemáticas verdaderas que no pueden ser derivadas del conjunto... Incluso si los axiomas de la aritmética estuviesen argumentados por un número indefinido de otros ciertos, siempre habría verdades matemáticas más allá que no serían formalmente derivables a partir del conjunto aumentado.

Rucker, Infinito y la Mente
La prueba del Teorema de Incompletitud de Gödel es tan simple y silenciosa que es casi embarazoso relatarla. El procedimiento básico es el siguiente:

Alguien introduce a Gödel a la UTM, una máquina la cual se supone que es la Maquina Universal de la Verdad, capaz de responder correctamente cualquier cuestión. Gödel pregunta por el programa y el diseño de circuitos de la UTM. El programa podría ser complicado pero solo puede ser finitamente largo. Denominemos al programa como P(UTM). Sonriendo un poco, Gödel escribe la siguiente frase: "La máquina construida en los fundamentos del programa P(UTM) nunca podrá decir que esta sentencia es verdadera." Denominemos a esta sentencia como G por Gödel. Hágase notar que G es equivalente a: "UTM nunca dirá que G es verdadera". Ahora Gödel se ríe a carcajadas y pregunta a la UTM si G es cierta o no.

Si UTM dice que G es cierta, entonces "UTM nunca dirá que G es cierta" es falsa. Si "UTM nunca dirá que G es cierta" es falsa, entonces G es falsa, ya que G es igual a "UTM nunca dirá que G es cierta". Así pues, si UTM dice que G es cierta, entonces G es de hecho, falsa, y UTM ha hecho una afirmación falsa. Por tanto, UTM nunca dirá que G es cierta, ya que UTM solo hace afirmaciones verdaderas. Hemos establecido que UTM nunca dirá que G es cierta. Por tanto, "UTM nunca dirá que G es cierta" es de hecho una afirmación cierta. Así pues, G es cierta, ya que g es igual a "UTM nunca dirá que G es cierta". Gödel dijo que conocía un verdad que la UTM nunca podrá pronunciar. "Se que G es cierta, y la UTM no es ciertamente universal. Piensa en ello... crecerá en ti".

Con su genial genio lógico y matemático, Gödel fue capaz de descubrir la manera, para cualquier P(UTM) dado, de anotar una complicada ecuación polinómica que tiene solución si y solo si G es cierta. Por tanto, G no es solo una sentencia vaga o no matemática. G es un problema matemático específico del cual conocemos la respuesta, ¡incluso aunque no la conozca la UTM! Así pues, la UTM no puede encarnar una mejor y última teoría de las matemáticas...

Aunque este teorema puede afirmarse y probarse de manera rigurosamente matemática, lo que parece decir es que el pensamiento racional nunca puede penetrar en la verdad última... Pero, paradójicamente, comprender la prueba de Gödel es descubrir una especie de liberación. Para muchos estudiantes de lógica, el descubrimiento final para comprender completamente el Teorema de Incompletitud es prácticamente una experiencia de conversión. Esto es en parte un subproducto de la potente mística que acarrea el nombre de Gödel. Pero, más profundamente, para entender que la naturaleza esencialmente laberintica del castillo está, de alguna manera, estar libre de ella.

Hofstadter, Gödel, Escher, Bach
Todas las formulaciones axiomáticas consistentes de la teoría de números incluyen proposiciones indecidibles... Gödel mostró que la demostrabilidad es una noción más débil que la verdad, no importa qué sistema de axiomas está involucrado.

¿Cómo podemos averiguar si estamos cuerdos?... Una vez empiezas a cuestionar tu propia cordura, quedarás atrapado en un vórtice más estrecho de profecías autocumplidas, aunque el proceso se inevitable por todos medios. Todo el mundo sabe que la locura interpreta el mundo mediante su propia y peculiar lógica consistentes; ¿Cómo puedes afirmar que tu lógica es "peculiar" o no, dado que solo tienes tu propia lógica para juzgarla? Yo no veo respuesta alguna. Me acuerdo del segundo teorema de Gödel, que implica que las únicas versiones de la teoría de números formal que afirman su propia consistencia son inconsistentes. La otra analogía metafórica del Teorema de Gödel que encuentro provocativa, sugiere que, en definitiva, no podemos entender nuestras propias mentes... Del mismo modo que no podemos ver nuestras caras con nuestros propios ojos, ¿no es inconcebible suponer que no podemos reflejar nuestras estructuras mentales completas en los símbolos que las llevan a cabo? Todos los teoremas limitadores de las matemáticas y la teoría de la computación sugieren que una vez que la habilidad de representar tu propia estructura ha llegado a un determinado punto crítico, esto supone el beso de la muerte: garantiza que nunca te podrás representar a ti mismo completamente.

Via miskatonic

10 comentarios:

  1. Jones & Wilson, en "nunca te comprenderás completamente a ti mismo, ya que tu mente, como cualquier otro sistema cerrado, solo puede estar segura de lo que sabe sobre si misma basándose en lo que sabe de si misma" caen en la falacia de asumir que la mente individual es un sistema cerrado. Asumen como punto de partida un individualismo radical (casi solipsista) que me cuesta aceptar. El individuo se construye en tanto que ente social y parte de una o varias comunidades, y por lo tanto creo que aplicar el teorema de incompletitud de Gödel sería falaz y reduccionista para con la mente.

    ResponderEliminar
  2. Excelente entrada, por cierto! Gödel fue uno de esos momentos que te iluminan cuando empiezas una carrera. Muchas gracias por recordarmelo.

    ResponderEliminar
  3. "una computadora nunca podrá ser más inteligente que un humano", si se consiguiese que una computadora fuese capaz de aprender ( y creo que no es imposible, puestos a entrar en un juego mental ), no sería un sistema cerrado, puesto que aprendería de nuevas realidades "ajenas" al creador, así que... discrepo con los que se apoyan en esta afirmación.

    ResponderEliminar
  4. A mí me gustó mucho la demostración de la teoría complementaria a ésta, la de ''No computabilidad'' de Turing que da Penrose en ''La nueva mente del emperador''.

    ResponderEliminar
  5. Iba a recomendar la lectura de "El hombre que sabía demasiado" acerca de Turing, o unos documentales sobre matemáticos http://vimeo.com/30482156 y http://vimeo.com/30641992

    ResponderEliminar
  6. EL TEOREMA DDE INCOMPLETITUD DE GODEL ES FALSO¡¡¡VEAN EL BLOG sangretroyana blogspot.com o por google LAS FALACIAS DE KURT GODEL,UN SALUDO JUAN

    ResponderEliminar
  7. Me gustó. Es como el diccionario. Si existen, que las hay, palabras no definidas en el diccionario, éste estará incompleto, pero será consistente ya que las definiciones de las palabras se dan una en base a las otras (no hay contradicciones). Sin embargo, si todas las palabras que son capaces de existir estuvieran definidas en el diccionario (completo), este seria inconsistente, ya que la palabra "soyunaplabraquenopuedeserdefinida" estaría definida por palabras, tal que: "soyunaplabraquenopuedeserdefinida" = “soy una palabra que no puede ser definida a través de palabras por ningún diccionario”, siendo esta palabra una perfectamente valida combinación de letras (un lenguaje), e incluso está perfectamente definida a pesar, de no ser posible de definir (contradicción).

    ResponderEliminar
  8. Las maquinas deductivamente superan la inteligencia humana (deep blue, watson, y el agente campeon de go, p. ej), pero es dudoso que puedan inferir y sin dudas no son capaces de abduccion. Y si por efecto de "fuerza bruta computacional" parecen inferir, las "inferencias" que aparentan realizar son asociaciones entre los datos que se ingresan con datos que estan en su memoria. Las soluciones que da son las que le fueron cargadas y por asociacion terminologica entre estas y los datos del problema que se le ingresan, da un resultado que semanticamente puede ser un absurdo.
    El teorema de Godel parte de una premisa incorrecta porque todos los programas de IA dan una respuesta con una probabilidad de error. Todos los agentes dan un porcentaje de error que tiene el resultado que dan.
    En el caso concreto del teorema la resp de P(UPM) es que G es cierto con un 50o/o de seguridad.
    No hay ningun programa "decisorio" (o metadocumental) que de respuestas sin margen de error.

    ResponderEliminar
  9. Los teoremas de K. Godel son FALSOS !!!

    ResponderEliminar