Converso

Los conversos son los peores. Te dan la lata sobre cualquier argumento, en particular sobre ordenadores, tabaco y estilo de vida, por no hablar de la moral y de lo mucho que les putea la otra gente. Así que allá tú, ya puedes ir a hacer cosas más interesantes.

23 febrero 2006

La diagonal de Ackermann

Inspirado en un post en otro blog, os cuento unas cosillas. La pregunta clave es: "¿Cómo puedo expresar múmeros muy muy grandes?". Por ejemplo, cómo expresar el número más grande posible usando sólo, digamos, seis símbolos?

Si consideramos que la operación de exponenciación se prioriza a la derecha (en el sentido que a^b^c quiere decir a^(b^c) ), entonces la respuesta podría ser 9^9^99, que es un entero con un montón de millones de dígitos.

Bueno, se puede hacer más. Gracias a mi amiga Wikipedia, os cuento como.

Definamos la función A(m,n) recursivamente, según la siguiente regla:
  • A(0,n)=n+1

  • A(m,0)=A(m-1,1)

  • A(m,n)=A(m-1,A(m,n-1))


Así podemos calcular A(1,n)=2+(n+3)-3 y A(2,n)=2(n+3)-3. Luego, con alguna dificultad, se llega a A(3,n)=2^(n+3)-3 y hasta se puede calcular que A(4,n)=2^2^...^2^2-3 (donde aparecen exactamente n+3 cifras 2).

De alguna forma, la fila 1 representa la operación "suma", la 2 el "producto", la 3 una "exponencial", ¿¿¿ y la 4 ??? ¿¿¿¿¿¿ y la 5 ??????
Los indios representaban tres operaciones de rango superior a la exponencial, que llamaban "cuadrado" "redondo" y "triangulo" (no me acuerdo el orden). Por ejemplo, cuadrado(3)=3^3^3, mientras que redondo(3)=cuadrado(cuadrado(cuadrado(3))), y asimismo triángulo(3)=redondo(redondo(redondo(3))). las filas 4, 5 y 6 de la tabla de Ackermann corresponden más o menos con dichas operaciones.

Supongo que a alguien se le puede ocurrir la idea de intentar calcular explícitamente alguno de estos números. Tengan cuidado, ¡pobres ilusos!, que A(4,2) es mayor que el número de partículas que forman el universo elevado a la potencia 200 y el resultado de A(5,2) no se puede escribir dado que tiene más dígitos que partículas el universo.

Un ejercicio interesante es intentar ver como crece la función a(n)=A(n,n).

a(0)=A(0,0)=1
a(1)=A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3
a(2)=A(2,2)=A(1,A(2,1))=A(1,A(1,A(2,0)))=A(1,A(1,A(1,1)))=A(1,A(1,3))=A(1,A(0,A(1,2)))=A(1,A(0,A(0,A(1,1))))=A(1,A(0,A(0,3)))=A(1,A(0,4))=A(1,5)=A(0,A(1,4))=A(0,A(0,A(1,3)))=A(0,A(0,A(0,A(1,2))))=A(0,A(0,A(0,A(0,A(1,1)))))=A(0,A(0,A(0,A(0,3))))=A(0,A(0,A(0,4)))=A(0,A(0,5))=A(0,6)=7
a(3)=A(3,3)=A(2,A(3,2))= ... =A(2,29)= ... = 61
a(4)=A(4,4)=A(3,A(4,3))= ... =2222222-3
a(5)=??????????????????????? (ni me atrevo a estimar la cantidad de dígitos que puede tener...)

Resulta, al final, que la funcion a(n) crece más de cualquier función primitiva recursiva, y prácticamente todas las funcione razonables son de tipo primitivo recursivo.

Así que con seis símbolos, yo escribo a(999) y gano.

03 febrero 2006

Silvano

Amami, amami, stringimi, sgonfiami
e amami, sdentami, stracciami, applicami
e dopo stringimi, dammi l'ebrezza dei tendini
prendimi, con le tue labbra accarezzami.
Rino, non riconosco gli aneddoti
e schiodami, spostami tutte le efelidi
aprimi, picchiami solo negli angoli,
brivido, no non distinguo più i datteri.

Silvano e non valevo le ciccioli
Silvano mi hai lasciato sporcandomi
e la gira la gira la ruota la gira
e la gira la gira la ruota la gira
e la storia del nostro impossibile amore continua anche senza di te.

E amami, amami, stringimi, sgonfiami
e allora amami, sdentami, stracciami, applicami
e stringimi, dammi l'ebrezza dei tendini
prendimi, con le tue labbra fracassami.
Rino, sfodera scuse plausibili,
girati, scaccia il bisogno del passero,
lurido, soffiati il naso col pettine,
Everest, sei la mia vetta incredibile.

Silvano, e non valevo le ciccioli
Silvano mi hai lasciato sporcandomi
e la gira la gira la ruota la gira
e la gira la gira la ruota la gira
e la storia del nostro impossibile amore continua anche senza di te

enzo jannacci