# Funció d'Ackermann

En teoria de la computació, la funció d'Ackermann és una funció recursiva que pren dos nombres naturals com arguments i retorna un únic nombre natural. Com a norma general es defineix com segueix:
    $A(m,n)={\begin{cases}n+1,&{\mbox{si }}m=0;\\A(m-1,1),&{\mbox{si }}m>0{\mbox{ i }}n=0;\\A(m-1,A(m,n-1)),&{\mbox{si }}m>0{\mbox{ i }}n>0\end{cases}}$
Ara bé, a efectes pedagògics es pot utilitzar una versió alternativa:
    $f_{0}(x)=s(x)\,$
    $f_{1}(x)=f_{0}^{x+2}(x)=s^{x+2}(x)$
    $f_{2}(x)=f_{1}^{x+2}(x)=(s^{x+2})^{x+2}(x)$
    $f_{k+1}(x)=f_{k}^{x+2}(x)$
On $s(x)$ és la funció successora i $f^{n}(x)$ és la funció potència (aquella que aplica f $n$ vegades).

## Propietats

* Sigui $k\in \mathbb {N} ,\;f_{k}\in Frp$
* Sigui $\;a>b,\;f_{k}(a)>f_{k}(b)$
* Sigui $\;x,k\in \mathbb {N} ,\;f_{k}(x)>x$
* Sigui $\;k\in \mathbb {N} ,\;f_{k+1}(x)>f_{k}(x)$
A més, la funció d'Ackermann ($Ack(x)=f_{x}(x)$) no és FRP (funció recursiva primitiva). La demostració d'aquest teorema es du a terme per reducció a l'absurd i utilitzant la premissa que tota funció recursiva primitiva està majorada per una funció d'Ackermann.
Comencem suposant que $Ack(x)\in Frp$, per tant $Ack(x)+1\in Frp$
Fent servir la premissa de la majoració, ha d'existir un valor $k$ tal que $Ack(x)+1\leq f_{k}(x)$
Però llavors, com que això val per a tot $x$, també valdrà per a $x=k$.
$ACK(k)+1\leq f_{k}(k)$, fent servir la definició, trobem que:
$ACK(k)+1\leq ACK(k)$
Que és absurd.
Aquesta funció creix extremadament ràpid: el valor A (4,2) ja té 19.729 dígits. Aquest creixement desmesurat es pot utilitzar per demostrar que la funció computable f (n) = A (n, n) creix més ràpid que qualsevol altra funció recursiva primitiva, i per això no és recursiva primitiva.

## Taula de valors

    Nombres de $A(m{,}n)$ m\n 01234n 0 12345n + 1 1 23456n + 2 2 3579112n + 3 3 5132961125 $8\cdot 2^{n}-3$ 4 1365533$2^{65536}-3\approx 2\cdot 10^{19728}$  A(3,2$^{65536}$-3)A(3,A(4,3)) $2^{2^{\dots ^{2}}}-3$ ($n+3$ termes) 5 65533A(4,65533)A(4,A(5,1))A(4,A(5,2))A(4,A(5,3)) 6 A(5,1)A(5,A(5,1))A(5,A(6,1)) A(5,A(6,2))A(5,A(6,3))
Per fer-se una idea de la magnitud dels valors que apareixen de la fila 4 en endavant, es pot destacar que, per exemple, A (4, 2) és major que el nombre de partícules que formen l'univers elevat a la potència 200 i el resultat de A (5, 2) no es pot escriure, ja que no cabria en l'univers físic. En general, per sota de la fila 4, ja no és possible escriure tots els dígits del resultat de la funció.

## Explicació intuïtiva

La primera fila de la funció d'Ackerman conté els enters positius, ja que A (0, n) consisteix en sumar un a n. La resta de les files es poden veure com indireccions cap a la primera. En el cas de m = 1, es redirecciona cap a A (0, n + 1); tanmateix, la simplificació és una mica complicada:
* $=A\,(0,A(1,1))$
* $=A\,(0,A(0,A(1,0)))$
* $=A\,(0,A(0,2))$
* $=A\,(0,3)$
* $=4\,$
Es pot intentar amb un cas una mica més complicat, com A (4, 3); el primer valor que no cap en l'univers físic.
* $=A\,(3,A(4,2))$
* $=A\,(3,A(3,A(4,1)))$
* $=A\,(3,A(3,A(3,A(4,0))))$
* $=A\,(3,A(3,A(3,A(3,1))))$
* $=A\,(3,A(3,A(3,A(2,A(3,0)))))$
* $=A\,(3,A(3,A(3,A(2,A(2,1)))))$
* $=A\,(3,A(3,A(3,A(2,A(1,A(2,0))))))$
* $=A\,(3,A(3,A(3,A(2,A(1,A(1,1))))))$
* $=A\,(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))$
* $=A\,(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))$
* $=A\,(3,A(3,A(3,A(2,A(1,A(0,2))))))$
* $=A\,(3,A(3,A(3,A(2,A(1,3)))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(1,2))))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(0,A(0,2))))))$
* $=A\,(3,A(3,A(3,A(2,A(0,A(0,3)))))$
* $=A\,(3,A(3,A(3,A(2,A(0,4)))))$
* $=A\,(3,A(3,A(3,A(2,5))))$
Per continuar calculant aquest valor, caldria trobar que A (2, 5) val 13, i després avaluar A (3, 13), que és 8179. Tanmateix, el valor de A (3, 8179) és comparable al nombre d'àtoms de l'univers elevat a una potència de més de 12. Aquest nombre hauria de calcular-se per fer la crida més externa a la funció, però ja no seria possible escriure els dígits del resultat en l'univers físic.
Tot això per composició de l'única operació aritmètica que s'utilitza, és a dir, l'increment en un d'un valor (en el càlcul de A (0, n)).

## Descripció explícita

Intuïtivament, la funció d'Ackermann defineix la generalització de la multiplicació per dos (sumes iterades) i l'exponenciació en base 2 (productes iterats) fins a l'exponenciació iterada; la iteració de l'exponenciació iterada; la iteració de l'operació anterior; etc. Pot expressar-se de forma concisa i no recursiva mitjançant la notació de fletxa de Conway:
    $A(m,n)=2\rightarrow (n+3)\rightarrow (m-2)-3$
o els hiperoperadors:
    $A(m,n)=\mathrm {hyper} (2,n+3,m-2)-3\;$

## Història

El 1928, Wilhelm Ackermann va considerar una funció doblement recursiva A (m, n, p) de tres variables: m → n → p en la notació de Conway. Ackermann va demostrar que es tracta d'una funció recursiva que no és primitiva recursiva. Aquesta definició va ser simplificada per Rózsa Péter i Raphael Robinson a la versió de dues variables. Rozsa Peter també va demostrar que la doble recursió no es pot reduir a recursió primitiva (i que de la mateixa manera la triple recursió no es pot reduir a recursió primitiva i doble recursió, etc.).
Tanmateix, la primera funció doblement recursiva que no és recursiva primitiva va ser descoberta per Gabriel Suen el 1927:
    $F_{0}(x,y)=x+y,\,$
    $F_{n+1}(x,0)=x,\ n\geq 0\,$
    $F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0.\,$
Tant Sudan com Ackermann eren alumnes de David Hilbert en aquell moment.

## Anàlisi d'algorismes

Així com la funció diagonal f (n) = A (n, n) creix molt ràpidament, la seva inversa creix molt lentament i s'utilitza freqüentment en anàlisi d'algorismes. En aquest context, se sol redefinir la funció d'Ackermann per una altra de comportament asimptòtic similar, però evitant els termes −3, o partint de les potències de 2 per a la fila 0 (que equival a ometre les tres primeres files). Si bé el resultat d'aquestes variants no és idèntic al de la funció original, es poden veure com a similars en ser possible delimitar la diferència. En el cas de la inversa de la funció diagonal, el seu resultat és inferior a 4 per a entrades de pràcticament qualsevol mida, de manera que s'assimila a una funció constant.

## Mesura de comparació

A causa de la seva definició, profundament recursiva, la funció d'Ackermann s'utilitza amb freqüència per comparar compiladors pel que fa a la seva habilitat per optimitzar la recursió. Per exemple, un compilador capaç de notar que A (3, 30) es pot calcular basant-se en potències de 2, o que guarda resultats intermediaris tals com A (3, n) i A (2, n) en lloc de recalcular-los cada vegada, estalviaria temps d'execució per un factor de 100 o 1000. Igualment, en calcular directament A (1, n) en lloc de fer una trucada recursiva s'obtenen estalvis significatius.
És possible calcular el terme A (4, 2) però no recursivament, sinó per altres mitjans.

## Codi C

El codi en C és el següent:

## Codi d'Haskell

El codi d'Haskell és el següent:

## Codi de Prolog

El codi en Prolog és el següent:

## Codi d'Ada

El codi d'Ada és el següent:

## Codi en Python

El codi en Python (3.0) és el següent:

## Bibliografia

* Ackermann, Wilhelm: Zum Hilbertschen Aufbau der reelen Zahlen. Math. Annalen 99 (1928), pp. 118-133. doi:10.1007/BF01459088
* von Heijenoort, J. (ed.): From Frege to Gödel: A Source Book in Mathematical Logic. Cambridge: Harvard University Press, 1967. Disponible en línea Arxivat 2008-05-04 a Wayback Machine..
* Kozen, Dexter C.: The Design and Analysis of Algorithms. Springer, 1992.
* Robinson, Raphael M.: Recursion and double recursion. Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.
* Schöning, Uwe: Theoretische Informatik – kurzgefasst. Spektrum Akademischer. ISBN 3-8274-1099-1
* Sundblad, Yngve: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. BIT 11 (1971), 107-119.

## Referències

* ↑ «Ackermann's function» (en anglès americà). [Consulta: 2 febrer 2022].
* ↑ Ackermann Function. MathWorld
* ↑ «Ackermann function - Encyclopedia of Mathematics». [Consulta: 25 gener 2022].

## Enllaços externs

* Some values of the Ackermann function (anglès)
* Example use of the Ackermann function as a benchmark Arxivat 2004-08-24 a Wayback Machine. (anglès)
* L'expansió decimal de A(4,2) Arxivat 2008-03-17 a Wayback Machine. (anglès)