La función de Ackermann, utilizada en la teoría de la computación, es una función recursiva que toma dos números naturales como argumentos y devuelve un número natural.

Definición

---

La función de Ackermann se define por recursividad como sigue:

$$

A(m,n)= \begin{cases} n+1, &\mbox{si }m=0; \\ A(m-1, 1), &\mbox{si }m>0\mbox{ y }n=0; \\ A(m-1, A(m, n-1)), &\mbox{si }m>0\mbox{ y }n>0 \end{cases}

Recursiva, pero no recursiva primitiva

---

La definición formal se construye a partir de funciones recursivas primitivas.

Se comienza con la siguente sucesión de funciones:

$f\_\{0\}(x)\; =\; s(x)$

$f\_\{1\}(x)\; =\; f\_\{0\}^\{x+2\}(x)\; =\; s^\{x+2\}(x)$

$f\_\{2\}(x)\; =\; f\_\{1\}^\{x+2\}(x)\; =\; (s^\{x+2\})^\{x+2\}(x)$

$f\_\{k\}(x)\; =\; f\_\{k\}^\{x+2\}(x)$

Donde $s(x)$ es la función sucesor y $f^\{n\}(x)$ es la función potencia (aquella que aplica f n veces).

Propiedades de la función de Ackermann

---

• $Sea\; \backslash ;\; k\; \backslash in\; \backslash mathbb\{N\}\; ,\backslash ;\; f\_\{k\}\; \backslash in\; FRP$

• $Sea\; \backslash ;\; a\; >\; b\; ,\backslash ;\; f\_\{k\}(a)\; >\; f\_\{k\}(b)$

• $Sea\; \backslash ;\; x,k\; \backslash in\; \backslash mathbb\{N\}\; ,\backslash ;\; f\_\{k\}(x)\; >\; x$

• $Sea\; \backslash ;\; k\; \backslash in\; \backslash mathbb\{N\}\; ,\backslash ;\; f\_\{k+1\}(x)\; >\; f\_\{k\}(x)$

Además la función de Ackerman ($ACK(x)\; =\; f\_\{x\}(x)$) no es FRP. La demostración de este teorema es por el absurdo y utilizando el lema que toda función recursiva primitiva está mayorada por una función Ackermann.

Comenzamos suponiendo que $ACK(x)\; \backslash in\; FRP$, por tanto $ACK(x)+1\; \backslash in\; FRP$

Usando el lema de la mayoración, debe existir un k tal que $ACK(x)+1\; \backslash le\; f\_\{k\}(x)$

Pero entonces como esto vale para todo x, también valdrá para x=k

$ACK(k)+1\; \backslash le\; f\_\{k\}(k)$, usando la definición, llegamos a que:

$ACK(k)+1\; \backslash le\; ACK(k)$

Lo cual es absurdo.

Esta función crece extremadamente rápido A(4,2) ya tiene 19.729 dígitos. Este crecimiento desmesurado se puede utilizar para demostrar que la función computable f(n) = A(n, n) crece más rápido que cualquier función recursiva primitiva, y por ello no es recursiva primitiva.

Tabla de Valores

---

{| border="1" cellpadding="2" Números de $A(m\{,\}n)$

---

-

! m\n 0 1 2 3 4 n

---

- 0 1 2 3 4 5 n + 1

---

- 1 2 3 4 5 6 n + 2

---

- 2 3 5 7 9 11 2n + 3

---

- 3 5 13 29 61 125 $8\backslash cdot\; 2^n-3$

---

- 4 13 65533 $2^\{65536\}-3\; \backslash approx\; 2\; \backslash cdot\; 10^\{19728\}$  A(3,2⁶⁵⁵³⁶-3) A(3,A(4,3)) $2^\{2^\{\backslash dots^2\}\}-3$ ($n+3$ términos)

---

- 5 65533 A(4,65533) A(4,A(5,1)) A(4,A(5,2)) A(4,A(5,3))

---

- 6 A(5,1) A(5,A(5,1)) A(5,A(6,1)) A(5,A(6,2)) A(5,A(6,3))

Para darse una idea de la magnitud de los valores que aparecen de la fila 4 en adelante, se puede destacar que por ejemplo, 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. En general, por debajo de la fila 4, ya no es posible escribir todos los dígitos del resultado de la función.

Explicación intuitiva

---

La primera fila de la función de Ackerman contiene los enteros positivos, dado que A(0, n)) consiste en sumar uno a n. El resto de las filas se pueden ver como indirecciones hacia la primera. En el caso de m = 1, se redirecciona hacia A(0, n + 1), sin embargo, la simplificación es algo complicada:

$=\; A\; \backslash ,(0,\; A(1,1))$

$=\; A\; \backslash ,(0,\; A(0,\; A(1,0)))$

$=\; A\; \backslash ,(0,\; A(0,\; 2))$

$=\; A\; \backslash ,(0,\; 3)$

$=\; 4\; \backslash ,$

Se puede intentar con una caso algo más complicado— como A(4, 3); el primer valor que no cabe en el universo físico.

$=\; A\; \backslash ,\; (3,\; A(4,\; 2))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(4,\; 1)))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(4,\; 0))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(3,\; 1))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(3,\; 0)))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(2,\; 1)))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; A(2,\; 0))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; A(1,\; 1))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; A(0,\; A(1,\; 0)))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; A(0,\; A(0,\; 1)))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; A(0,\; 2))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(1,\; 3)))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(1,\; 2))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(0,\; A(1,\; 1)))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(0,\; A(0,\; A(1,\; 0))))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(0,\; A(0,\; A(0,\; 1))))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(0,\; A(0,\; 2))))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; A(0,\; 3)))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; A(0,\; 4)))))$

$=\; A\; \backslash ,\; (3,\; A(3,\; A(3,\; A(2,\; 5))))$

Para seguir calculando este valor, habría que encontrar que A(2, 5) vale 13, luego evaluar A(3, 13), que es 8179. Sin embargo, el valor de A(3, 8179) es comparable al número de átomos del Universo elevado a una potencia de más de 12. Ese número tendría que calcularse para hacer la llamada más externa a la función, pero ya no sería posible escribir los dígitos del resultado en el universo físico.

Todo esto por composición de la única operación aritmética que se utiliza, es decir, el incremento en uno de un valor (en el cálculo de A(0, n)).

Descripción explícita

---

Intuitivamente, la función de Ackermann define la generalización de la multiplicación por dos (sumas iteradas) y la exponenciación con base 2 (productos iterados) hasta la exponenciación iterada, la iteración de la exponenciación iterada, la iteración de la operación anterior, etc. Puede expresarse de forma concisa y no recursiva mediante la notación de flecha de Conway:

$A(m,n)=2\backslash rightarrow\; (n+3)\backslash rightarrow\; (m-2)-3$

o los hiper operadores:

$A(m,n)=\backslash mathrm\{hyper\}(2,m,n+3)-3\; \backslash ;$

Historia

---

En 1928, Wilhelm Ackermann consideró una función A(m, n, p) de tres variables: m → n → p en la notación de Conway. Ackermann demostró que se trata de una función recursiva que no es primitiva recursiva. Esa definición fue simplificada por Rozsa Peter y Raphael Robinson en la versión de dos variables dada al principio.

Análisis de algoritmos

---

Así como la función diagonal  f (n) = A(n, n) crece muy rápidamente, su inversa crece muy lentamente y se utiliza frecuentemente en análisis de algoritmos. En ese contexto, se suele redefinir la función de Ackermann por otra de comportamiento asintótico similar, pero evitando los términos −3, o partiendo de la potencias de 2 para la fila 0 (lo que equivale a omitir las tres primeras filas). Si bien el resultado de estas variantes no es idéntico al de la función original, se pueden ver como similares al ser posible acotar la diferencia. En el caso de la inversa de la función diagonal, su resultado es inferior a 4 para entradas de prácticamente cualquier tamaño, de manera que se asimila a una función constante.

Medida de comparación

---

Debido a su definición, profundamente recursiva, la función de Ackermann se utiliza con frecuencia para comparar compiladores en cuanto a su habilidad para optimizar la recursión. Por ejemplo, un compilador capaz de notar que A(3, 30) se puede calcular en base a potencias de 2, o que guarda resultados intermediarios tales como A(3, n) y A(2, n) en lugar de recalcularlos cada vez, ahorraría tiempo de ejecución por un factor de 100 o 1000. Igualmente, al calcular directamente A(1, n) en lugar de hacer una llamada recursiva se realizan ahorros significativos.

Es posible calcular el término A(4, 2) pero no recursivamente, sino por otros medios.

Código C

---

{| align=left

int ackerman(int M, int N)

{

int temp;

if(M == 0)

{

temp = N + 1;

}

else

{

if (N == 0)

{

temp = ackerman(M-1,1);

}

else

{

temp = ackerman(M-1,ackerman(M,N-1));

}

}

return(temp);

}

Código de Haskell

---

ack 0 n = n + 1

ack m 0 = ack (m - 1) 1

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

Bibliografía

---

• Ackermann, Wilhelm: Zum Hilbertschen Aufbau der reelen Zahlen. Math. Annalen 99 (1928), pp. 118-133.
• von Heijenoort, J. (ed.): From Frege to Gödel: A Source Book in Mathematical Logic. Cambridge: Harvard University Press, 1967. Disponible en línea.
• Kozen, Dexter C.: The Design and Analysis of Algorithms. Springer, 1992.
• Robinson, Raphael M.: Recursion and double recursion. Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.
• Schöning, Uwe: Theoretische Informatik – kurzgefasst. Spektrum Akademischer. ISBN 3-8274-1099-1
• Sundblad, Yngve: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. BIT 11 (1971), 107-119.

Enlaces externos

---

• Some values of the Ackermann function.
• Example use of the Ackermann function as a benchmark.
• La expansión decimal de A(4,2)

Teoría de números | Computabilidad

Ackermannova funkce | Ackermannfunktion | Ackermann function | Fonction d'Ackermann | Ackermann-függvény | アッカーマン関数 | Ackermannfunctie | Funkcja Ackermanna | Ackermann işlevi | Hàm số Ackermann | 阿克曼函數