Algoritmo Ackerman

PRESENTACIÓN

INFOGRÁFICA

Logaritmo ackerman

Función de Ackermann

Función de Ackermann

En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales y devuelve un único número natural.

En 1928, Wilhelm Ackermann observó que A(x,y,z), la z-ésima exponenciación iterada de x con y como exponente, es una función recursiva que no es recursiva primitiva. En 1935, Rózsa Péter simplificó A(x,y,z) a una función de dos variables. En 1948, Raphael M. Robinson simplificó la condición inicial, quedando una función doblemente recursiva de N2 en N, definida recursivamente por las tres condiciones siguientes:

Esta última versión es conocida hoy día como la función de Ackermann, el ejemplo más simple de una función total que es computable. O sea, que se puede implementar con ciclos de tipo "While". Pero que no es primitiva recursiva. Por tanto no se puede implementar sólo con ciclos de tipo "For". Esto proporciona un contraejemplo a la creencia de principios del siglo XX de que toda función computable era también recursiva primitiva. Por su definición inicial, la función de Ackermann crece más rápido que cualquier función exponencial, e incluso cualquier función exponencial múltiple.

De hecho, A[4,2] = 22222 − 3 = 265536 − 3 es un número natural con más de 19.000 dígitos en base 10. Aunque correcto y funcional, no permite calcular A[4,2] en un tiempo razonable, en ningún ordenador actual. Sin embargo, el número 265536 − 3 se calcula en segundos. Lo que enlentece el cálculo de la función de Ackermann, es tener que ir de uno en uno hacia atrás y hacia delante varias veces antes de alcanzar el número final, que acaba siendo enumerado muchas veces.

GRACIAS

¡Recuerda publicar!