PDF de programación - Gödel Metáforas y realidades

Gödel

Mitos y realidades

Marco Aurelio Alzate Monroy

Universidad Distrital Francisco José de Caldas

(*)



(*) No es un matemático. Es simplemente un ingeniero al que le dio
por estudiar sistemas complejos... ¡Sean indulgentes, por favor!

Los libros que quise
estudiar para hoy…

…pero apenas
alcancé a hojearlos

Algunos Mitos y Realidades en la
Teoría de Sistemas Complejos
 Realidad: Los fenómenos complejos se dan lejos del equilibrio

termodinámico, el equilibrio más estable. Mito: Los fenómenos
complejos se dan lejos de cualquier equilibrio, en particular del
equilibrio estable.

 Realidad: Los sistemas dinámicos lineales no pueden presentar
comportamientos complejos. Mito: Los sistemas complejos son
ajenos a cualquier forma de linealidad.

 Realidad: Cualquier forma de control centralizado va en contravía

de la complejidad. Mito: Cualquier forma de control va en
contravía de la complejidad.

 Realidad: Los sistemas vivos superan la capacidad computacional

de la máquina de Turing, la cual no resuelve eficientemente los
problemas NP. Mito: La vida es un problema NP.

Algunos Mitos con respecto a los
teoremas de Gödel

 Mito: Los teoremas de Gödel establecen un límite a las pretensiones de la razón

humana.

 Mito: Los teoremas de Gödel dicen que ninguna verdad puede establecerse de

manera definitiva

 Mito: Los teoremas de Gödel dicen que, ni siquiera en las matemáticas, puede haber

total certidumbre.

 Mito: El teorema de la consistencia de Gödel dice que ninguna teoría puede ser

consistente.

 Mito: Los teoremas de Gödel dicen que ninguna teoría puede ser a la vez consistente

y completa.

 Mito: Los teoremas de Gödel dicen que toda teoría de la aritmética es incompleta.

 Mito: Los teoremas de Gödel dicen que toda teoría recursiva es incompleta.

 Mito: Los teoremas de Gödel no tienen ninguna incidencia en las matemáticas.

¿1+1=2?

¿La virgen María fue concebida sin pecado?

 x (x + 0 = x)  1 + 0 = 1

 xy ( x + S(y) = S(x + y) )  1 + S(0) = S(1+0) = S(1)

 S(0) = 1 y S(1) = 2

  1 + 1 = 2

QED 

Quod erat demonstrandum

Una verdad
Demostrable

¡Isomorfismo!

AXIOMAS

Axiomas: Conjunto reducido de enunciados verdaderos,
seleccionados de manera tal que puedan obtenerse de ellos,
mediante demostración, todos los enunciados verdaderos en
el sistema.

Demostraciones

Demostración: Sucesión de enunciados, encadenados por
pasos elementales estrictamente lógicos, de manera que
cualquier persona (o máquina) pueda examinarlos para tener
la seguridad de que no se ha cometido ningún error.

TEOREMAS

Teorema: Último enunciado de la demostración. Cuando el
razonamiento es profundo, el teorema sorprende, maravilla:
La creatividad, la inspiración y el arte participaron en la
elección de los pasos que, entre todas las bifurcaciones
posibles, marcaban el camino oculto que llevaba de los
axiomas a los teoremas.

Forma típica de un teorema: Si se cumple un conjunto de hipótesis, entonces se verifica una tesis.

Corolario: Conclusión (más o menos) inmediata de un teorema

Lema: Sentencia intermedia de la demostración (que pudo haber sido un teorema por demostrar)

Un hermoso ejemplo

Un sistema formal consiste de los símbolos {M, I, U} y algunas reglas gramaticales para

construir cadenas válidas a partir de otras conocidas con anterioridad:



Axioma : MI
Reglas gramaticales : 1. Si xI, entonces xIU

2. Si Mx, entonces Mxx
3. Si xIIIy, entonces xUy
4. Si xUUy, entonces xy

Tarea : Demuestre MU, si es posible

Douglas R. Hofstadter,
“Gödel, Escher, Bach: an Eternel Golden Braid”,
Basic Books, 1979

(donde x & y son cualquier secuencia
–aún secuencias vacías– de símbolos
M, I y/o U)

1. Si xI, entonces xIU
2. Si Mx, entonces Mxx
3. Si xIIIy, entonces xUy
4. Si xUUy, entonces xy

2

MII

1

2

4

MIIU

MIIII

4

4

4

MI

1

MIU

2

3

MIUIU

2

2

1

2

3

MIUIUIUIU

MIIUIIU

MIIIIU

MIIIIIIII

MUI

2

2

2

3

3

MIUIUIUIUIUIUIUIU

MIIIIUIIIIU MUIU MIUU

MUUII MIUUI MIIUU

MIIUIIU

MUIUUIU MIUUUIU MIUUIUU

MUIIU

Douglas R. Hofstadter,
“Gödel, Escher, Bach: an Eternel Golden Braid”,
Basic Books, 1979

3 maneras: Mechanical mode
I ntelligent mode
U n-mode

El modo Mecánico aplica las reglas hasta que aparezca MU… ¡o por toda la
eternidad si MU no aparece!

El modo Inteligente empieza observando patrones mientras se gana experiencia
con el sistema. Por ejemplo, ninguna regla exige que los teoremas empiecen con
M, pero la relación entre el axioma inicial y las reglas de producción hacen obvio
que los teoremas deben empezar con M.

Sólo las reglas 2 y 3 cambian este número.
La regla 2 lo dobla, mientras que le regla 3 lo reduce en 3.
Entonces hay una propiedad de invarianza: El número de Ies no es divisible por 3:

Es imposible llegar a la cadena MU desde la cadena MI mediante la aplicación repetida de las reglas
dadas. Para probar esta afirmación basta con mirar el número de Ies en una cadena:



Al comienxo, el número de Ies es 1, que no es divisible por 3.
Doblar un número que no es divisible por 3 no lo hace divisible por 3.
Restar 3 de un número que no es divisible por 3 tampoco lo hace divisible por 3.
Entonces, el objetivo MU, con cero Ies, no se puede conseguir porque 0 es divisible por 3.

El axioma MI tiene una I

La regla 2 duplica el número de Ies

La regla 3 elimina 3n Ies

La regla 2 duplica el número de Ies

La regla 3 elimina 3n Ies

(32)

(20,23,26,29,32)

(20,22,23,26,28,29,32,34)

(20,22,23,25,26,28,29,31,32,34)

el número de Ies no puede ser divisible por 3

Douglas R. Hofstadter,
“Gödel, Escher, Bach: an Eternel Golden Braid”,
Basic Books, 1979

3 maneras: Mechanical mode
I ntelligent mode
U n-mode

El modo Mecánico aplica las reglas hasta que aparezca MU… ¡o por toda la
eternidad si MU no aparece!

El modo Inteligente aplica un meta-formalismo para demostrar que MU no es
posible en el sistema MIU.
¿Y el Un-mode?
El término Japonés y Koreano mu (Japones: 無; Koreano: 무) o Chino wu (chino
tradicional: 無; chino simplificado: 无) significa “No tener”, “Sin”. Es una palabra clave en el Budismo,
especialmente en la tradición Zen

¡El modo del Zen!

Algunas traducciones: “no”, “nada”, “sin”, “No existencia”, “no ser”, “no tener”, “falta de”, “imposible”, “sin razón
ni causa”, “pura conciencia humana”, “anterior a la experiencia del conocimiento”. El Zen dice que la palabra
MU es “la puerta a la iluminación". Por eso el koan MU se considera hosshin 発心 "resuélvase para obtener la
iluminación", esto es, es apropiado para principiantes en busca de kenshō (en busca de la “naturaleza Buda”).

Un colección de koanes del siglo 13 usa la palabra MU en su título (Mumonkan 無門關). El primer koan es “el perro de Joshu” 趙州狗子.

Un monje pregunto al maestro Zen Jōshū “¿Tiene un perro naturaleza Buda?” Jōshū repondió “Mu"

Douglas R. Hofstadter,
“Gödel, Escher, Bach: an Eternel Golden Braid”,
Basic Books, 1979

3 maneras: Mechanical mode
I ntelligent mode
U n-mode

El modo Mecánico aplica las reglas hasta que aparezca MU… ¡o por toda la
eternidad si MU no aparece!

El modo Inteligente aplica un meta-formalismo para demostrar que MU no es
posible en el sistema MIU.

El Un-modo permite que la demostración emerja como la
“iluminación” que proviene de la “nada”.

Sistemas formales como números

Un sistema formal consiste de los símbolos {3, 1, 0} y algunas reglas gramaticales para

construir cadenas válidas a partir de otras conocidas con anterioridad:

Axioma : 31
Reglas gramaticales : 1. Si 10k+1, entonces 10(10k+1)

(donde k, m, n  N y n < 10m)



2. Si 310m+n, entonces 10m(310m+n) + n

3. Si k10m+3+11110m+n, entonces k10m+1+n



4. Si k10m+2+n, entonces k10m+n

Tarea : Demuestre 30, si es posible

Algunos sistemas formales como estos
usados en el modelado matemático de
sistemas complejos

Sistemas-L:
Gramática Formal
y Re-escritura



Chomsky

Gramática formal
Re-escribir para describir

las características

sintácticas del lenguaje

natural (1950’s)



Backus y Naur

Notación basada en re-

escritura

Definición formal de los
lenguajes de programación

(Algol, 1960’s)



El reconocimiento de su

equivalencia inició un

período de fascinación con
la sintaxis, la gramática y
su aplicación a la ciencia de

la computación



Sistemas-L: Re-escritura

• Un árbol crece desde una semilla: ¿Cómo se pueden generar

nuevas células a partir de las células viejas?

• La semilla se conoce como un axioma
• Las instrucciones para hacer crecer nuevas células se conocen

como reglas de producción

• Por ejemplo,

Axioma : B

Reglas : BF-B+B, FFF

Cadena

B

F-B+B

FF-(F-B+B)+(F-B+B)

FFFF-(FF-(F-B+B)+(F-B+B))+(FF-(F-B+B)+(F-B+B))

Nivel

0

1

2

3

Sistemas-L: Re-escritura

F

F

B

F

F

F

F

F

F

F

Sistemas L

Aristid Lindenmayer, 1925 - 1989

En muchos procesos de crecimiento de organismos
vivos, especialmente de plantas, se puede notar
fácilmente
la aparición de ciertas estructuras
multicelulares que se repiten regularmante.... En el
caso de una hoja compuesta, por