Computabilidad y Gödel

Date: Tue, 2 Nov 1999 11:33:59 +0100
From: Nicandro Cruz-Ramirez
--------
Hola Carlos:

Despues de un tiempo de estar "fuera del aire" retomo el tema del ultimo mensaje que habia quedado pendiente de mi parte.

>---Nicandro---
Godel y Turing (entre otros) demostraron que hay cosas que no son computables en el sentido que no existe algoritmo alguno para generar una infinidad de secuencias a partir de un conjunto de axiomas y
reglas (universo). Existen algunos ejemplos muy interesantes sobre la existencia de conjuntos no recursivos que ilustran estas ideas. Ahi entra un nivel mas alto de "penetracion" de la inteligencia, digamos, una meta-inteligencia que aun no ha llegado a ser, hasta la fecha, del todo comprendida por ningun enfoque: psicologico, computacional, de la fisica cuantica, etc. y por lo tanto, no reproducida por ningun algoritmo.
En mi opinión Gödel no demostró que existan cosas que no son computables. El se refería a la aritmética, como un caso de sistema formal, y no afirmó algo que entraría de lleno en el campo de la metafísica (una proposición del tipo "existe algo que tiene entidad
propia -es una cosa- y no es computable"). Yo, personalmente dudo que exista algo que no sea computable, aunque resulta evidente que existen muchas cosas que *no son computadas*.
---
>Hola Nicandro:
Espero no te tome de sorpresa que vuelva atrás en algunos comentarios tuyos. Pero me encontré con éste párrafo escrito por ti (buscando otras cosas) que ahora me suscita la siguiente reflexión...
Naturalmente no espero una respuesta inmediata, así que tómatelo con tranquilidad :-)
Carlos
---

La prueba del teorema de la "incompletitud" que logro Godel fue efectivamente en el campo de la Teoria de Numeros; sin embargo es posible deducir (teniendo como base la definicion de un sistema formal) que dicha prueba es equivalente a la "irresolubilidad" del "halting problem" (que postulo Turing) o a la afirmacion de que existe un conjunto recursivamente enumerable que no es recursivo. De ahi podemos afirmar que existen cosas que no son computables o demostrables a partir de un conjunto de axiomas y reglas. Perdona si me explique mal pero no quise decir que Godel tuviera en mente el campo de la metafisica para aplicarle su demostracion. Por otro lado difiero un poco de tu opinion: creo que si hay cosas que no son computables. Pero te pregunto, a que te refieres con que haya cosas que no son computadas?

---
>Después de Gödel se puede afirmar con cierta seguridad que un sistema formal no puede ser a la misma vez completo y consistente (1); pero hay muchas cosas en el mundo que no son sistemas formales. Y de ellas Gödel no puede decir nada (o mejor dicho, no lo dijo). Yo puedo inclinarme conscientemente (es decir con deliberación) por la hipótesis que "fuera de los sistemas formales todo es computable... mientras no se demuestre lo contrario" y quedarme lo más tranquilo. En todo caso me parece una *hipótesis de trabajo* provocativamente estimulante :-)

Llamada (1)
Antes de Gödel, se pensaba que toda proposición dentro de un sistema axiomático era demostrablemente verdadera o demostrablemente falsa. Gödel mostró que había una tercera posibilidad: existían proposiciones que no se podía demostrar si eran verdaderas o falsas.
Ej. la conjetura de Goldbach: "todo número par puede obtenerse mediante la suma de dos primos". No puede demostrarse ni su verdad ni su falsedad dentro del sistema de la aritmética.

Carlos
---

Creo que hay mucha gente tratando de "encasillar" esas cosas en el mundo que tu mencionas que no son sistemas formales en sistemas formales para poder tener un cierto modelo que nos ayude a comprendelas mejor (tal vez).

Saludos.

Nicandro.