función de ackermann

Función de rápido crecimiento

En la teoría de la computabilidad , la función de Ackermann , que lleva el nombre de Wilhelm Ackermann , es uno de los ejemplos más simples ^[1] y los primeros descubiertos 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 ^[2] de su función (que tenía tres argumentos enteros no negativos), muchos autores la modificaron para adaptarla a diversos propósitos, de modo que hoy "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 dos argumentos de Ackermann-Péter desarrollada por Rózsa Péter y Raphael Robinson . Su valor crece muy rápidamente; por ejemplo, da como resultado , un número 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 , alumnos 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 . Sudán publicó la función Sudán , menos conocida , y poco después y de forma independiente, en 1928, Ackermann publicó su función (del griego, la letra phi ). La función de tres argumentos de Ackermann, se define de manera 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}}}$

(Aparte de su papel histórico como función recursiva total 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 la 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 , ^[5] David Hilbert planteó la hipótesis de que la función de Ackermann no era recursiva primitiva, pero fue Ackermann, secretario personal y ex alumno de Hilbert, quien en realidad demostró la hipótesis en su artículo Sobre la construcción de los números reales de Hilbert . ^{[2] [6]}

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

La secuencia de hiperoperación generalizada , por ejemplo , también es 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 hiperoperación : ^{[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]

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) se define para números enteros no negativos y es la siguiente: ${\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,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 : ^{[13] [14]}

${\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 (extendido 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, de manera equivalente, en términos de la función F de Buck: ^[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 ené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 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))}$

Concebiendo 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 luego se convierte 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

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

TRS, basado en función 2-aria

La definición de la función biaria de Ackermann conduce a las reglas de reducción obvias ^{[15] [16]}

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

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

MIENTRAS longitud de pila <> 1{ POP 2 elementos; EMPUJAR 1 o 2 o 3 elementos, aplicando las reglas r1, r2, r3}

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

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

Observaciones

• La estrategia más interna a la izquierda se implementa en 225 lenguajes informáticos en Rosetta Code .
• Para todo el cálculo de no se necesitan más que pasos. ^[17] ${\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 en el tiempo y en el 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 iteradas de Ackermann 1-aria 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, el cálculo de 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, repetidamente, los tres elementos superiores se reemplazan 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, a partir de : ${\displaystyle \langle 1,m,n\rangle }$

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

Ejemplo

Al ingresar, se muestran las configuraciones de pila sucesivas. ${\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 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&,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, 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" que 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. Los 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 queda 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 la recursividad. Como la reducción según las reglas {r4, r5, r7} implica una profundidad máxima de recursividad menor, ^{[n 6]} este cálculo es más eficiente a ese respecto. ${\displaystyle A_{i}(n)}$ ${\displaystyle 2\times A(i,n)}$ ${\displaystyle 2(i+2)}$

TRS, basado en hiperoperadores

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

${\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 en sí misma, 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 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 ocupan 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 acuerdo con las reglas {b1 ​​- b5, b6, r8 - r10} es profundamente recursivo. La profundidad máxima de s anidados es . El culpable es el orden en que se ejecuta la iteración: . El primero desaparece sólo después de que se ha desarrollado 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 eficaz a este respecto. La iteración simula el bucle repetido sobre un bloque de código. ^{[n 7]} El anidamiento está limitado a un nivel de recursividad por función iterada. Meyer y Ritchie (1967) mostraron esta correspondencia. ${\displaystyle F^{n+1}(x)=F^{n}(F(x))}$ ${\displaystyle (i+1)}$
• Estas consideraciones se refieren únicamente a la profundidad de la recursividad. 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 "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 sólo afecta al orden en que se aplican las reglas de reducción. ${\displaystyle A(2,1)}$
• Sólo se puede lograr una ganancia real de 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 repiten las mismas entradas. Véase, por ejemplo, Ward (1993). Grossman y Zeitman (1988) publicaron un ingenioso algoritmo que calcula en el tiempo y en el espacio. ${\displaystyle A(i,n)}$ ${\displaystyle {\mathcal {O}}(iA(i,n))}$ ${\displaystyle {\mathcal {O}}(i)}$

Cifras enormes

Para demostrar cómo se realiza el cálculo de 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

Calcular la función de Ackermann se puede reformular en términos de una tabla infinita. Primero, coloca los números naturales en 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 titulada "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 escribirlos 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 mayores, como el número de Graham , que no se puede escribir con un número pequeño de flechas de Knuth. Este número se construye con una técnica similar a aplicar la función de Ackermann a sí mismo 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 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 recursividad está limitada porque en cada aplicación recursiva disminuye o permanece igual y disminuye. Cada vez que llega a cero, disminuye, por lo que eventualmente también llega a cero. (Expresado de manera más técnica, en cada caso el par disminuye en el orden lexicográfico en pares, lo cual es un buen ordenamiento , al igual que el orden de números enteros no negativos; esto significa que no se puede bajar en el orden infinitamente muchas veces seguidas .) Sin embargo, cuando disminuye, 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 lentamente con respecto a n (como máximo exponencialmente ). Porque , sin embargo, crece mucho más rápidamente; 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 poder de rápido crecimiento se basa únicamente en la recursividad anidada. Esto también implica que su tiempo de ejecución es al menos proporcional a su producción y, por lo tanto, también es extremadamente enorme. 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 que aumenta ambas y al mismo tiempo eclipsa todas las funciones recursivas primitivas, incluidas funciones de crecimiento muy rápido como la función exponencial , la función factorial, funciones multifactoriales y superfactoriales , e incluso funciones definidas mediante la flecha hacia arriba de Knuth. notación (excepto cuando se utiliza la flecha hacia arriba indexada). Se puede ver que es más o menos comparable a la jerarquía de rápido crecimiento . Este crecimiento extremo puede explotarse para mostrar que lo que es obviamente computable en una máquina con memoria infinita como una máquina de Turing y, por tanto, es una función computable , crece más rápido que cualquier función recursiva primitiva y, por 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 recursiva primitiva en sí misma. El bosquejo de la prueba es el siguiente: una función recursiva primitiva definida usando 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)}$

Específicamente, se muestra que para cada función recursiva primitiva existe un número entero no negativo tal que para todos los números 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 procede de la siguiente manera: defina 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 muestre que contiene todas las funciones recursivas primitivas. Esto último se logra mostrando que contiene las funciones constantes, la función sucesora, las funciones de proyección y que está cerrado bajo las operaciones de composición de funciones y recursividad primitiva. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Uso en complejidad computacional

La función de Ackermann aparece en la complejidad temporal de algunos algoritmos , ^[18] como los sistemas de suma de vectores ^[19] y la alcanzabilidad de la red de Petri , ^[20] , lo que demuestra que son computacionalmente inviables para instancias grandes. La inversa de la función de Ackerman aparece en algunos resultados de complejidad temporal.

Inverso

Dado que 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 ⁻¹ generalmente se denota 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 utiliza 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 −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 está la función suelo : ${\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 conjuntos disjuntos, 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ínima, 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 piso a veces se reemplaza por un techo .

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

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

Usar como punto de referencia

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

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

Ver también

• Teoría de la computabilidad
• doble recursividad
• Jerarquía en rápido crecimiento
• función de goodstein
• Función recursiva primitiva
• Recursión (informática)

Notas

1. con el orden de los parámetros invertido
2. ' curry '
3. En cada paso se reescribe la redex subrayada .
4. aquí: ¡estrategia más interna a la izquierda!
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 recursividad se refiere al número de niveles de activación de un procedimiento que existen durante la llamada más profunda del procedimiento. Cornelio 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, pag. 185.
6. van Heijenoort 1977.
7. Pedro 1935.
8. Robinson 1948.
9. Ritchie 1965, pag. 1028.
10. Dólar 1963.
11. Meeussen y Zantema 1992, pág. 6.
12. Munafo 1999a.
13. Sundblad 1971.
14. Oporto y Matos 1980.
15. Grossman y Zeitman 1988.
16. Paulson 2021.
17. Cohen 1987, pag. 56, Proposición 3.16 (ver prueba).
18. Brubaker 2023.
19. Czerwiński y Orlikowski 2022.
20. Leroux 2022.
21. Pettie 2002.
22. Matos 2014.
23. Vaida 1970.
24. Wichmann 1976.
25. Wichmann 1977.
26. 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.
• Dólar, RC (1963). "Inducción matemática y definiciones recursivas". Mensual Matemático Estadounidense . 70 (2): 128-135. doi :10.2307/2312881. JSTOR  2312881.
• Calude, Cristian ; Marco, Salomón ; Tevy, Ionel (noviembre de 1979). "El primer ejemplo de una función recursiva que no es recursiva primitiva". Historia de las Matemáticas . 6 (4): 380–84. doi : 10.1016/0315-0860(79)90024-7 .
• Cohen, Daniel E. (enero de 1987). Computabilidad y lógica . Prensa detenida. ISBN 9780745800349.
• Cornelio, BJ; Kirby, GH (1975). "Profundidad de recursividad y función de Ackermann". BIT Matemáticas Numéricas . 15 (2): 144-150. doi :10.1007/BF01932687. S2CID  120532578.
• Czerwiński, Wojciech; Orlikowski, Łukasz (7 de febrero de 2022). La accesibilidad en los sistemas de suma de vectores es completa según Ackermann. Actas del 62º Simposio Anual del IEEE de 2021 sobre fundamentos de la informática. 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". Informática 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]. De Frege a Gödel: un libro de consulta sobre lógica matemática, 1879-1931 . Prensa de la Universidad de Harvard.
• 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 de las redes de Petri no es recursivo primitivo. Actas del 62º Simposio Anual del IEEE de 2021 sobre fundamentos de la informática. 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 9 de octubre de 2022.
• Meeussen, VCS; Zantema, H. (1992). Longitudes de derivación en la reescritura de términos a partir de interpretaciones en los naturales (PDF) (Reporte). Universidad de Utrecht. UU-CS, Departamento de Informática. ISSN  0924-3275. Archivado (PDF) desde el original el 9 de octubre de 2022.
• Meyer, Albert R .; Ritchie, Dennis MacAlistair (1967). "La complejidad de los programas en 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-François; Hinchey, MG (2003). Comprensión de los métodos formales. Saltador. pag. 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). "Inventar nuevos operadores y funciones". Grandes números en MROB . Consultado el 6 de noviembre de 2021 .
• Paulson, Lawrence C. (2021). "Función de Ackermann en forma iterativa: un experimento auxiliar de prueba" . 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 inverso de Ackermann para el problema de verificación del árbol de expansión mínima en línea". 43º Simposio anual del IEEE sobre fundamentos de la informática, 2002. Actas . págs. 155-163. doi :10.1109/SFCS.2002.1181892. ISBN 0-7695-1822-2. S2CID  8636108.
• Oporto, Antonio; Matos, Armando B. (1 de septiembre de 1980). «Ackermann y las superpotencias» (PDF) . Noticias ACM SIGACT . 12 (3): Versión original 1980, publicada en “ACM SIGACT News”, Modificado el 20 de octubre de 2012, Modificado el 23 de enero de 2016 (documento de trabajo). doi :10.1145/1008861.1008872. S2CID  29780652. Archivado (PDF) desde el original el 9 de octubre de 2022.
• Ritchie, Robert Wells (noviembre de 1965). "Clases de funciones recursivas basadas en la función de Ackermann". Revista Pacífico de Matemáticas . 15 (3): 1027–1044. doi : 10.2140/pjm.1965.15.1027 .
• Robinson, Rafael Mitchel (1948). "Recursividad y doble recursividad". Boletín de la Sociedad Matemática Estadounidense . 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 de manipulación de fórmulas". BIT Matemáticas Numéricas . 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). "La función de Ackermann: un estudio sobre la eficiencia de los procedimientos de llamada". BIT Matemáticas Numéricas . 16 : 103-110. CiteSeerX  10.1.1.108.4125 . doi :10.1007/BF01940783. S2CID  16993343.
• Wichmann, Brian A. (julio de 1977). "Cómo convocar procedimientos o dudas sobre la función de Ackermann". BIT Matemáticas Numéricas . 16 (3): 103–110. doi : 10.1002/spe.4380070303. S2CID  206507320.
• Wichmann, Brian A. (julio de 1982). "Últimos resultados de la prueba de llamada al procedimiento, función de Ackermann" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.

enlaces externos

• "Función de Ackermann". Enciclopedia de Matemáticas . Prensa EMS . 2001 [1994].
• Weisstein, Eric W. "Función de Ackermann". MundoMatemático .
•  Este artículo incorpora material de dominio público de Paul E. Black. "La función de Ackermann". Diccionario de Algoritmos y Estructuras de Datos . NIST .
• Una calculadora animada de funciones de Ackermann.
• Función de Ackerman implementada mediante un bucle for
• Aaronson, Scott (1999). "¿Quién puede nombrar el número mayor?".
• Funciones de Ackermann. Incluye una tabla de algunos valores.
• Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece sencillo produce cifras demasiado grandes para nuestro universo".
• Munafo, Robert. "Números grandes".describe varias variaciones de la definición de A .
• Nivasch, Gabriel (octubre de 2021). "Ackermann inverso sin dolor". Archivado desde el original el 21 de agosto de 2007 . Consultado el 18 de junio de 2023 .
• Seidel, Raimund. "Comprensión de la función inversa de Ackermann" (PDF) .
• La función de Ackermann escrita en diferentes lenguajes de programación (en Código Rosetta )
• Smith, Harry J. "Función de Ackermann". Archivado desde el original el 26 de octubre de 2009.) Algo de estudio y programación.