stringtranslate.com

Función de Ackermann

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]

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 adición , multiplicación y exponenciación como

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

(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]

En 1963, RC Buck basó una variante intuitiva de dos variables [n 1] en la secuencia de hiperoperaciones : [10] [11]

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

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 :

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:

La función de Ackermann también se ha expresado en relación con la secuencia de hiperoperaciones : [14] [15]

o, escrito en la notación de flecha hacia arriba de Knuth (extendida a índices enteros ):
o, equivalentemente, en términos de la función de Buck F: [10]

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

Definir como la n -ésima iteración de :

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 .

Concibiendo la función de Ackermann como una secuencia de funciones unarias, se puede establecer .

La función se convierte entonces en una secuencia de funciones unarias [n 2] , definidas a partir de la iteración :

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]

Ejemplo

Calcular

La secuencia de reducción es [n 3]

Para el cálculo se puede utilizar una pila , que inicialmente contiene los elementos .

Luego se reemplazan repetidamente los dos elementos superiores según las reglas [n 4]

Esquemáticamente, partiendo de :

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 ,

Observaciones

Su propio algoritmo, inherentemente iterativo, calcula dentro del tiempo y dentro del espacio.

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

Como la composición de funciones es asociativa, en lugar de la regla r6 se puede definir

Al igual que en la sección anterior, el cálculo se puede implementar con una pila.

Inicialmente la pila contiene los tres elementos .

Luego se reemplazan repetidamente los tres elementos superiores según las reglas [n 4]

Esquemáticamente, partiendo de :

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

Las igualdades correspondientes son

Cuando se utiliza la regla de reducción r7 en lugar de la regla r6, los reemplazos en la pila seguirán

Las configuraciones de pila sucesivas serán entonces

Las igualdades correspondientes son

Observaciones

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 :

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

La función de Buck , [10] una variante de la función de Ackermann, se puede calcular con las siguientes reglas de reducción:

En lugar de la regla b6 se puede definir la regla

Para calcular la función de Ackermann basta con sumar tres reglas de reducción

Estas reglas se encargan del caso base A(0,n), la alineación (n+3) y el error (-3).

Ejemplo

Calcular

Las igualdades coincidentes son

Observaciones

Enormes números

Para demostrar cómo se calculan los resultados en muchos pasos y en un gran número: [n 5]

Tabla de valores

El cálculo de la función de Ackermann se puede replantear en términos de una tabla infinita. Primero, se colocan los números naturales en la fila superior. Para determinar un número en la tabla, se toma el número inmediatamente a la izquierda. Luego, se utiliza ese número para buscar el número requerido en la columna dada por ese número y una fila más arriba. Si no hay ningún número a su izquierda, simplemente se mira la columna encabezada por "1" en la fila anterior. A continuación, se muestra una pequeña parte 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

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 crecimiento rápido, pero la función de Ackermann crece al menos tan rápido como .

En concreto, se demuestra que para cada función recursiva primitiva existe un entero no negativo tal que para todos los enteros no negativos ,

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

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.

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.

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 −1 , crece muy lentamente. Esta función inversa de Ackermann f −1 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 . 

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 :

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 2 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

Notas

  1. ^ con orden de parámetros invertido
  2. ^ ' al curry '
  3. ^ En cada paso se reescribe el redex subrayado .
  4. ^ ab aquí: ¡estrategia más a la izquierda y más al interior!
  5. ^ abcd 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. ^Por 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. ^Abc Buck 1963.
  11. ^ Meeussen y Zantema 1992, pág. 6.
  12. ^ Munafo 1999a.
  13. ^ Ritchie 1965.
  14. ^ desde 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

Enlaces externos