Función de Ackermann

Ajustar Compartir Imprimir Citar

Función de crecimiento rápido

En la teoría de la computabilidad, la función de Ackermann, llamada así por Wilhelm Ackermann, es uno de los ejemplos más simples y descubiertos más temprano de una función computable total que no es recursiva primitiva. Todas las funciones recursivas primitivas son totales y computables, pero la función de Ackermann ilustra que no todas las funciones computables totales son recursivas primitivas. Después de la publicación de Ackermann de su función (que tenía tres argumentos enteros no negativos), muchos autores la modificaron para adaptarse a varios propósitos, de modo que hoy en día "la función de Ackermann" puede referirse a cualquiera de las numerosas variantes de la función original. Una versión común, la función Ackermann-Péter de dos argumentos, se define de la siguiente manera para los enteros no negativos m y n:

{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}}}

Su valor crece rápidamente, incluso para pequeñas entradas. Por ejemplo, A(4, 2) es un número entero de 19 729 dígitos decimales (equivalente a 2⁶⁵⁵³⁶−3, o 2^{2^{2^2²}}−3).

Historia

A finales de la década de 1920, los matemáticos Gabriel Sudán y Wilhelm Ackermann, estudiantes de David Hilbert, estaban estudiando las bases de la computación. Tanto Sudán como Ackermann se acreditan con el descubrimiento de funciones computables totales (terminadas simplemente "recursivas" en algunas referencias) que no son recursivas primitivas. Sudán publicó la función menos conocida del Sudán, después de poco tiempo e independientemente, en 1928, Ackermann publicó su función $varphi$ (la carta griega phi). La función de tres brazos de Ackermann, ${displaystyle varphi (m,n,p)}$ , se define de tal manera que ${displaystyle p=0,1,2}$ , reproduce las operaciones básicas de adición, multiplicación y exponenciación como

{displaystyle {begin{aligned}varphi (m,n,0)&=m+n\varphi (m,n,1)&=mtimes n\varphi (m,n,2)&=m^{n}end{aligned}}}

y para p > 2 extiende estas operaciones básicas de una manera que puede compararse con las hiperoperaciones:

3end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ ()m,n,3)=m[4]()n+1)φ φ ()m,n,p)⪆ ⪆ m[p+1]()n+1)parap■3{displaystyle {begin{aligned}varphi (m,n,3) limit=m[4](n+1)\varphi (m,n,p) conllevagtrapprox m[p+1](n+1) limitándose{text{for ¿Qué?3end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55d4772652d7289170cc00951d017f5ae1c25d5b" style="vertical-align: -2.505ex; width:43.007ex; height:6.176ex;"/>

(Además de su papel histórico como una función recursiva totalmente computable pero no primitiva, se considera que la función original de Ackermann extiende las operaciones aritméticas básicas más allá de la exponenciación, aunque no tan perfectamente como lo hacen las variantes de función de Ackermann que están diseñadas específicamente para ese propósito, como la secuencia de hiperoperación de Goodstein).

En Sobre el infinito, David Hilbert planteó la hipótesis de que la función de Ackermann no era recursiva primitiva, pero fue Ackermann, el secretario personal y antiguo alumno de Hilbert, quien demostró la hipótesis en su artículo Sobre la construcción de los números reales de Hilbert.

Rózsa Péter y Raphael Robinson desarrollaron más tarde una versión de dos variables de la función de Ackermann que se volvió preferida por casi todos los autores.

La secuencia generalizada de hiperoperación, por ejemplo. ${displaystyle G(m,a,b)=a[m]b}$ , es una versión de la función Ackermann también.

En 1963 R.C. Buck basó una variante intuitiva de dos variables $operatorname {F}$ en la secuencia de hiperoperación:

{displaystyle operatorname {F} (m,n)=2[m]n.}

En comparación con la mayoría de las otras versiones, la función de Buck no tiene compensaciones no esenciales:

{displaystyle {begin{aligned}operatorname {F} (0,n)&=2[0]n=n+1\operatorname {F} (1,n)&=2[1]n=2+n\operatorname {F} (2,n)&=2[2]n=2times n\operatorname {F} (3,n)&=2[3]n=2^{n}\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\&quad vdots end{aligned}}}

Se han investigado muchas otras versiones de la función de Ackermann.

Definición

Definición: como función m-aria

Función original de tres brazos de Ackermann ${displaystyle varphi (m,n,p)}$ se define recursivamente como sigue para los enteros no negativos ${displaystyle m,n,}$ y $p$ :

2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ ()m,n,0)=m+nφ φ ()m,0,1)=0φ φ ()m,0,2)=1φ φ ()m,0,p)=mparap■2φ φ ()m,n,p)=φ φ ()m,φ φ ()m,n− − 1,p),p− − 1)paran,p■0{displaystyle {begin{aligned}varphi (m,n,0) Sent=m+n\\varphi (m,0,1) limit=0\\varphi (m,0,2) limit=1\varphi (m,0,p) }p confía2\varphi (m,n,p) limitada=varphi (m,varphi (m,n-1,p),p-1) }n,p confía0end{aligned}}2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6855f9ddb1eb08206260d704b921e4a459da030" style="vertical-align: -7.171ex; width:56.337ex; height:15.509ex;"/>

De las diferentes versiones de dos águlos, la desarrollada por Péter y Robinson (llamada "la" función Ackermann por la mayoría de los autores) se define para los enteros no negativos $m$ y $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,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:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A()m,n)={}n+1m=02[m]()n+3)− − 3m■0{displaystyle A(m,n)={begin{cases}n+1 limitm=02[m](n+3)-3 implicam confianza0\end{cases}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>

o, escrito en la notación de arriba de Knuth (extended to integer indices

{displaystyle geq -2}

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=02↑ ↑ m− − 2()n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=02uparrow ^{m-2}(n+3)-3 implicam confianza0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d5eb19389f023dbd9efd2fa3ed9c0a69948aecc" style="vertical-align: -2.505ex; width:32.172ex; height:6.176ex;"/>

o, equivalentemente, en términos de la función F de Buck:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=0F()m,n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=0F(m,n+3)-3 Pulsón0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Definición: como función iterada 1-aria

Define ${displaystyle f^{n}}$ como n- el itinerario $f$ :

{displaystyle {begin{array}{rll}f^{0}(x)&=&x\f^{n+1}(x)&=&f(f^{n}(x)),,,,{{textrm {for}},,ngeq 1}end{array}}}

La iteración es el proceso de componer una función con sí mismo un cierto número de veces. La composición de la función es una operación asociativa, por lo que ${displaystyle f(f^{n}(x))=f^{n}(f(x))}$ .

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

La función entonces se convierte en una secuencia ${displaystyle operatorname {A} _{0},operatorname {A} _{1},operatorname {A} _{2},...}$ of unary functions, defined from iteration:

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

Cálculo

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

TRS, basado en la función biaria

La definición de la función 2-aria de Ackermann conduce a las reglas de reducción obvias

{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

Computación ${displaystyle A(1,2)rightarrow _{*}4}$

La secuencia de reducción es

La estrategia más externa (un solo paso):	Estrategia más interna (un paso):
${displaystyle {underline {A(S(0),S(S(0)))}}}$	${displaystyle {underline {A(S(0),S(S(0)))}}}$
${displaystyle rightarrow _{r3}{underline {A(0,A(S(0),S(0))}})}$	${displaystyle rightarrow _{r3}A(0,{underline {A(S(0),S(0))}})}$
${displaystyle rightarrow _{r1}S({underline {A(S(0),S(0))}})}$	${displaystyle rightarrow _{r3}A(0,A(0,{underline {A(S(0),0)}}))}$
${displaystyle rightarrow _{r3}S({underline {A(0,A(S0,0))}})}$	${displaystyle rightarrow _{r2}A(0,A(0,{underline {A(0,S(0))}}))}$
${displaystyle rightarrow _{r1}S(S({underline {A(S(0),0)}}))}$	${displaystyle rightarrow _{r1}A(0,{underline {A(0,S(S(0)))}})}$
${displaystyle rightarrow _{r2}S(S({underline {A(0,S(0))}}))}$	${displaystyle rightarrow _{r1}{underline {A(0,S(S(S(0))))}}}$
${displaystyle rightarrow _{r1}S(S(S(S(0))))}$	${displaystyle rightarrow _{r1}S(S(S(S(0))))}$

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

Luego, repetidamente, los dos elementos superiores se reemplazan de acuerdo con las reglas

{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)&,&nend{array}}}

Esquemáticamente, a partir de ${displaystyle langle m,nrangle }$ :

WHILE stackLength 1
{}
 POP 2 elementos;
 PUSH 1 o 2 o 3 elementos, aplicando las reglas r1, r2, r3
}

El pseudocódigo está publicado en Grossman & Zeitman (1988).

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

las configuraciones de pila	reflejar la reducción
${displaystyle {underline {2,1}}}$	${displaystyle {underline {A(2,1)}}}$
${displaystyle rightarrow 1,{underline {2,0}}}$	${displaystyle rightarrow _{r1}A(1,{underline {A(2,0)}})}$
${displaystyle rightarrow 1,{underline {1,1}}}$	${displaystyle rightarrow _{r2}A(1,{underline {A(1,1)}})}$
${displaystyle rightarrow 1,0,{underline {1,0}}}$	${displaystyle rightarrow _{r3}A(1,A(0,{underline {A(1,0)}}))}$
${displaystyle rightarrow 1,0,{underline {0,1}}}$	${displaystyle rightarrow _{r2}A(1,A(0,{underline {A(0,1)}}))}$
${displaystyle rightarrow 1,{underline {0,2}}}$	${displaystyle rightarrow _{r1}A(1,{underline {A(0,2)}})}$
${displaystyle rightarrow {underline {1,3}}}$	${displaystyle rightarrow _{r1}{underline {A(1,3)}}}$
${displaystyle rightarrow 0,{underline {1,2}}}$	${displaystyle rightarrow _{r3}A(0,{underline {A(1,2)}})}$
${displaystyle rightarrow 0,0,{underline {1,1}}}$	${displaystyle rightarrow _{r3}A(0,A(0,{underline {A(1,1)}}))}$
${displaystyle rightarrow 0,0,0,{underline {1,0}}}$	${displaystyle rightarrow _{r3}A(0,A(0,A(0,{underline {A(1,0)}})))}$
${displaystyle rightarrow 0,0,0,{underline {0,1}}}$	${displaystyle rightarrow _{r2}A(0,A(0,A(0,{underline {A(0,1)}})))}$
${displaystyle rightarrow 0,0,{underline {0,2}}}$	${displaystyle rightarrow _{r1}A(0,A(0,{underline {A(0,2)}}))}$
${displaystyle rightarrow 0,{underline {0,3}}}$	${displaystyle rightarrow _{r1}A(0,{underline {A(0,3)}})}$
${displaystyle rightarrow {underline {0,4}}}$	${displaystyle rightarrow _{r1}{underline {A(0,4)}}}$
${displaystyle rightarrow 5}$	${displaystyle rightarrow _{r1}5}$

Comentarios

La estrategia más interna de la izquierda se aplica en 225 idiomas informáticos en el Código Rosetta.
Para todos $m,n$ la computación de ${displaystyle A(m,n)}$ no toma más que ${displaystyle (A(m,n)+1)^{m}}$ pasos.
Grossman " Zeitman (1988) señaló 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 $0}" xmlns="http://www.w3.org/1998/Math/MathML">m■0{displaystyle m confía0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>$ .

Su propio algoritmo, inherentemente iterativo, calcula

{displaystyle operatorname {A} (m,n)}

dentro

{displaystyle {mathcal {O}}(moperatorname {A} (m,n))}

tiempo y dentro

{mathcal {O}}(m)

espacio.

TRS, basado en una función aria iterada

La definición de las funciones iteradas 1-aria de Ackermann 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}}}

Como en la sección anterior la computación de ${displaystyle operatorname {A} _{m}^{1}(n)}$ se puede implementar con una pila.

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

Luego, repetidamente, los tres elementos superiores se reemplazan de acuerdo con las reglas.

{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, a partir de ${displaystyle langle 1,m,nrangle }$ :

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

Ejemplo

Sobre la entrada ${displaystyle langle 1,2,1rangle }$ las configuraciones de pilas 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}5end{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)=5end{aligned}}}

Cuando se usa 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&,nend{array}}}

Las sucesivas configuraciones de 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}5end{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)=5end{aligned}}}

Comentarios

En 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 "lo mismo que" 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. 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 se queda abajo ${displaystyle 2times A(i,n)}$ . Cuando la regla de reducción r7 se utiliza en lugar de regla r6, la longitud máxima de la pila es sólo ${displaystyle 2(i+2)}$ . La longitud de la pila refleja la profundidad de la recursión. Dado que la reducción según las reglas {r4, r5, r7} implica una menor profundidad máxima de recurrencia, este cálculo es más eficiente en ese sentido.

TRS, basado en hiperoperadores

Como Sundblad (1971), o Porto & Matos (1980) — mostró explícitamente que la función de Ackermann se puede expresar en términos de la secuencia de hiperoperación:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A()m,n)={}n+1m=02[m]()n+3)− − 3m■0{displaystyle A(m,n)={begin{cases}n+1 limitm=02[m](n+3)-3 implicam confianza0\end{cases}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>

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

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=0F()m,n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=0F(m,n+3)-3 Pulsón0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Función de Buck ${displaystyle operatorname {F} (m,n)=2[m]n}$ , una variante de la función Ackermann por sí misma, se puede computar 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 es suficiente agregar 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 A(0,n), la alineación (n+3) y el error (-3).

Ejemplo

Computación ${displaystyle A(2,1)rightarrow _{*}5}$

utilizando reglas de reducción ${displaystyle {text{b7}}}$ :	utilizando reglas de reducción ${displaystyle {text{b6}}}$ :
${displaystyle {underline {A(2,1)}}}$	${displaystyle {underline {A(2,1)}}}$
${displaystyle rightarrow _{r9}P({underline {F(1,2,4)}})}$	${displaystyle rightarrow _{r9}P({underline {F(1,2,4)}})}$
${displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}}))}$	${displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}}))}$
${displaystyle rightarrow _{b3}P({underline {F(4,1,0)}})}$	${displaystyle rightarrow _{b3}P({underline {F(4,1,0)}})}$
${displaystyle rightarrow _{b7}P(F(3,1,{underline {F(1,1,0)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,{underline {F(3,1,0)}}))}$
${displaystyle rightarrow _{b2}P({underline {F(3,1,2)}})}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,{underline {F(2,1,0)}})))}$
${displaystyle rightarrow _{b7}P(F(2,1,{underline {F(1,1,2)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{underline {F(1,1,0)}}))))}$
${displaystyle rightarrow _{b5}P(F(2,1,F(2,0,{underline {F(1,1,0)}})))}$	${displaystyle rightarrow _{b2}P(F(1,1,F(1,1,{underline {F(1,1,2)}})))}$
${displaystyle rightarrow _{b2}P(F(2,1,{underline {F(2,0,2)}}))}$	${displaystyle rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{underline {F(1,1,0)}}))))}$
${displaystyle rightarrow _{b7}P(F(2,1,F(1,0,{underline {F(1,0,2)}})))}$	${displaystyle rightarrow _{b2}P(F(1,1,F(1,1,{underline {F(2,0,2)}})))}$
${displaystyle rightarrow _{b1}P(F(2,1,{underline {F(1,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{underline {F(1,0,2)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(2,1,4)}})}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,1,{underline {F(1,0,3)}})))}$
${displaystyle rightarrow _{b7}P(F(1,1,{underline {F(1,1,4)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,1,4)}}))}$
${displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})))}$	${displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})))}$
${displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)}}))}$	${displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)}}))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(3,0,{underline {F(1,0,2)}})))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,{underline {F(3,0,2)}})))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(3,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{underline {F(2,0,2)}}))))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(2,0,{underline {F(1,0,3)}})))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)}})))))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(2,0,4)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{underline {F(1,0,3)}}))))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(1,0,{underline {F(1,0,4)}})))}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,0,{underline {F(1,0,4)}})))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(1,1,6)}})}$	${displaystyle rightarrow _{b1}P({underline {F(1,1,6)}})}$
${displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}}))}$	${displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}}))}$
${displaystyle rightarrow _{b2}P({underline {F(6,0,2)}})}$	${displaystyle rightarrow _{b2}P({underline {F(6,0,2)}})}$
${displaystyle rightarrow _{b7}P(F(5,0,{underline {F(1,0,2)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,{underline {F(5,0,2)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(5,0,3)}})}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,{underline {F(4,0,2)}})))}$
${displaystyle rightarrow _{b7}P(F(4,0,{underline {F(1,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{underline {F(3,0,2)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(4,0,4)}})}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(2,0,2)}})))))}$
${displaystyle rightarrow _{b7}P(F(3,0,{underline {F(1,0,4)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)}}))))))}$
${displaystyle rightarrow _{b1}P({underline {F(3,0,5)}})}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,3)}})))))}$
${displaystyle rightarrow _{b7}P(F(2,0,{underline {F(1,0,5)}}))}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{underline {F(1,0,4)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(2,0,6)}})}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,{underline {F(1,0,5)}})))}$
${displaystyle rightarrow _{b7}P(F(1,0,{underline {F(1,0,6)}}))}$	${displaystyle rightarrow _{b1}P(F(1,0,{underline {F(1,0,6)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(1,0,7)}})}$	${displaystyle rightarrow _{b1}P({underline {F(1,0,7)}})}$
${displaystyle rightarrow _{b1}{underline {P(8)}}}$	${displaystyle rightarrow _{b1}{underline {P(8)}}}$
${displaystyle rightarrow _{r10}5}$	${displaystyle rightarrow _{r10}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)=8end{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)=8end{aligned}}}

Comentarios

La computación de ${displaystyle operatorname {A} _{i}(n)}$ según las reglas {b1 - b5, b6, r8 - r10} es profundamente recursivo. La profundidad máxima de anidado $F$ s ${displaystyle A(i,n)+1}$ . El culpable es la orden en la que se ejecuta la iteración: ${displaystyle F^{n+1}(x)=F(F^{n}(x))}$ . La primera $F$ desaparece sólo después de que toda la secuencia se desarrolle.
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. El anidaje se limita a $(i+1)$ , un nivel de recursión por función iterada. Meyer & Ritchie (1967) mostró esta correspondencia.
Estas consideraciones se refieren únicamente a la profundidad de recursión. Cualquier forma de iteración conduce al mismo número de pasos de reducción, que implican las mismas reglas (cuando las reglas b6 y b7 se consideran "el mismo"). 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 sólo afecta el orden en que se aplican las reglas de reducción.
Una ganancia real del tiempo de ejecución sólo puede lograrse no recalculando los subresultos una y otra vez. La memoización es una técnica de optimización donde los resultados de las llamadas de función son caché y devueltos cuando las mismas entradas ocurren de nuevo. Véase por ejemplo Ward (1993). Grossman " Zeitman (1988) publicó un algoritmo astuto que compute ${displaystyle A(i,n)}$ dentro ${displaystyle {mathcal {O}}(iA(i,n))}$ tiempo y dentro ${displaystyle {mathcal {O}}(i)}$ espacio.

Números enormes

Para demostrar cómo la computación $A(4,3)$ resultados en muchos pasos y en un gran número:

{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}}}

Tabla de valores

El cálculo de la función de Ackermann se puede reformular en términos de una tabla infinita. Primero, coloca los números naturales a lo largo de la fila superior. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda. Luego use ese número para buscar el número requerido en la columna dada por ese número y una fila hacia arriba. Si no hay un número a su izquierda, simplemente mire la columna encabezada "1" en la fila anterior. Aquí hay una pequeña parte superior izquierda de la tabla:

Valores de A()m,n)
n m	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13 ${displaystyle ={2^{2^{2}}}-3}$ ${displaystyle =2uparrow uparrow 3-3}$	65533 ${displaystyle ={2^{2^{2^{2}}}}-3}$ ${displaystyle =2uparrow uparrow 4-3}$	2⁶⁵⁵³⁶3 - 3 ${displaystyle ={2^{2^{2^{2^{2}}}}}-3}$ ${displaystyle =2uparrow uparrow 5-3}$	${2^{2^{65536}}}-3$ ${displaystyle ={2^{2^{2^{2^{2^{2}}}}}}-3}$ ${displaystyle =2uparrow uparrow 6-3}$	${2^{2^{2^{65536}}}}-3$ ${displaystyle ={2^{2^{2^{2^{2^{2^{2}}}}}}}-3}$ ${displaystyle =2uparrow uparrow 7-3}$	${displaystyle {begin{matrix}underbrace {{2^{2}}^{{cdot }^{{cdot }^{{cdot }^{2}}}}} _{n+3}-3end{matrix}}}$ ${displaystyle =2uparrow uparrow (n+3)-3}$
5	65533 ${displaystyle =2uparrow uparrow (2uparrow uparrow 2)-3}$ ${displaystyle =2uparrow uparrow uparrow 3-3}$	$2uparrow uparrow uparrow 4-3$	$2uparrow uparrow uparrow 5-3$	$2uparrow uparrow uparrow 6-3$	$2uparrow uparrow uparrow 7-3$	$2uparrow uparrow uparrow (n+3)-3$
6	$2uparrow uparrow uparrow uparrow 3-3$	$2uparrow uparrow uparrow uparrow 4-3$	$2uparrow uparrow uparrow uparrow 5-3$	$2uparrow uparrow uparrow uparrow 6-3$	$2uparrow uparrow uparrow uparrow 7-3$	$2uparrow uparrow uparrow uparrow (n+3)-3$
m	${displaystyle (2to 3to (m-2))-3}$	${displaystyle (2to 4to (m-2))-3}$	${displaystyle (2to 5to (m-2))-3}$	${displaystyle (2to 6to (m-2))-3}$	${displaystyle (2to 7to (m-2))-3}$	${displaystyle (2to (n+3)to (m-2))-3}$

Los números aquí que solo se expresan con exponenciación recursiva o flechas de Knuth son muy grandes y ocuparían demasiado espacio para anotarlos en dígitos decimales simples.

A pesar de los grandes valores que aparecen en esta primera sección de la tabla, se han definido algunos números aún más grandes, como el número de Graham, que no se puede escribir con una pequeña cantidad de flechas de Knuth. Este número se construye con una técnica similar a aplicar la función de Ackermann a sí mismo recursivamente.

Esta es una repetición de la tabla anterior, pero con los valores reemplazados por la expresión relevante de la definición de la función para mostrar el patrón claramente:

Valores de A()m,n)
n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(0, 1)	A(0, A(1, 0)) = A(0, 2)	A(0, A(1, 1)) = A(0, 3)	A(0, A(1, 2)) = A(0, 4)	A(0, A(1, 3)) = A(0, 5)	A(0, A(1, n−1))
2	A(1, 1)	A(1, A(2, 0)) = A(1, 3)	A(1, A(2, 1)) = A(1, 5)	A(1, A(2, 2)) = A(1, 7)	A(1, A(2, 3)) = A(1, 9)	A(1, A(2, n−1))
3	A(2, 1)	A(2, A(3, 0)) = A(2, 5)	A(2, A(3, 1)) = A(2, 13)	A(2, A(3, 2)) = A(2, 29)	A(2, A(3, 3)) = A(2, 61)	A(2, A(3, n−1))
4	A(3, 1)	A(3, A(4, 0))) = A(3, 13)	A(3, A(4, 1)) = A(3, 65533)	A(3, A(4, 2))	A(3, A(4, 3))	A(3, A(4, n−1))
5	A(4, 1)	A(4, A(5, 0))	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	A(4, A(5, n−1))
6	A(5, 1)	A(5, A(6, 0))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))	A(5, A(6, n−1))

Propiedades

Observaciones generales

Puede que no sea inmediatamente obvio que la evaluación $A(m,n)$ siempre termina. Sin embargo, la recursión está ligada porque en cada aplicación recursiva ya sea $m$ disminuciones, o $m$ sigue siendo el mismo $n$ disminuciones. Cada vez que $n$ alcanza cero, $m$ disminuciones, por lo tanto $m$ eventualmente llega a cero también. (Expresado más técnicamente, en cada caso el par $(m,n)$ disminuciones en el orden lexicográfico sobre pares, que es un bien ordenado, al igual que el orden de enteros no negativos individuales; esto significa que no se puede bajar en el orden infinitamente muchas veces en sucesión.) Sin embargo, cuando $m$ disminuciones no hay límite superior en cuánto $n$ puede aumentar — y a menudo aumentará enormemente.
Para valores pequeños de m como 1, 2, o 3, la función Ackermann crece relativamente lentamente con respecto a n (a lo más exponencial). Para ${displaystyle mgeq 4}$ , sin embargo, crece mucho más rápidamente; incluso ${displaystyle A(4,2)}$ es alrededor de 2×10¹⁹⁷²⁸, y la expansión decimal $A(4,3)$ es muy grande por cualquier medida típica.
Un aspecto interesante es que la única operación aritmética que utiliza es la adición de 1. Su poder de crecimiento rápido se basa únicamente en la recursión anida. Esto también implica que su tiempo de funcionamiento es al menos proporcional a su producción, y también es extremadamente enorme. En la actualidad, para la mayoría de los casos el tiempo de funcionamiento es mucho mayor que la salida; véase arriba.
Una versión de un solo grupo ${displaystyle f(n)=A(n,n)}$ que aumenta ambos $m$ y $n$ al mismo tiempo enana cada función recursiva primitiva, incluyendo funciones de crecimiento muy rápido como la función exponencial, la función factorial, funciones multi- y superfactoriales, e incluso funciones definidas usando la notación de Knuth (excepto cuando se utiliza la flecha indizada). Se puede ver que $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 $f$ que es obviamente computable en una máquina con memoria infinita como una máquina de Turing y así es una función computable, crece más rápido que cualquier función recursiva primitiva y por lo tanto no es recursiva primitiva.

No primitivo recursivo

La función Ackermann crece más rápido que cualquier función recursiva primitiva y por lo tanto no es en sí misma la recursiva primitiva. El boceto de la prueba es éste: una función recursiva primitiva definida usando recursiones de hasta k debe crecer más lento que la ${displaystyle f_{k+1}(n)}$ , la función (k+1)-th en la jerarquía de crecimiento rápido, pero la función Ackermann crece al menos tan rápido como ${displaystyle f_{omega }(n)}$ .

Específicamente, se muestra que a cada función recursiva primitiva $f(x_{1},ldotsx_{n})$ existe un entero no negativo $t$ tal que para todos los enteros no negativos $x_{1},ldotsx_{n}$ ,