En primer lugar, hay dos teoremas de incompletitud. La espectacular derivación de Gödel todavía se considera una hazaña de gran virtuosismo técnico y si lo desea (y tiene los antecedentes lógicos y matemáticos) para leerlo, puede encontrar el documento original con anotaciones modernas (y enlaces de hipertexto LaTeX útiles), aquí: http: //www.research.ibm.com/peop…
Sin embargo, durante el siglo pasado, los matemáticos han encontrado formas más fáciles de derivar los teoremas de incompletitud. De hecho, la prueba de Gödel era una forma de evitar un concepto fundamental que le faltaba en ese momento: una computadora. Si está familiarizado con los modelos teóricos de cómputo, como las máquinas de Turing o el cálculo lambda de Church, la prueba puede acortarse considerablemente. Si no es un informático teórico pero tiene una comprensión básica de lo que son una computadora y un programa, puede seguir el razonamiento informal a continuación.
Primero suponga que el teorema de incompletitud es falso. Es decir, existe un sistema formal consistente y computable [matemática] F [/ matemática] dentro del cual cualquier declaración sobre enteros puede ser probada o refutada (es decir, un sistema completo ). Aquí, [math] F [/ math] se supone que es lo suficientemente expresivo como para poder representar aritmética en números naturales. Dada una declaración particular [matemática] p [/ matemática] en el sistema, puede diseñar un programa de computadora que busque en todas las pruebas en [matemática] F [/ matemática] hasta que encuentre una que pruebe [matemática] p [/ matemática] o no [matemática] p [/ matemática] (su contradicción). Como [math] F [/ math] es consistente y completo, se garantizará que el programa arroje el resultado correcto. Además, podría usar esta estrategia para determinar si un programa de computadora dado [matemática] P [/ matemática] se detiene para una determinada entrada (esto puede parecer descabellado pero se debe simplemente al hecho de que la declaración “[matemática] P [/ matemática] ] se detiene en la entrada [math] x [/ math] “es equivalente a una declaración sobre enteros). Llamamos [math] H [/ math] al programa que, para un par dado de entrada de programa [math] (P, x) [/ math], decide si [math] P [/ math] se detendrá en la entrada correspondiente [matemáticas] x [/ matemáticas].
- ¿Qué es el modelado financiero?
- ¿Cómo rediseñaría la notación matemática hoy, si no necesitara soportar ningún equipaje histórico?
- ¿Es posible tener una probabilidad compleja o imaginaria? Si es así, ¿qué implicaría eso?
- Cómo encontrar el máximo factor común de 3 números
- Si Hitler pospusiera la preparación para Barbarroja y se concentrara en una invasión británica, ¿caerían las islas?
¿Qué sucede si modificamos [math] H [/ math] para escribir un nuevo programa [math] H ‘[/ math] que se comporte de la siguiente manera?
– [math] H ‘[/ math] se ejecuta para siempre (por ejemplo, al ingresar un bucle interminable) si se demuestra que [math] P [/ math] se detiene dado su propio código como entrada;
– se detiene si se demuestra que [math] P [/ math] se ejecuta para siempre dado su propio código de entrada.
Ahora, mire de cerca lo que sucede mientras alimentamos [math] H ‘[/ math] su propio código como entrada. O [math] H ‘[/ math] se ejecuta para siempre si se demuestra que detiene dado su propio código como entrada (que es lo que hemos hecho) o se detiene si se demuestra que se ejecuta para siempre. Hay una contradicción obvia aquí. Por lo tanto, [math] H ‘[/ math] se ejecutará para siempre sin descubrir una prueba de que se detiene o se ejecuta para siempre. Este es el primer teorema de incompletitud.
La derivación del segundo teorema de incompletitud se realiza formalizando la prueba anterior dentro del propio sistema. Te preguntarás por qué el argumento que acabamos de dar no es en sí mismo una prueba de que [math] H ‘[/ math] se ejecutará para siempre. ¿Por qué [math] H ‘[/ math] no descubriría esta prueba al explorar [math] F [/ math] y, por lo tanto, detenerse y, por lo tanto, correr para siempre, etc.?
La resolución de esa paradoja proviene de uno de nuestros primeros supuestos, a saber, que [math] F [/ math] es consistente. En un sistema consistente, ya sea [math] H ‘[/ math] se detiene o se ejecuta para siempre, no puede ser ambos. Pero no puede probar eso dentro de [matemáticas] F [/ matemáticas] en sí, ya que si pudiera, traería de vuelta la contradicción mencionada anteriormente. Por lo tanto, un sistema que demuestra su propia consistencia es en última instancia inconsistente y los sistemas consistentes son necesariamente incompletos (ya que hay declaraciones que no pueden probar, como su propia consistencia). Este resultado es el segundo teorema de incompletitud.
Fuente: http://www.scottaaronson.com/dem…
