Función de Ackermann

Función de rápido crecimiento

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 ^[1] 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 ^[2] de la función de Ackermann (que tenía tres argumentos enteros no negativos), muchos autores la modificaron para adaptarla a diversos 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 es la función de Ackermann-Péter de dos argumentos desarrollada por Rózsa Péter y Raphael Robinson . Su valor crece muy rápidamente; por ejemplo, da como resultado , un entero de 19.729 dígitos decimales. ^[3] ${\displaystyle \operatorname {A} (4,2)}$ ${\displaystyle 2^{65536}-3}$

Historia

A finales de la década de 1920, los matemáticos Gabriel Sudan y Wilhelm Ackermann , estudiantes de David Hilbert , estudiaban los fundamentos de la computación. Tanto a Sudan como a Ackermann se les atribuye ^[4] el descubrimiento de funciones computables totales (denominadas simplemente "recursivas" en algunas referencias) que no son recursivas primitivas . Sudan publicó la menos conocida función Sudan y, poco después e independientemente, en 1928, Ackermann publicó su función (del griego, la letra phi ). La función de tres argumentos de Ackermann, , se define de modo que para , reproduce las operaciones básicas de suma , multiplicación y exponenciación como ${\displaystyle \varphi }$ ${\displaystyle \varphi (m,n,p)}$ ${\displaystyle p=0,1,2}$

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times 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 :

${\displaystyle {\begin{aligned}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{aligned}}}$

(Además de su papel histórico como función totalmente computable pero no recursiva 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 la función de Ackermann que están diseñadas específicamente para ese propósito, como la secuencia de hiperoperaciones de Goodstein ).

En Sobre el infinito , ^[5] David Hilbert planteó la hipótesis de que la función de Ackermann no era recursiva primitiva, pero fue Ackermann, el secretario personal de Hilbert y ex alumno, quien realmente demostró la hipótesis en su artículo Sobre la construcción de los números reales por Hilbert . ^{[2] [6]}

Posteriormente, Rózsa Péter ^[7] y Raphael Robinson ^[8] desarrollaron una versión de dos variables de la función de Ackermann que pasó a ser la preferida por casi todos los autores.

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

En 1963, RC Buck basó una variante intuitiva de dos variables ^{[n 1]} en la secuencia de hiperoperaciones : ^{[10] [11]} ${\displaystyle \operatorname {F} }$

${\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=2\times 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. ^{[12] [13]}

Definición

Definición: como función m-aria

La función original de tres argumentos de Ackermann se define recursivamente de la siguiente manera para números enteros no negativos y : ${\displaystyle \varphi (m,n,p)}$ ${\displaystyle m,n,}$ ${\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{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}}$

De las diversas versiones de dos argumentos, la desarrollada por Péter y Robinson (llamada "la" función de Ackermann por la mayoría de los autores) está definida para números enteros no negativos y de la siguiente manera: ${\displaystyle m}$ ${\displaystyle 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}}}$

La función de Ackermann también se ha expresado en relación con la secuencia de hiperoperaciones : ^{[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 ={\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 de Buck F: ^[10]

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

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

Definir como la n -ésima iteración de : ${\displaystyle f^{n}}$ ${\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 número determinado 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 de funciones unarias ^{[n 2]} , definidas a partir de la iteración : ${\displaystyle \operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...}$

${\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 puede naturalmente transponerse a un sistema de reescritura de términos (TRS) .

TRS, basado en la función 2-aria

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

${\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 el cálculo se puede utilizar una pila , que inicialmente contiene los elementos . ${\displaystyle \operatorname {A} (m,n)}$ ${\displaystyle \langle m,n\rangle }$

Luego se reemplazan repetidamente los dos elementos superiores de acuerdo con 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, partiendo de : ${\displaystyle \langle m,n\rangle }$

MIENTRAS longitud de pila <> 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 más a la izquierda-más al interior se implementa en 225 lenguajes de computadora en Rosetta Code .
• Porque todo el cálculo no requiere más que pasos. ^[18] ${\displaystyle m,n}$ ${\displaystyle A(m,n)}$ ${\displaystyle (A(m,n)+1)^{m}}$
• Grossman y Zeitman (1988) señalaron que en el cálculo de la longitud máxima de la pila es , siempre que . ${\displaystyle \operatorname {A} (m,n)}$ ${\displaystyle \operatorname {A} (m,n)}$ ${\displaystyle m>0}$

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

TRS, basado en una función 1-aria iterada

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 se puede implementar con una pila. ${\displaystyle \operatorname {A} _{m}^{1}(n)}$

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

Luego se reemplazan repetidamente los tres elementos superiores 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, partiendo de : ${\displaystyle \langle 1,m,n\rangle }$

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

Ejemplo

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

${\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 de pila sucesivas 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

• En cualquier entrada dada, las TRS presentadas 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 converge en 14 pasos: 6 × r1, 3 × r2, 5 × r3. La reducción de converge en los mismos 14 pasos: 6 × r4, 3 × r5, 5 × r6/r7. Las TRS difieren en el orden en que se aplican las reglas de reducción. ${\displaystyle A(2,1)}$ ${\displaystyle A_{2}(1)}$
• Cuando se calcula siguiendo las reglas {r4, r5, r6}, la longitud máxima de la pila se mantiene por debajo de . Cuando se utiliza la regla de reducción r7 en lugar de la regla r6, la longitud máxima de la pila es solo . 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. ${\displaystyle A_{i}(n)}$ ${\displaystyle 2\times A(i,n)}$ ${\displaystyle 2(i+2)}$

TRS, basado en hiperoperadores

Como lo demostraron explícitamente Sundblad (1971) —o Porto y Matos (1980)—, 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 ={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}$

La función de Buck , ^[10] una variante de la función de Ackermann, se puede calcular con las siguientes reglas de reducción: ${\displaystyle \operatorname {F} (m,n)=2[m]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 sumar 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

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

Las igualdades coincidentes son

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

${\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 se aplica el TRS con la regla de reducción : ${\displaystyle {\text{b7}}}$

${\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 según las reglas {b1 ​​- b5, b6, r8 - r10} es profundamente recursivo. La profundidad máxima de los s anidados es . El culpable es el orden en el que se ejecuta la iteración: . El primero desaparece solo después de que se desarrolla toda la secuencia. ${\displaystyle \operatorname {A} _{i}(n)}$ ${\displaystyle F}$ ${\displaystyle A(i,n)+1}$ ${\displaystyle F^{n+1}(x)=F(F^{n}(x))}$ ${\displaystyle F}$
• El cálculo según las reglas {b1 ​​- b5, b7, r8 - r10} es más eficiente en ese sentido. La iteración simula el bucle repetido sobre un bloque de código. ^{[n 7]} La ​​anidación está limitada a un nivel de recursión por función iterada. Meyer y Ritchie (1967) demostraron esta correspondencia. ${\displaystyle F^{n+1}(x)=F^{n}(F(x))}$ ${\displaystyle (i+1)}$
• Estas consideraciones se refieren únicamente a la profundidad de recursión. Cualquiera de las dos formas de iteración conduce a la misma cantidad de pasos de reducción, que implican las mismas reglas (cuando las reglas b6 y b7 se consideran "iguales"). La reducción de, 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 el que se aplican las reglas de reducción. ${\displaystyle A(2,1)}$
• Solo se puede lograr una ganancia real en el tiempo de ejecución si no se recalculan los subresultados una y otra vez. La memorización es una técnica de optimización en la que los resultados de las llamadas a funciones se almacenan en caché y se devuelven cuando se vuelven a producir las mismas entradas. Véase, por ejemplo, Ward (1993). Grossman y Zeitman (1988) publicaron un algoritmo ingenioso que realiza cálculos dentro del tiempo y del espacio. ${\displaystyle A(i,n)}$ ${\displaystyle {\mathcal {O}}(iA(i,n))}$ ${\displaystyle {\mathcal {O}}(i)}$

Enormes números

Para demostrar cómo se calculan los resultados en muchos pasos y en un gran número: ^{[n 5]} ${\displaystyle A(4,3)}$

${\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 replantear en términos de una tabla infinita. Primero, coloque 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 ningún número a su izquierda, simplemente mire la columna encabezada "1" en la fila anterior. Aquí hay una pequeña porción superior izquierda de la tabla:

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 incluso mayores, como el número de Graham , que no se puede escribir con ninguna pequeña cantidad de flechas de Knuth. Este número se construye con una técnica similar a la de aplicar la función de Ackermann a sí misma de forma recursiva.

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:

Propiedades

Observaciones generales

• Puede que no sea inmediatamente obvio que la evaluación de siempre termina. Sin embargo, la recursión está limitada porque en cada aplicación recursiva o bien decrece, o bien permanece igual y decrece. Cada vez que llega a cero, decrece, por lo que finalmente también llega a cero. (Expresado de manera más técnica, en cada caso el par decrece en el orden lexicográfico en pares, lo cual es un buen ordenamiento , al igual que el ordenamiento de números enteros no negativos individuales; esto significa que no se puede descender en el ordenamiento infinitas veces seguidas). Sin embargo, cuando decrece no hay un límite superior sobre cuánto puede aumentar, y a menudo aumentará mucho. ${\displaystyle A(m,n)}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle (m,n)}$ ${\displaystyle m}$ ${\displaystyle n}$
• 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 ). Sin embargo, para , crece mucho más rápido; incluso es aproximadamente 2,00353 × 10 ${\displaystyle m\geq 4}$ ${\displaystyle A(4,2)}$^{19 728} , y la expansión decimal dees muy grande según cualquier medida típica, aproximadamente 2,12004 × 10 ^{6,03123 × 10} ${\displaystyle A(4,3)}$^{19 727} .
• Un aspecto interesante es que la única operación aritmética que utiliza es la suma de 1. Su creciente potencia se basa únicamente en la recursión anidada. Esto también implica que su tiempo de ejecución es al menos proporcional a su salida, y por lo tanto también es extremadamente grande. En realidad, para la mayoría de los casos el tiempo de ejecución es mucho mayor que la salida; vea más arriba.
• Una versión de un solo argumento que aumenta ambos y al mismo tiempo empequeñece cada función recursiva primitiva, incluyendo funciones de crecimiento muy rápido como la función exponencial , la función factorial, funciones multifactoriales y superfactoriales , e incluso 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 es aproximadamente comparable a en la jerarquía de crecimiento rápido . Este crecimiento extremo se puede explotar para mostrar que lo que es obviamente 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. ${\displaystyle f(n)=A(n,n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle f_{\omega }(n)}$ ${\displaystyle f}$

No recursivo primitivo

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 recursiva primitiva. El esquema de la prueba es el siguiente: una función recursiva primitiva definida utilizando hasta k recursiones debe crecer más lentamente que , la (k+1)-ésima función en la jerarquía de rápido crecimiento, pero la función de Ackermann crece al menos tan rápido como . ${\displaystyle f_{k+1}(n)}$ ${\displaystyle f_{\omega }(n)}$

En concreto, se demuestra que para cada función recursiva primitiva existe un entero no negativo tal que para todos los enteros no negativos , ${\displaystyle f(x_{1},\ldots ,x_{n})}$ ${\displaystyle t}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i}).}$

Una vez establecido esto, se deduce que en sí mismo no es recursivo primitivo, ya que de lo contrario ponerlo conduciría a la contradicción ${\displaystyle A}$ ${\displaystyle x_{1}=x_{2}=t}$ ${\displaystyle A(t,t)<A(t,t).}$

La prueba se realiza de la siguiente manera: define la clase de todas las funciones que crecen más lentamente que la función de Ackermann. ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {A}}=\left\{f\,{\bigg |}\,\exists t\ \forall x_{1}\cdots \forall x_{n}:\ f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i})\right\}}$

y demostrar que contiene todas las funciones recursivas primitivas. Esto último se logra demostrando que contiene las funciones constantes, la función sucesora, las funciones de proyección y que está cerrada bajo las operaciones de composición de funciones y recursión primitiva. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Uso en complejidad computacional

La función de Ackermann aparece en la complejidad temporal de algunos algoritmos ^[19] , como los sistemas de adición vectorial ^[20] y la accesibilidad de redes de Petri ^[21] , lo que demuestra que son computacionalmente inviables para instancias grandes. La inversa de la función de Ackermann aparece en algunos resultados de complejidad temporal.

Inverso

Como la función f ( n ) = A ( n , n ) considerada anteriormente crece muy rápidamente, su función inversa , f ⁻¹ , crece muy lentamente. Esta función inversa de Ackermann f ⁻¹ se suele denotar por α . De hecho, α ( n ) es menor que 5 para cualquier tamaño de entrada práctico n , ya que A (4, 4) es del orden de .  ${\displaystyle 2^{2^{2^{2^{16}}}}}$

Esta inversa aparece en la complejidad temporal de algunos algoritmos, como la estructura de datos de conjuntos disjuntos y el algoritmo de Chazelle para árboles de expansión mínima . A veces, se utilizan la función original de Ackermann u otras variaciones en estos entornos, pero todas crecen a tasas igualmente altas. En particular, algunas funciones modificadas simplifican la expresión eliminando el −3 y términos similares.

Una variación de dos parámetros de la función inversa de Ackermann se puede definir de la siguiente manera, donde es la función base : ${\displaystyle \lfloor x\rfloor }$

${\displaystyle \alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.}$

Esta función surge en análisis más precisos de los algoritmos mencionados anteriormente y proporciona un límite de tiempo más refinado. En la estructura de datos de conjunto disjunto, m representa el número de operaciones mientras que n representa el número de elementos; en el algoritmo de árbol de expansión mínimo, m representa el número de aristas mientras que n representa el número de vértices. Existen varias definiciones ligeramente diferentes de α ( m , n ) ; por ejemplo, log ₂ n a veces se reemplaza por n , y la función floor a veces se reemplaza por ceiling .

Otros estudios podrían definir una función inversa de uno donde m se establece en una constante, de modo que la inversa se aplica a una fila particular. ^[22]

La inversa de la función de Ackermann es recursiva primitiva. ^[23]

Utilizar como punto de referencia

La función de Ackermann, debido a su definición en términos de recursión extremadamente profunda, puede utilizarse como un parámetro de referencia de 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 ^[24] y, casi simultáneamente, en 1971, por Yngve Sundblad. ^[14]

El artículo seminal de Sundblad fue retomado por Brian Wichmann (coautor del punto de referencia Whetstone ) en una trilogía de artículos escritos entre 1975 y 1982. ^{[25] [26] [27]}

Véase también

• Teoría de la computabilidad
• Doble recursión
• Jerarquía de rápido crecimiento
• Función de Goodstein
• Función recursiva primitiva
• Recursión (informática)

Notas

1. con orden de parámetros invertido
2. ' al curry '
3. En cada paso se reescribe el redex subrayado .
4. aquí: ¡estrategia más a la izquierda y más al interior!
5. Para una mejor legibilidad
   , S(0) se anota como 1,
   S(S(0)) se anota como 2,
   S(S(S(0))) se anota como 3,
   etc.
6. La profundidad máxima de recursión se refiere al número de niveles de activación de un procedimiento que existen durante la llamada más profunda del procedimiento. Cornelius y Kirby (1975)
7. BUCLE n+1 VECES HACER F

Referencias

1. Monin y Hinchey 2003, pág. 61.
2. Ackermann 1928.
3. "Expansión decimal de A(4,2)". kosara.net . 27 de agosto de 2000. Archivado desde el original el 20 de enero de 2010.
4. Calude, Marcus y Tevy 1979.
5. Hilbert 1926, pág. 185.
6. de Heijenoort 1977.
7. Pedro 1935.
8. Robinson 1948.
9. Ritchie 1965, pág. 1028.
10. Buck 1963.
11. Meeussen y Zantema 1992, pág. 6.
12. Munafo 1999a.
13. Ritchie 1965.
14. Sundblad 1971.
15. Porto y Matos 1980.
16. Grossman y Zeitman 1988.
17. Paulson 2021.
18. Cohen 1987, p. 56, Proposición 3.16 (ver en prueba).
19. Brubaker 2023.
20. Czerwiński y Orlikowski 2022.
21. Leroux 2022.
22. Petite 2002.
23. Matos 2014.
24. Vaida 1970.
25. Wichmann 1976.
26. Wichmann 1977.
27. Wichmann 1982.

Bibliografía

• Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Annalen Matemáticas . 99 : 118-133. doi :10.1007/BF01459088. S2CID  123431274.
• Buck, RC (1963). "Inducción matemática y definiciones recursivas". American Mathematical Monthly . 70 (2): 128–135. doi :10.2307/2312881. JSTOR  2312881.
• Calude, Cristian ; Marcus, Solomon ; Tevy, Ionel (noviembre de 1979). "El primer ejemplo de una función recursiva que no es recursiva primitiva". Historia Math . 6 (4): 380–84. doi : 10.1016/0315-0860(79)90024-7 .
• Cohen, Daniel E. (enero de 1987). Computabilidad y lógica . Halsted Press. ISBN 9780745800349.
• Cornelius, BJ; Kirby, GH (1975). "Profundidad de recursión y la función de Ackermann". BIT Numerical Mathematics . 15 (2): 144–150. doi :10.1007/BF01932687. S2CID  120532578.
• Czerwiński, Wojciech; Orlikowski, Łukasz (7 de febrero de 2022). La accesibilidad en sistemas de adición vectorial es completa según el método de Ackermann. Actas del 62.º Simposio anual sobre fundamentos de la informática del IEEE de 2021. arXiv : 2104.13866 . doi :10.1109/FOCS52979.2021.00120.
• Grossman, Jerrold W.; Zeitman, R. Suzanne (mayo de 1988). "Un cálculo inherentemente iterativo de la función de Ackermann". Ciencias de la Computación Teórica . 57 (2–3): 327–330. doi :10.1016/0304-3975(88)90046-1.
• van Heijenoort, Jean (1977) [reimpreso con correcciones, publicado por primera vez en 1967]. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 . Harvard University Press.
• Hilbert, David (1926). "Über das Unendliche". Annalen Matemáticas . 95 : 161-190. doi :10.1007/BF01206605. S2CID  121888793.
• Leroux, Jérôme (7 de febrero de 2022). El problema de accesibilidad para las redes de Petri no es recursivo primitivo. Actas del 62.º Simposio anual sobre fundamentos de la informática del IEEE de 2021. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121.
• Matos, Armando B (7 de mayo de 2014). "La inversa de la función de Ackermann es recursiva primitiva" (PDF) . Archivado (PDF) desde el original el 2022-10-09.
• Meeussen, VCS; Zantema, H. (1992). Longitudes de derivación en la reescritura de términos a partir de interpretaciones en los números naturales (PDF) (Informe). Universiteit Utrecht. UU-CS, Departamento de Ciencias de la Computación. ISSN  0924-3275. Archivado (PDF) desde el original el 2022-10-09.
• Meyer, Albert R. ; Ritchie, Dennis MacAlistair (1967). "La complejidad de los programas de bucle". Actas de la 22.ª conferencia nacional de 1967 . ACM '67: Actas de la 22.ª conferencia nacional de 1967 . págs. 465–469. doi : 10.1145/800196.806014 .
• Monin, Jean-Francois; Hinchey, MG (2003). Comprensión de los métodos formales. Springer. pág. 61. ISBN 9781852332471.
• Munafo, Robert (1999a). "Versiones de la función de Ackermann". Grandes números en MROB . Consultado el 6 de noviembre de 2021 .
• Munafo, Robert (1999b). "Inventando nuevos operadores y funciones". Large Numbers en MROB . Consultado el 6 de noviembre de 2021 .
• Paulson, Lawrence C. (2021). "Función de Ackermann en forma iterativa: un experimento de asistente de pruebas" . Consultado el 19 de octubre de 2021 .
• Peter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Annalen Matemáticas . 111 : 42–60. doi :10.1007/BF01472200. S2CID  121107217.
• Pettie, S. (2002). "Un límite inferior de estilo Ackermann inverso para el problema de verificación de árbol de expansión mínimo en línea". 43.° Simposio anual IEEE sobre fundamentos de la informática, 2002. Actas . págs. 155–163. doi :10.1109/SFCS.2002.1181892. ISBN . 0-7695-1822-2.S2CID8636108  .​
• Porto, António; Matos, Armando B. (1 de septiembre de 1980). "Ackermann y las superpotencias" (PDF) . ACM SIGACT News . 12 (3): Versión original de 1980, publicada en “ACM SIGACT News”, modificada el 20 de octubre de 2012, modificada el 23 de enero de 2016 (documento de trabajo). doi :10.1145/1008861.1008872. S2CID  29780652. Archivado (PDF) desde el original el 2022-10-09.
• Ritchie, Robert Wells (noviembre de 1965). "Clases de funciones recursivas basadas en la función de Ackermann". Pacific Journal of Mathematics . 15 (3): 1027–1044. doi : 10.2140/pjm.1965.15.1027 .
• Robinson, Raphael Mitchel (1948). "Recursión y doble recursión". Boletín de la American Mathematical Society . 54 (10): 987–93. doi : 10.1090/S0002-9904-1948-09121-2 .
• Sundblad, Yngve (marzo de 1971). "La función de Ackermann. Un estudio teórico, computacional y manipulativo de fórmulas". BIT Numerical Mathematics . 11 (1): 107–119. doi :10.1007/BF01935330. S2CID  123416408.
• Vaida, Dragoș (1970). "Validación del compilador para un lenguaje similar a Algol". Boletín Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie . Nueva serie. 14 (62) (4): 487–502. JSTOR  43679758.
• Ward, Martin P. (16 de julio de 1993). Procedimientos iterativos para calcular la función de Ackerman . CiteSeerX  10.1.1.35.9907 .
• Wichmann, Brian A. (marzo de 1976). "Función de Ackermann: un estudio sobre la eficiencia de los procedimientos de llamada". BIT Numerical Mathematics . 16 : 103–110. CiteSeerX  10.1.1.108.4125 . doi :10.1007/BF01940783. S2CID  16993343.
• Wichmann, Brian A. (julio de 1977). "Cómo llamar a procedimientos, o reflexiones sobre la función de Ackermann". BIT Numerical Mathematics . 16 (3): 103–110. doi :10.1002/spe.4380070303. S2CID  206507320.
• Wichmann, Brian A. (julio de 1982). "Últimos resultados de la prueba de llamada a procedimientos, función de Ackermann" (PDF) . Archivado (PDF) desde el original el 2022-10-09.

Enlaces externos

• "Función de Ackermann". Enciclopedia de Matemáticas . EMS Press . 2001 [1994].
• Weisstein, Eric W. "Función de Ackermann". MundoMatemático .
•  Este artículo incorpora material de dominio público de Paul E. Black. "Función de Ackermann". Diccionario de algoritmos y estructuras de datos . NIST .
• Una calculadora animada de funciones de Ackermann
• Aaronson, Scott (1999). "¿Quién puede nombrar el número mayor?".
• Funciones de Ackermann. Incluye una tabla con algunos valores.
• Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece fácil produce números demasiado grandes para nuestro universo".
• Munafo, Robert. "Grandes números".describe varias variaciones sobre la definición de A.
• Nivasch, Gabriel (octubre de 2021). «Ackermann inverso sin dolor». Archivado desde el original el 2007-08-21 . Consultado el 18 de junio de 2023 .
• Seidel, Raimund. "Entendiendo la función inversa de Ackermann" (PDF) .
• La función de Ackermann escrita en diferentes lenguajes de programación, (en Rosetta Code )
• Smith, Harry J. "Función de Ackermann". Archivado desde el original el 26 de octubre de 2009.)Un poco de estudio y programación.