Función de Ackermann

La función de Ackermann es un ejemplo simple de una función computable definida en todas partes que no es recursiva primitiva . Toma dos enteros no negativos como parámetros y devuelve un número natural , denotado por . Esta función crece muy rápidamente, por ejemplo, el número es tan grande que el número de dígitos en el orden de este número es muchas veces mayor que el número de átomos en la parte observable del Universo . $A(m,\;n)$ $A(4,\;4)$

Historia

A fines de la década de 1920, los matemáticos de David Hilbert , Gabriel Sudan y Wilhelm Ackermann , estudiaron los fundamentos de la computación. Sudan y Ackerman son famosos [1] por descubrir una función computable definida en todas partes (a veces llamada simplemente "recursiva") que no es recursiva primitiva . Sudán descubrió la función menos conocida Sudán , después de lo cual, independientemente de él, Ackerman publicó su función en 1928 . La función de Ackermann de tres argumentos se definió de tal forma que para ella realizaba la operación de suma, multiplicación o exponenciación: $\varphi$ ${\ estilo de visualización \ varphi (m, \, n, \, p)}$ ${\ estilo de visualización p = 0, \; 1, \; 2}$

{\ estilo de visualización \ varphi (m, \, n, \, 0) = m + n,}

\varphi (m,\,n,\,1)=m\cdot n,

{\ estilo de visualización \ varphi (m, \, n, \, 2) = m ^ {n},}

y para ello se amplía utilizando la notación de flecha de Knuth , publicada en 1976: $pag>2$

{\ estilo de visualización \ varphi (m, \, n, \, p) = m \ flecha arriba ^ {p-1} (n + 1)}

(Además de su papel histórico como la primera función computable recursiva no primitiva definida en todas partes, la función original de Ackermann extendió las operaciones aritméticas básicas más allá de la exponenciación, aunque no tan bien como las funciones dedicadas como la secuencia del hiperoperador de Goodstein ).

En Sobre el infinito, Hilbert conjeturó que la función de Ackermann no es primitivamente recursiva, y Ackerman (secretario personal de Hilbert y antiguo alumno) demostró esta conjetura en Sobre la construcción de los números reales de Hilbert. Rosa Peter y Raphael Robinson presentaron más tarde una versión de dos argumentos de la función de Ackermann, que muchos autores ahora prefieren a la original [2] .

Definición

La función de Ackermann se define recursivamente para enteros no negativos y de la siguiente manera: $metro$ $norte$

A(m,\;n)=\begin{casos}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m -1,\;A(m,\;n-1)),&m>0,\;n>0.\end{casos}

Puede que no parezca obvio que la recursividad siempre termina. Esto se deriva del hecho de que en una llamada recursiva, el valor de se reduce o el valor se conserva, pero el valor se reduce . Esto significa que cada vez que el par se reduce en términos de orden lexicográfico , lo que significa que el valor eventualmente llegará a cero: para un valor , hay un número finito de valores posibles (ya que la primera llamada con los datos fue hecho con algún valor particular , y además, si el valor se conserva, el valor solo puede disminuir), y el número de valores posibles , a su vez, también es finito. Sin embargo, cuando disminuye , el valor que aumenta es ilimitado y generalmente muy grande. $metro$ $metro$ $norte$ $(Minnesota)$ $metro$ $metro$ $norte$ $metro$ $norte$ $metro$ $norte$ $metro$ $metro$ $norte$

Tabla de valores

Consulte el operador hyper para obtener detalles sobre hyper .

$norte$ $\|m$	${\ estilo de visualización 0}$	$una$	$2$	$3$	$cuatro$	$5$	$metro$
${\ estilo de visualización 0}$	$una$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hiper}}(2,\;m,\;3)-3$
$una$	$2$	$3$	$5$	$13$	$65533$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}-3$	${\mathrm {hiper}}(2,\;m,\;4)-3$
$2$	$3$	$cuatro$	$7$	$29$	$2^{{65536}}-3$	$\soporte {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{{\soporte {2^{{2^ {{ \cdot ^{{\cdot ^{{\cdot ^{2))))))))))))_{{65536))))-3$	${\mathrm {hiper}}(2,\;m,\;5)-3$
$3$	$cuatro$	$5$	$9$	$61$	$2^{{2^{{65536}}}}-3$	$A(4,\;\soporte {2^{{2^{{\cdot ^({\cdot ^({\cdot ^{2))))))))))))_({\soporte { 2^ {{2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536))))-3)$	${\mathrm {hiper}}(2,\;m,\;6)-3$
$cuatro$	$5$	$6$	$once$	$125$	$2^{{2^{{2^{{65536}}}}}}-3$	$A(4,\;A(5,\;3))$	${\mathrm {hiper}}(2,\;m,\;7)-3$
$5$	$6$	$7$	$13$	$253$	$2^{{2^{{2^{{2^{{65536}}}}}}}}-3$	$A(4,\;A(5,\;4))$	${\mathrm {hiper}}(2,\;m,\;8)-3$
$norte$	$n+1$	$n+2$	$2n+3$	$2^{{n+3}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{n+3}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{({\underset {\underbrace {2^ {{ 2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536}}}{\vdots }}}}-3$ ( bloques totales ) $norte$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))}$	${\mathrm {hiper}}(2,\;m,\;n+3)-3$

Función inversa

Dado que la función crece muy rápidamente, la función inversa , denotada por , crece muy lentamente. Esta función se encuentra en el estudio de la complejidad de algunos algoritmos , por ejemplo, un sistema de conjuntos disjuntos o el algoritmo de Chazell para construir un árbol de expansión mínimo [3] . Al analizar las asintóticas , podemos suponer que para todos los números que ocurren en la práctica, el valor de esta función es menor que cinco, ya que no es menor que . $f(n)=A(n,\;n)$ $f^{{-1}}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}$ $\alfa$ ${\ estilo de visualización A (4, \, 4)}$ ${\ estilo de visualización 10 ^ {10 ^ {10 ^ {19500}}}}$

Uso en pruebas de rendimiento

La función de Ackerman, en virtud de su definición, tiene un nivel muy profundo de recursividad, que se puede utilizar para probar la capacidad del compilador para optimizar la recursividad. Yngwie Sundblad [4] fue el primero en utilizar la función de Ackerman para esto .

Brian Wichman (coautor de Whetstone benchmark ) tuvo en cuenta este artículo al escribir una serie de artículos sobre pruebas de optimización de llamadas [5] [6] [7] .

Por ejemplo, un compilador que al analizar un cálculo sea capaz de almacenar valores intermedios, por ejemplo, y pueda acelerar el cálculo cientos y miles de veces. También evaluar directamente en lugar de expandirse recursivamente acelerará bastante el cálculo. El cálculo toma tiempo lineal . El cálculo requiere tiempo cuadrático, ya que se expande en llamadas anidadas O ( ) para varios . El tiempo de cálculo es proporcional a . ${\ estilo de visualización A (3, \, 30)}$ ${\ estilo de visualización A (3, \, n)}$ ${\ estilo de visualización A (2, \, n)}$ ${\ estilo de visualización A (3, \, 30)}$ ${\ estilo de visualización A (2, \, n)}$ $A(1,\,A(1,\,A(1,\,\ldots A(1,\,0)\ldots )))$ ${\ estilo de visualización A (1, \, n)}$ $norte$ ${\ estilo de visualización A (2, \, n)}$ $norte$ ${\ estilo de visualización A (1, \, i)}$ $i$ ${\ estilo de visualización A (3, \, n)}$ ${\ estilo de visualización 4^{n+1}}$

El valor no se puede calcular con una simple aplicación recursiva en un tiempo razonable. En su lugar, se utilizan fórmulas abreviadas para optimizar las llamadas recursivas, como . ${\ estilo de visualización A (4, \, n)}$ $A(3,\,n)=8\cdot 2^{n}-3$

Una de las formas prácticas de calcular los valores de la función de Ackermann es la memorización de resultados intermedios. El compilador puede aplicar esta técnica a una función automáticamente usando las funciones de memo [8] [9] de Donald Michie .

Notas

↑ Cristian Calude, Solomon Marcus y Ionel Tevy . El primer ejemplo de una función recursiva que no es recursiva primitiva // Historia Matemática . : diario. - 1979. - noviembre ( vol. 6 , no. 4 ). - P. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Rafael M. Robinson . Recursión y doble recursión (neopr.) // Boletín de la sociedad matemática estadounidense . - 1948. - T. 54 , N º 10 . - S. 987-993 . -doi : 10.1090 / S0002-9904-1948-09121-2 . Archivado desde el original el 7 de junio de 2011.
↑ Matemáticas discretas: algoritmos. Árboles de expansión mínimos (enlace no disponible) . Consultado el 13 de agosto de 2011. Archivado desde el original el 2 de junio de 2010. (indefinido)
↑ Y. Sundblad . La función de Ackermann. Un estudio teórico, computacional y de manipulación de fórmulas (inglés) // BIT: revista. - 1971. - vol. 11 _ - pág. 107-119 . -doi : 10.1007/ BF01935330 . (enlace no disponible)
↑ Función de Ackermann: un estudio sobre la eficiencia de los procedimientos de llamada (1975). Consultado el 13 de agosto de 2011. Archivado desde el original el 23 de febrero de 2012. (indefinido)
↑ Cómo llamar a los procedimientos, o dudas sobre la función de Ackermann (1977). Consultado el 13 de agosto de 2011. Archivado desde el original el 23 de febrero de 2012. (indefinido)
↑ Últimos resultados de la prueba de llamada a procedimiento. Función de Ackermann (1982). Consultado el 13 de agosto de 2011. Archivado desde el original el 23 de febrero de 2012. (indefinido)
↑ Michie, Donald Funciones de Memo y aprendizaje automático, Nature , no. 218, págs. 19-22, 1968.
↑ Ejemplo: versión de la función memo explícita de la función de Ackermann Archivado el 17 de julio de 2011 en Wayback Machine implementado en PL/SQL.

Enlaces

Weisstein, Eric W. Ackermann Función (inglés) en el sitio web de Wolfram MathWorld .

Grandes números
Números	gogol Número de Shannon googolplex número de sesgos número de Moser número de graham ÁRBOL(3) Número de Rayo
Funciones	Función de Ackermann Función Veblen Funciones psi de Buchholz tetración pentación hiperoperador Jerarquía de rápido crecimiento Jerarquía de crecimiento lento Jerarquía resistente
Notaciones	Notación de Steinhaus-Moser Notación de flecha Knuth Notación de flecha de Conway Notación masiva de Bowers