función de Ackermann

La función original de tres argumentos de Ackermann${\displaystyle \varphi (m,n,p)}$se define recursivamente de la siguiente manera para enteros no negativos${\displaystyle m,n,}$y${\displaystyle p}$:

$${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{para }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{para }}n,p>0\end{aligned}}}$$

De las diversas versiones de dos argumentos, la desarrollada por Péter y Robinson (denominada "la" función de Ackermann por la mayoría de los autores) está definida para enteros no negativos.${\displaystyle m}$y${\displaystyle n}$como sigue:

$${\displaystyle {\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}}}$$

La función de Ackermann también se ha expresado en relación con la secuencia de hiperoperación : ^{[ 14 ] [ 15 ]}

$${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}$$

o, escrito en la notación de flecha hacia arriba de Knuth (extendida a índices enteros)${\displaystyle \geq -2}$):

$${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}}$$

o, equivalentemente, en términos de la función F de Buck: ^{[ 10 ]}

$${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}$$

Por inducción en${\displaystyle m}$, se puede demostrar que${\displaystyle F(m,n)\leq A(m,n)}$a pesar de${\displaystyle m,n\in \mathbb {N} _{0}}$.

Definir${\displaystyle f^{n}}$como la n -ésima iteración de${\displaystyle f}$:

$${\displaystyle {\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\end{array}}}$$

La iteración es el proceso de componer una función consigo misma un cierto número de veces. La composición de funciones es una operación asociativa , por lo que${\displaystyle f(f^{n}(x))=f^{n}(f(x))}$.

Concibiendo la función de Ackermann como una secuencia de funciones unarias, se puede establecer${\displaystyle \operatorname {A} _{m}(n)=\operatorname {A} (m,n)}$.

La función se convierte entonces en una secuencia${\displaystyle \operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...}$de funciones unarias ^{[ n 2 ]} , definidas a partir de la iteración :

$${\displaystyle {\begin{array}{lcl}\operatorname {A} _{0}(n)&=&n+1\\\operatorname {A} _{m+1}(n)&=&\operatorname {A} _{m}^{n+1}(1)\,.\end{array}}}$$

Las funciones${\displaystyle \operatorname {A} _{i}}$encajar en la jerarquía de crecimiento rápido (FGH) ( de nivel finito) de funciones ^{[ 16 ]}

$${\displaystyle {\begin{array}{lcl}\operatorname {FGH} _{0}(n)&=&n+1\\\operatorname {FGH} _{m+1}(n)&=&\operatorname {FGH} _{m}^{n}(n)\,.\end{array}}}$$

Se cumple la siguiente desigualdad: ^{[ 17 ]}$${\displaystyle \forall m>1,\forall n>1:\operatorname {A} _{m}(n)<\operatorname {FGH} _{m}(n)}$$

Para fijo${\displaystyle k}$, la función${\displaystyle \operatorname {FGH} _{k}(n)}$puede calcularse mediante un programa LOOP de profundidad de anidamiento${\displaystyle k}$: ^{[ 18 ]}

# ENTRADA (n) BUCLE n : # profundidad de anidamiento: 1 BUCLE n : # profundidad de anidamiento: 2 ... # ... BUCLE n : # profundidad de anidamiento: k n += 1 # # SALIDA (n)

La función${\displaystyle \operatorname {A} _{k}(n)}$También se puede calcular mediante un programa LOOP-k. ^{[ 19 ]} (El programa (esquema) no se incluye aquí).

Es obvio que${\displaystyle \operatorname {A} (m,n)}$, al no ser una función recursiva primitiva —véase más abajo— , no puede ser calculada por un programa LOOP.

La definición recursiva de la función de Ackermann se puede transponer naturalmente a un sistema de reescritura de términos (TRS) .

La definición de la función de Ackermann 2-aria conduce a las reglas de reducción obvias ^{[ 20 ] [ 21 ].}

$${\displaystyle {\begin{array}{lll}{\text{(r1)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r2)}}&A(S(m),0)&\rightarrow &A(m,S(0))\\{\text{(r3)}}&A(S(m),S(n))&\rightarrow &A(m,A(S(m),n))\end{array}}}$$

Ejemplo

Calcular${\displaystyle A(1,2)\rightarrow _{*}4}$

La secuencia de reducción es ^{[ n 3 ]}

Para calcular${\displaystyle \operatorname {A} (m,n)}$se puede usar una pila , que inicialmente contiene los elementos${\displaystyle \langle m,n\rangle }$.

Luego, los dos elementos superiores se reemplazan repetidamente según las reglas ^{[ n 4 ].}

$${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&n&\rightarrow &(n+1)\\{\text{(r2)}}&(m+1)&,&0&\rightarrow &m&,&1\\{\text{(r3)}}&(m+1)&,&(n+1)&\rightarrow &m&,&(m+1)&,&n\end{array}}}$$

Esquemáticamente, comenzando desde${\displaystyle \langle m,n\rangle }$:

MIENTRAS stackLength <> 1 { POP 2 elementos; PUSH 1 o 2 o 3 elementos, aplicando las reglas r1, r2, r3. }

El pseudocódigo se publica en Grossman & Zeitman (1988) .

Por ejemplo, en la entrada${\displaystyle \langle 2,1\rangle }$,

Observaciones

• La estrategia leftmost-innermost está implementada en 225 lenguajes de programación en Rosetta Code .
• A pesar de${\displaystyle m,n}$el cálculo de${\displaystyle A(m,n)}$no toma más de${\displaystyle (A(m,n)+1)^{m}}$pasos. ^{[ 22 ]}
• Grossman y Zeitman (1988) señalaron que en el cálculo de${\displaystyle \operatorname {A} (m,n)}$La longitud máxima de la pila es${\displaystyle \operatorname {A} (m,n)}$, mientras${\displaystyle m>0}$.

  Su propio algoritmo, inherentemente iterativo, calcula${\displaystyle \operatorname {A} (m,n)}$dentro${\displaystyle {\mathcal {O}}(m\operatorname {A} (m,n))}$tiempo y dentro${\displaystyle {\mathcal {O}}(m)}$espacio.

La definición de las funciones de Ackermann 1-arias iteradas conduce a diferentes reglas de reducción.

$${\displaystyle {\begin{array}{lll}{\text{(r4)}}&A(S(0),0,n)&\rightarrow &S(n)\\{\text{(r5)}}&A(S(0),S(m),n)&\rightarrow &A(S(n),m,S(0))\\{\text{(r6)}}&A(S(S(x)),m,n)&\rightarrow &A(S(0),m,A(S(x),m,n))\end{array}}}$$

Como la composición de funciones es asociativa, en lugar de la regla r6 se puede definir

$${\displaystyle {\begin{array}{lll}{\text{(r7)}}&A(S(S(x)),m,n)&\rightarrow &A(S(x),m,A(S(0),m,n))\end{array}}}$$

Al igual que en la sección anterior, el cálculo de${\displaystyle \operatorname {A} _{m}^{1}(n)}$se puede implementar con una pila.

Inicialmente, la pila contiene los tres elementos.${\displaystyle \langle 1,m,n\rangle }$.

Luego, los tres elementos superiores se reemplazan repetidamente según las reglas ^{[ n 4 ].}

$${\displaystyle {\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}}$$

Esquemáticamente, comenzando desde${\displaystyle \langle 1,m,n\rangle }$:

MIENTRAS stackLength <> 1 { POP 3 elementos; PUSH 1 o 3 o 5 elementos, aplicando las reglas r4, r5, r6; }

Ejemplo

En la entrada${\displaystyle \langle 1,2,1\rangle }$las configuraciones de pila sucesivas son

$${\displaystyle {\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r6}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r6}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r6}1,0,{\underline {3,0,1}}\rightarrow _{r6}1,0,1,0,{\underline {2,0,1}}\\&\rightarrow _{r6}1,0,1,0,1,0,{\underline {1,0,1}}\rightarrow _{r4}1,0,1,0,{\underline {1,0,2}}\rightarrow _{r4}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$$

Las igualdades correspondientes son

$${\displaystyle {\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1))=A_{0}(A_{0}(A_{0}^{2}(1)))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1))))=A_{0}(A_{0}(A_{0}(2)))=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}}$$

Cuando se utiliza la regla de reducción r7 en lugar de la regla r6, los reemplazos en la pila seguirán

$${\displaystyle {\begin{array}{lllllllll}{\text{(r7)}}&(x+2)&,m&,n&\rightarrow &(x+1)&,m&,1&,m&,n\end{array}}}$$

Las configuraciones sucesivas de la pila serán entonces

$${\displaystyle {\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r7}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r7}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r7}3,0,{\underline {1,0,1}}\rightarrow _{r4}{\underline {3,0,2}}\\&\rightarrow _{r7}2,0,{\underline {1,0,2}}\rightarrow _{r4}{\underline {2,0,3}}\rightarrow _{r7}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$$

Las igualdades correspondientes son

$${\displaystyle {\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1))=A_{0}^{3}(2)\\&=A_{0}^{2}(A_{0}(2))=A_{0}^{2}(3)=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}}$$

Observaciones

• Para cualquier entrada dada, los TRS presentados hasta ahora convergen en el mismo número de pasos. También utilizan las mismas reglas de reducción (en esta comparación, las reglas r1, r2, r3 se consideran "iguales a" las reglas r4, r5, r6/r7 respectivamente). Por ejemplo, la reducción de${\displaystyle A(2,1)}$converge en 14 pasos: 6 × r1, 3 × r2, 5 × r3. La reducción de${\displaystyle A_{2}(1)}$converge en los mismos 14 pasos: 6 × r4, 3 × r5, 5 × r6/r7. Los TRS difieren en el orden en que se aplican las reglas de reducción.
• Cuando${\displaystyle A_{i}(n)}$se calcula siguiendo las reglas {r4, r5, r6}, la longitud máxima de la pila permanece por debajo${\displaystyle 2\times A(i,n)}$Cuando se utiliza la regla de reducción r7 en lugar de la regla r6, la longitud máxima de la pila es solo${\displaystyle 2(i+2)}$. La longitud de la pila refleja la profundidad de recursión. Como la reducción según las reglas {r4, r5, r7} implica una profundidad máxima de recursión menor, ^{[ n 6 ]} este cálculo es más eficiente en ese sentido.

Como Sundblad (1971) —o Porto y Matos (1980) — demostraron explícitamente, la función de Ackermann puede expresarse en términos de la secuencia de hiperoperaciones :

$${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}$$

o, después de eliminar la constante 2 de la lista de parámetros, en términos de la función de Buck

${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}$

La función de Buck${\displaystyle \operatorname {F} (m,n)=2[m]n}$, ^{[ 10 ]} una variante de la función de Ackermann por sí misma, se puede calcular con las siguientes reglas de reducción:

$${\displaystyle {\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}}$$ En lugar de la regla b6 se puede definir la regla

$${\displaystyle {\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}}$$ Para calcular la función de Ackermann basta con añadir tres reglas de reducción.

$${\displaystyle {\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}}&P(S(S(S(m))))&\rightarrow &m\\\end{array}}}$$

Estas reglas se encargan del caso base.${\displaystyle A(0,n)}$, la alineación${\displaystyle (n+3)}$y el dulce de leche (-3).

Ejemplo

Calcular${\displaystyle A(2,1)\rightarrow _{*}5}$

Las igualdades coincidentes son

• cuando el TRS con la regla de reducción${\displaystyle {\text{b6}}}$se aplica:

$${\displaystyle {\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F(0,F^{5}(0,2))=F(0,F(0,F^{4}(0,2)))\\&=F(0,F(0,F(0,F^{3}(0,2))))=F(0,F(0,F(0,F(0,F^{2}(0,2)))))=F(0,F(0,F(0,F(0,F(0,F(0,2))))))\\&=F(0,F(0,F(0,F(0,F(0,3)))))=F(0,F(0,F(0,F(0,4))))=F(0,F(0,F(0,5)))=F(0,F(0,6))=F(0,7)=8\end{aligned}}}$$

• cuando el TRS con la regla de reducción${\displaystyle {\text{b7}}}$se aplica:

$${\displaystyle {\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F^{5}(0,F(0,2))=F^{5}(0,3)=F^{4}(0,F(0,3))=F^{4}(0,4)\\&=F^{3}(0,F(0,4))=F^{3}(0,5)=F^{2}(0,F(0,5))=F^{2}(0,6)=F(0,F(0,6))=F(0,7)=8\end{aligned}}}$$Observaciones

• El cálculo de${\displaystyle \operatorname {A} _{i}(n)}$Según las reglas {b1 ​​- b5, b6, r8 - r10} es profundamente recursivo. La profundidad máxima de anidamiento${\displaystyle F}$s es${\displaystyle A(i,n)+1}$El problema radica en el orden en que se ejecuta la iteración:${\displaystyle F^{n+1}(x)=F(F^{n}(x))}$. La primera${\displaystyle F}$desaparece solo después de que se haya desplegado toda la secuencia.
• El cálculo según las reglas {b1 ​​- b5, b7, r8 - r10} es más eficiente en ese sentido. La iteración${\displaystyle F^{n+1}(x)=F^{n}(F(x))}$simula el bucle repetido sobre un bloque de código. ^{[ n 7 ]} El anidamiento está limitado a${\displaystyle (i+1)}$, un nivel de recursión por función iterada. Meyer y Ritchie (1967) demostraron esta correspondencia.
• Estas consideraciones se refieren únicamente a la profundidad de recursión. Cualquiera de las formas de iterar conduce al mismo número de pasos de reducción, que involucran las mismas reglas (cuando las reglas b6 y b7 se consideran "iguales"). La reducción de${\displaystyle A(2,1)}$Por ejemplo, converge en 35 pasos: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10. El modus iterandi solo afecta el orden en que se aplican las reglas de reducción.
• Una ganancia real en el tiempo de ejecución solo se puede lograr al no recalcular los subresultados una y otra vez. La memorización es una técnica de optimización donde los resultados de las llamadas a funciones se almacenan en caché y se devuelven cuando se producen las mismas entradas. Véase, por ejemplo, Ward (1993) . Grossman y Zeitman (1988) publicaron un ingenioso algoritmo que calcula${\displaystyle A(i,n)}$dentro${\displaystyle {\mathcal {O}}(iA(i,n))}$tiempo y dentro${\displaystyle {\mathcal {O}}(i)}$espacio.

Para demostrar cómo se realiza el cálculo de${\displaystyle A(4,3)}$da como resultado muchos pasos y en gran número: ^{[ n 5 ]}

$${\displaystyle {\begin{aligned}A(4,3)&\rightarrow A(3,A(4,2))\\&\rightarrow A(3,A(3,A(4,1)))\\&\rightarrow A(3,A(3,A(3,A(4,0))))\\&\rightarrow A(3,A(3,A(3,A(3,1))))\\&\rightarrow A(3,A(3,A(3,A(2,A(3,0)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,4)))))\\&\rightarrow A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}}$$

• Puede que no sea inmediatamente obvio que la evaluación de${\displaystyle A(m,n)}$siempre termina. Sin embargo, la recursión está limitada porque en cada aplicación recursiva${\displaystyle m}$disminuye o${\displaystyle m}$permanece igual y${\displaystyle n}$disminuye. Cada vez que${\displaystyle n}$llega a cero,${\displaystyle m}$disminuye, por lo tanto${\displaystyle m}$eventualmente también llega a cero. (Expresado de manera más técnica, en cada caso el par${\displaystyle (m,n)}$disminuye en el orden lexicográfico en pares, que es un buen ordenamiento , al igual que el ordenamiento de enteros no negativos individuales; esto significa que no se puede descender en el ordenamiento infinitas veces consecutivas. Sin embargo, cuando${\displaystyle m}$disminuye no hay límite superior en cuánto${\displaystyle n}$puede aumentar, y a menudo aumentará considerablemente.
• Para valores pequeños de m como 1, 2 o 3, la función de Ackermann crece relativamente lento con respecto a n (como máximo exponencialmente ).${\displaystyle m\geq 4}$Sin embargo, crece mucho más rápido; incluso${\displaystyle A(4,2)}$es aproximadamente 2,00353 × 10^{19 728} y la expansión decimal de${\displaystyle A(4,3)}$es muy grande según cualquier medida típica, aproximadamente 2,12004 × 10 ^{6,03123 × 1019 727} .
• Un aspecto interesante es que la única operación aritmética que utiliza es la suma de 1. Su rápido crecimiento se basa exclusivamente en la recursión anidada. Esto implica que su tiempo de ejecución es al menos proporcional a su resultado, por lo que también es extremadamente grande. En realidad, en la mayoría de los casos, el tiempo de ejecución es mucho mayor que el resultado; véase más arriba.
• Una versión de un solo argumento${\displaystyle f(n)=A(n,n)}$que aumenta ambos${\displaystyle m}$y${\displaystyle n}$Al mismo tiempo, empequeñece a todas las funciones recursivas primitivas, incluidas las funciones de crecimiento muy rápido como la función exponencial , la función factorial, las funciones multifactoriales y superfactoriales , e incluso las funciones definidas usando la notación de flecha hacia arriba de Knuth (excepto cuando se usa la flecha hacia arriba indexada). Se puede ver que${\displaystyle f(n)}$es aproximadamente comparable a${\displaystyle f_{\omega }(n)}$en la jerarquía de rápido crecimiento . Este crecimiento extremo puede ser explotado para demostrar que${\displaystyle f}$, que obviamente es computable en una máquina con memoria infinita como una máquina de Turing y por lo tanto es una función computable , crece más rápido que cualquier función recursiva primitiva y por lo tanto no es recursiva primitiva.

La función de Ackermann crece más rápido que cualquier función recursiva primitiva y, por lo tanto, no es en sí misma una función recursiva primitiva.

Boceto de prueba :

Las funciones recursivas primitivas se construyen a partir de funciones básicas mediante composición y recursión primitiva, y todas crecen a una determinada tasa. Definimos, de forma constructiva, una jerarquía de funciones totales.${\displaystyle \operatorname {FGH} _{k}(n)}$por:

$${\displaystyle \operatorname {FGH} _{0}(n)=n+1,\quad \operatorname {FGH} _{k+1}(n)=\operatorname {FGH} _{k}^{n}(n)}$$

dónde${\displaystyle \operatorname {FGH} _{k}^{n}}$denota${\displaystyle n}$iteración de pliegues de${\displaystyle \operatorname {FGH} _{k}}$en la entrada${\displaystyle n}$. ^{[ 23 ]} Esta jerarquía crece estrictamente más rápido con el aumento${\displaystyle k}$y toda función recursiva primitiva está finalmente acotada superiormente por algún${\displaystyle \operatorname {FGH} _{k}}$Esto se puede demostrar mediante inducción estructural sobre las definiciones de funciones recursivas primitivas.

Sin embargo, la función de Ackermann${\displaystyle \operatorname {A} (m,n)}$eventualmente supera a todos${\displaystyle \operatorname {FGH} _{k}}$; por cada${\displaystyle k}$, existe${\displaystyle m}$de tal manera que${\displaystyle \operatorname {A} (m,n)>\operatorname {FGH} _{k}(n)}$para todos suficientemente grandes${\displaystyle n}$. De este modo,${\displaystyle \operatorname {A} }$crece más rápido que cualquier función recursiva primitiva y, por lo tanto, no es recursiva primitiva.

La función de Ackermann aparece en la complejidad temporal de algunos algoritmos , ^{[ 26 ]} como los sistemas de suma de vectores ^{[ 27 ]} y la alcanzabilidad de redes de Petri , lo que demuestra que son computacionalmente inviables para instancias grandes. ^{[ 28 ]}

La inversa de la función de Ackermann aparece en algunos resultados de complejidad temporal. Por ejemplo, la estructura de datos de conjuntos disjuntos requiere un tiempo amortizado por operación proporcional a la inversa de la función de Ackermann, ^{[ 29 ]} y no se puede acelerar dentro del modelo de sonda celular de complejidad computacional. ^{[ 30 ]}

Ciertos problemas en geometría discreta relacionados con secuencias de Davenport-Schinzel tienen límites de complejidad en los que la función de Ackermann inversa${\displaystyle \alpha (n)}$aparece. Por ejemplo, para${\displaystyle n}$segmentos de línea en el plano, la cara no delimitada de la disposición de los segmentos tiene complejidad${\displaystyle O(n\alpha (n))}$y algunos sistemas de${\displaystyle n}$Los segmentos de línea tienen una cara de complejidad ilimitada.${\displaystyle \Omega (n\alpha (n))}$. ^{[ 31 ]}

La función de Ackermann, debido a su definición en términos de recursión extremadamente profunda, puede utilizarse como referencia para evaluar la capacidad de un compilador para optimizar la recursión. El primer uso publicado de la función de Ackermann de esta manera fue en 1970 por Dragoș Vaida ^{[ 32 ]} y, casi simultáneamente, en 1971, por Yngve Sundblad ^{[ 14 ] .}

El artículo fundamental de Sundblad fue retomado por Brian Wichmann (coautor del estándar Whetstone ) en una trilogía de artículos escritos entre 1975 y 1982. ^{[ 33 ] [ 34 ] [ 35 ]}