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 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 [2]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 "la función de Ackermann" puede referirse a cualquiera de las numerosas variantes de la función original. Una versión común, el de dos argumentos función Ackermann-Peter , se define como sigue para los números enteros no negativos m y n :
Su valor crece rápidamente, incluso para pequeños insumos. Por ejemplo, A (4, 2) es un número entero de 19,729 dígitos decimales [3] (equivalente a 2 65536 −3, o 2 2 2 2 2 −3).
Historia
A finales de la década de 1920, los matemáticos Gabriel Sudan y Wilhelm Ackermann , estudiantes de David Hilbert , estaban estudiando los fundamentos de la computación. Tanto a Sudán 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 de Sudán menos conocida , luego, poco después y de forma independiente, en 1928, Ackermann publicó su función(la letra griega phi ). La función de tres argumentos de Ackermann,, se define de tal manera que para , reproduce las operaciones básicas de suma , multiplicación y exponenciación como
y para p > 2 extiende estas operaciones básicas de una manera que se puede comparar con las hiperoperaciones :
(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 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, el secretario personal y ex alumno de Hilbert, quien de hecho 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 se convirtió en la preferida por muchos autores.
La secuencia de hiperoperación generalizada , p. Ej., también es una versión de la función de Ackermann. [9]
En 1963, RC Buck basó una variante intuitiva de dos variables ([10] ) sobre la secuencia de hiperoperación : [11]
En comparación con la mayoría de las otras versiones, la función de Buck no tiene compensaciones no esenciales:
Definición y propiedades
La función original de tres argumentos de Ackermann se define recursivamente de la siguiente manera para enteros no negativos y :
De las diversas versiones de dos argumentos, la desarrollada por Péter y Robinson (llamada "la" función de Ackermann por algunos autores) se define para enteros no negativos y como sigue:
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 o disminuye, o sigue siendo el mismo y disminuye. Cada vez que llega a cero, disminuye, entonces eventualmente también llega a cero. (Expresado más técnicamente, en cada caso el pardisminuciones en el orden lexicográfico en pares, que es un buen ordenamiento , al igual que el ordenamiento de enteros simples no negativos; esto significa que uno no puede descender en el orden infinitas veces seguidas.) Sin embargo, cuando disminuye no hay límite superior en cuanto puede aumentar y, a menudo, aumentará considerablemente.
La función Péter-Ackermann también se puede expresar en relación con varias otras versiones de la función Ackermann:
- hiperoperación , representada en la notación de flecha hacia arriba de Knuth (extendida a índices enteros):
- hiperoperación , representada en notación de flechas encadenadas de Conway :
- Por eso
- ( y correspondería con y , que lógicamente podría agregarse).
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 ). Parasin embargo, crece mucho más rápidamente; inclusoes aproximadamente 2 × 10 19 728 , y la expansión decimal de A (4, 3) es muy grande según cualquier medida típica.
Un aspecto interesante de la función (Péter-) Ackermann 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, por lo que también es extremadamente grande. En realidad, en la mayoría de los casos, el tiempo de ejecución es mucho mayor que la salida; vea abajo.
Una versión de un solo argumento eso aumenta tanto y al mismo tiempo empequeñece todas las funciones recursivas primitivas, incluidas las funciones de crecimiento muy rápido como la función exponencial , la función factorial, las funciones multifactoriales y superfactoriales , e incluso las funciones definidas utilizando la notación de flecha hacia arriba de Knuth (excepto cuando la flecha hacia arriba indexada se utiliza). Se puede ver que es aproximadamente comparable a en la jerarquía de rápido crecimiento . Este crecimiento extremo puede aprovecharse para demostrar queque 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.
En una categoría con exponenciales , usando el isomorfismo(en informática, esto se llama currización ), la función de Ackermann se puede definir mediante recursividad primitiva sobre funcionales de orden superior de la siguiente manera:
donde S ( n ) = n + 1 es la función sucesora habitual e Iter denota el operador de potencia funcional , definido también por recursividad primitiva:
La función definido de esta manera concuerda con la función de Ackermann definido arriba: .
Expansiones de ejemplo
Para ver cómo la función de Ackermann crece tan rápidamente, es útil expandir algunas expresiones simples usando las reglas de la definición original. Por ejemplo, uno puede evaluar completamente de la siguiente manera:
Para demostrar como El cálculo de 'da como resultado muchos pasos y en un gran número:
Tabla de valores
El cálculo de la función de Ackermann se puede reformular 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 parte superior izquierda de la tabla:
norte metro | 0 | 1 | 2 | 3 | 4 | norte |
---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | |
1 | 2 | 3 | 4 | 5 | 6 | |
2 | 3 | 5 | 7 | 9 | 11 | |
3 | 5 | 13 | 29 | 61 | 125 | |
4 | 13 | 65533 | 2 65536 - 3 | | | |
5 | 65533 | |||||
6 | ||||||
metro |
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 anotar 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:
norte metro | 0 | 1 | 2 | 3 | 4 | norte |
---|---|---|---|---|---|---|
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)) |
Prueba de que la función de Ackermann no es recursiva primitiva
En cierto sentido, 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.
Específicamente, se muestra que para cada función recursiva primitiva existe un entero no negativo tal que para todos los enteros no negativos ,
Una vez que esto se establece, se sigue que en sí mismo no es recursivo primitivo, ya que de lo contrario llevaría a la contradicción
La prueba [12] procede de la siguiente manera: define la clase de todas las funciones que crecen más lentamente que la función de Ackermann
y demuestre 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 se cierra bajo las operaciones de composición de funciones y recursividad primitiva.
Tenga en cuenta que no ser recursivo primitivo no significa que no se pueda calcular utilizando un bucle for. [13]
Inverso
Dado que la función f ( n ) = A ( n , n ) considerada anteriormente crece muy rápidamente, su función inversa , f −1 , crece muy lentamente. Esta función de Ackermann inversa f −1 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 .
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, la función original de Ackermann u otras variaciones se utilizan en estos entornos, pero todas crecen a tasas igualmente altas. En particular, algunas funciones modificadas simplifican la expresión al eliminar el −3 y términos similares.
Una variación de dos parámetros de la función de Ackermann inversa se puede definir de la siguiente manera, donde es la función de piso :
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í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 2 n a veces se reemplaza por n , y la función de piso a veces se reemplaza por un techo .
Otros estudios podrían definir una función inversa de una donde m se establece en una constante, de modo que la inversa se aplica a una fila en particular. [14]
La inversa de la función de Ackermann es recursiva primitiva. [15]
Usar como punto de referencia
La función de Ackermann, debido a su definición en términos de recursividad extremadamente profunda, se puede utilizar 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 [16] y, casi simultáneamente, en 1971, por Yngve Sundblad. [17]
Brian Wichmann (coautor del punto de referencia Whetstone ) retomó el artículo fundamental de Sundblad en una trilogía de artículos escritos entre 1975 y 1982. [18] [19] [20]
Ver también
- Teoría de la computabilidad
- Doble recursividad
- Jerarquía de rápido crecimiento
- Función de Goodstein
- Función recursiva primitiva
- Recursión (informática)
Referencias
- ^ Monin y Hinchey 2003 , p. 61.
- ↑ a b Ackermann, 1928 .
- ^ "Expansión decimal de A (4,2)" . kosara.net . 27 de agosto de 2000. Archivado desde el original el 20 de enero de 2010.
- ^ Calude, Marcus y Tevy 1979 .
- ↑ Hilbert , 1926 , pág. 185.
- ↑ van Heijenoort, 1967 .
- ^ Péter, 1935 .
- ^ Robinson, 1948 .
- ^ Ritchie , 1965 , p. 1028.
- ^ con orden de parámetros invertido
- ^ Buck 1963 .
- ^ Woo, Chi (17 de diciembre de 2009). "La función de Ackermann no es recursiva primitiva | planetmath.org" . planetmath.org . Archivado desde el original el 9 de mayo de 2013.
- ^ "El bucle Koop (función de Ackermann en un bucle For) | timkoop" . timkoop.com . 2021-04-27. Archivado desde el original el 27 de abril de 2021 . Consultado el 27 de abril de 2021 .
- ^ Pettie 2002 .
- ^ Matos 2014 .
- ^ Vaida 1970 .
- ^ Sundblad, 1971 .
- ^ Wichmann, 1976 .
- ^ Wichmann 1977 .
- ^ Wichmann, 1982 .
Bibliografía
- Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen" . Mathematische Annalen . 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, Salomón ; 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 .
- van Heijenoort, Jean (1967). De Frege a Gödel: un libro de consulta en lógica matemática, 1879-1931 . Prensa de la Universidad de Harvard.
- Hilbert, David (1926). "Über das Unendliche". Mathematische Annalen . 95 : 161-190. doi : 10.1007 / BF01206605 . S2CID 121888793 .
- Matos, Armando B (7 de mayo de 2014). "La inversa de la función de Ackermann es primitiva recursiva" (PDF) .
- Koop, Tim (25 de abril de 2021). "Función de Ackermann implementada con un bucle for" .
- Monin, Jean-Francois; Hinchey, MG (2003). Comprensión de los métodos formales . Saltador. pag. 61. ISBN 9781852332471.
- Péter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Mathematische Annalen . 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 del árbol de expansión mínimo en línea". El 43º Simposio anual del IEEE sobre fundamentos de la informática, 2002. Actas : 155–163. doi : 10.1109 / SFCS.2002.1181892 . ISBN 0-7695-1822-2. S2CID 8636108 .
- 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 M. (1948). "Recursión y doble recursividad" . 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 Matemáticas numéricas . 11 (1): 107-119. doi : 10.1007 / BF01935330 . S2CID 123416408 .
- Vaida, Dragoș (1970). "Validación del compilador para un lenguaje tipo Algol". Boletín Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie . Nouvelle série. 14 (62) (4): 487–502. JSTOR 43679758 .
- Wichmann, Brian A. (marzo de 1976). "Función de Ackermann: un estudio sobre la eficacia de los procedimientos de llamada". BIT Matemáticas numéricas . 16 : 103-110. doi : 10.1007 / BF01940783 . S2CID 16993343 .
- Wichmann, Brian A. (julio de 1977). "Cómo llamar a 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) .
enlaces externos
- "Función de Ackermann" . Enciclopedia de Matemáticas . EMS Press . 2001 [1994].
- Weisstein, Eric W. "Función de Ackermann" . MathWorld .
- Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "Función de Ackermann" . Diccionario de algoritmos y estructuras de datos .
- Una calculadora de funciones de Ackermann animada
- Función de Ackerman implementada usando un bucle for
- Scott Aaronson , ¿Quién puede nombrar el número más grande? (1999)
- Funciones de Ackermann . Incluye una tabla de algunos valores.
- Hiperoperaciones: función de Ackermann y nueva operación aritmética
- Grandes Números de Robert MUNAFO describe varias variaciones en la definición de una .
- Gabriel Nivasch, Inverse Ackermann sin dolor en la función inversa de Ackermann.
- Raimund Seidel, Comprensión de la función inversa de Ackermann (presentación en PDF).
- La función de Ackermann escrita en diferentes lenguajes de programación (en código Rosetta )
- Función de Ackermann ( Archivado el 24 de octubre de 2009) —Algunos estudios y programación de Harry J. Smith.