UTNianos

Hablando de nerdeadas en el trabajo, un compañero nos mostró la función de Ackermann, y tratamos de probar algunos valores haciendo el algoritmo en nuestra herramienta diaria (Smalltalk).

\[A(m;n)\begin{cases}n+1 & \text{ if } m=0 \\ A(m-1;1) & \text{ if } m>0 \wedge n=0 \\ A(m-1;A(m;n-1)) & \text{ if } m>0 \wedge n>0\end{cases}\]

Lo loco es que para valores 0, 1 o 2 es relativamente sencillo de calcularlo mentalmente. Después de empieza a complicar la cosa.

Cuando el primer parámetro de la función (m) llega a 4, se va todo a la mierda. Mientras tanto el segundo parámetro (digamos n) puede crecer hasta 8 sin problema. Ya a partir de 9 empieza a complicarse la cosa.

Acá les dejo una implementación en Smalltalk.

 | ack |



ack := [:m :n :function | 

	m = 0

		ifTrue: [ n+1 ]

		ifFalse: [ n= 0

			ifTrue: [ function value: (m-1) value: 1 value: function] 

			ifFalse: [ function value: (m-1) value: (function value: m value: (n-1) value: function) value: function]]].



0 to: 3 do: [ :m |

	0 to: 8 do: [ : n | |start|

		start := Time millisecondClockValue.

		Transcript 

			show: ('A( %1 ; %2 ) = %3' bindWith: m printString with: n printString with: (ack value: m value: n value: ack) printString);

			tab; tab; tab;

			show: ('time %1 ms' bindWith: (Time millisecondClockValue - start));

			cr

	]

]

En Wikipedia está el detalle con la implementación en varios lenguajes. Si alguno se anima a probar A(4;1) y calcular el tiempo que tarda (deberían ser unos 10 minutos) cuéntenos cómo le fue.

"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 no cabría en el Universo físico."

Ja, ja. Es tan grande, que no entra ni en el universo.

 

ack 0 n = n + 1

ack m 0 = ack (m - 1) 1

ack m n = ack (m - 1) (ack m (n - 1))



main = print $ ack 4 2

---

ehm, copiar y pegar de wikipedia no sirvio, despues lo arreglo

---

ahora si, se rompe