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.

1 Comments:

At 10/3/06 14:18, Anonymous lola said...

tío....pero para explicarlo te pasas la vida.... yo creo que habría puesto 9^9^9^9^9..... y así...lo que me dejaran.

p.s. tío petros, eh? :P

 

Publicar un comentario

Links to this post:

Crear un enlace

<< Home