Mostra la font per a Funció d'Ackermann

En [[teoria de la computació]], la '''funció d'Ackermann''' és una [[funció recursiva]] que pren dos [[nombre natural|nombres naturals]] com arguments i retorna un únic nombre natural. Com a norma general es defineix com segueix:<ref>{{Ref-web|títol=Ackermann's function|url=https://xlinux.nist.gov/dads/HTML/ackermann.html|consulta=2022-02-02|llengua=en-US}}</ref>

:<math>
 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}
 </math>

Ara bé, a efectes [[pedagogia|pedagògics]] es pot utilitzar una versió alternativa:

:<math> f_{0}(x) = s(x) \,</math>

:<math>f_{1}(x) = f_{0}^{x+2}(x) = s^{x+2}(x)</math>

:<math>f_{2}(x) = f_{1}^{x+2}(x) = (s^{x+2})^{x+2}(x)</math>

:<math>f_{k+1}(x) = f_{k}^{x+2}(x)</math>

On <math>s(x)</math> és la funció successora i <math>f^{n}(x)</math> és la funció [[Potenciació|potència]] (aquella que aplica ''f'' <math>n</math> vegades).

== Propietats ==
* Sigui <math>k \in \mathbb{N},\; f_{k} \in Frp</math>
* Sigui <math>\; a > b,\; f_{k}(a) > f_{k}(b)</math>
* Sigui <math>\; x,k \in \mathbb{N},\; f_{k}(x) > x</math>
* Sigui <math>\; k \in \mathbb{N},\; f_{k+1}(x) > f_{k}(x)</math>

A més, la funció d'Ackermann (<math> Ack(x) = f_{x}(x) </math>) '''no''' és FRP (funció recursiva primitiva).<ref>[https://mathworld.wolfram.com/AckermannFunction.html Ackermann Function]. MathWorld</ref> La demostració d'aquest [[teorema]] es du a terme per [[reducció a l'absurd]] i utilitzant la [[premissa]] que tota [[funció recursiva primitiva]] està [[majoració|majorada]] per una funció d'Ackermann.

Comencem suposant que <math> Ack(x) \in Frp </math>, per tant <math> Ack(x)+1 \in Frp </math>

Fent servir la premissa de la majoració, ha d'existir un valor <math>k</math> tal que <math> Ack(x)+1 \le f_{k}(x) </math>

Però llavors, com que això val per a tot <math>x</math>, també valdrà per a <math>x = k</math>.

<math>ACK(k)+1 \le f_{k}(k) </math>, fent servir la definició, trobem que:

<math>ACK(k)+1 \le ACK(k)</math>

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.<ref>{{Ref-web|títol=Ackermann function - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/index.php?title=Ackermann_function|consulta=2022-01-25}}</ref>

== Taula de valors ==
:{| cellpadding=2 class=wikitable border=1
|+ '''Nombres de <math>A(m{,}n)</math>'''
|----- 
! ''m''\''n''
! 0 !! 1 !! 2 !! 3 !! 4 !! ''n''
|-----
! 0
| 1 || 2 || 3 || 4 || 5 || ''n'' +&nbsp;1
|-----
! 1
| 2 || 3 || 4 || 5 || 6 || ''n'' +&nbsp;2
|-----
! 2
| 3 || 5 || 7 || 9 || 11 || 2''n'' +&nbsp;3
|-----
! 3
| 5 || 13 || 29 || 61 || 125
| <math>8\cdot 2^n-3</math>
|-----
! 4
| 13 || 65533 || <math>2^{65536}-3 \approx 2 \cdot 10^{19728}</math>&nbsp;
| A(3,2<sup>65536</sup>-3) || A(3,A(4,3))
| <math>2^{2^{\dots^2}}-3</math> (<math>n+3</math> termes)
|-----
! 5
| 65533 || A(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 [[Suma|sumar]] un a ''n''. La resta de les files es poden veure com indireccions cap a la primera. En el cas de ''m'' =&nbsp;1, es redirecciona cap a ''A'' (0, ''n'' &nbsp;+&nbsp;1); tanmateix, la simplificació és una mica complicada:

{| style="margin-left: 212px;"
|-
| <math>A\,(1, 2)</math>
| <math>= A\,(0, A(1, 1))</math>
|-
| || <math>= A \,(0, A(0, A(1, 0)))</math>
|-
| || <math>= A\,(0, A(0, 2))</math>
|-
| || <math>= A \,(0, 3)</math>
|-
| || <math>= 4\,</math>
|}

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.

{| style="margin-left: 212px;"
|-
| <math>A \,(4, 3)</math>
| <math>= A \, (3, A(4, 2))</math>
|-
| || <math>= A \, (3, A(3, A(4, 1)))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(4, 0))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(3, 1))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(3, 0)))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(2, 1)))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, A(2, 0))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, A(1, 1))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, A(0, 2))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(1, 3)))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(1, 2))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, A(0, 3)))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, A(0, 4)))))</math>
|-
| || <math>= A \, (3, A(3, A(3, A(2, 5))))</math>
|}

Per continuar [[Càlcul (matemàtiques)|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 ([[Suma|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]]:
:<math>A(m,n)=2\rightarrow (n+3)\rightarrow (m-2)-3</math>
o els [[hiperoperadors]]:
:<math>A(m,n)=\mathrm{hyper}(2,n+3,m-2)-3 \;</math>

== Història ==
El [[1928]], [[Wilhelm Ackermann]] va considerar una funció doblement recursiva ''A'' (''m'', ''n'', ''p'') de tres variables: ''m'' &nbsp;→ ''n'' &nbsp;→ ''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]]:

:<math>F _0 (x, y) = x+y,\,</math>
:<math>F _{n+1} (x, 0) = x, \ n \ge 0\,</math>
:<math>F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,</math>

Tant Sudan com Ackermann eren alumnes de [[David Hilbert]] en aquell moment.

== Anàlisi d'algorismes ==
Així com la funció diagonal ''f'' (''n'') &nbsp;= ''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 [[notació de Landau|comportament asimptòtic]] similar, però evitant els termes −3, o partint de les [[Potència de 2|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 [[compilador]]s 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 font|codi]] en [[C (llenguatge de programació)|C]] és el següent:
<pre><nowiki>
int Ackermann(int p, int q)
{
 if(p==0) return q+1;
 else if(q==0) return Ackermann(p-1,1);
 else return Ackermann(p-1,Ackermann(p,q-1));
}
</nowiki></pre>

== Codi d'Haskell ==
El codi d'[[Haskell]] és el següent:
<pre><nowiki>ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))</nowiki></pre>

== Codi de Prolog ==
El codi en [[Prolog]] és el següent:
<pre><nowiki>
ackermann(0,N,R):- R is N+1.
ackermann(M,0,R):- M1 is M-1,
 ackermann(M1,1,R).
ackermann(M,N,R):- M1 is M-1,
	 N1 is N-1,
		 ackermann(M,N1,R1),
		 ackermann(M1,R1,R).
</nowiki></pre>

== Codi d'Ada ==
El codi d'[[Ada (llenguatge de programació)|Ada]] és el següent:
<pre><nowiki>
function Ackermann (m, n : Integer) return Integer is
begin
 if m = 0 then
 return n + 1;
 elsif m > 0 and n = 0 then
 return Ackermann (m - 1, 1);
 elsif m > 0 and n > 0 then
 return Ackermann (m - 1, Ackermann (m, n - 1));
 end if;
end Ackermann;
</nowiki></pre>

== Codi en Python ==
El codi en [[Python]] (3.0) és el següent:
<pre><nowiki>
def ackermann(m,n):
 if m == 0: return n+1
 elif m > 0 and n == 0: return ackermann(m-1,1)
 elif m > 0 and n > 0: return ackermann(m-1, ackermann(m,n-1))
</nowiki></pre>

== 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]]: [[Universidad Harvard|Harvard University]] Press, [[1967]]. Disponible [http://mathgate.info/cebrown/notes/vonHeijenoort.php en línea] {{Webarchive|url=https://web.archive.org/web/20080504224223/http://mathgate.info/cebrown/notes/vonHeijenoort.php |date=2008-05-04}}.
* Kozen, Dexter C.: ''The Design and Analysis of Algorithms''. Springer, [[1992]].
* [[Raphael Robinson|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 ==
{{Referències}}

== Enllaços externs ==
* [http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm Some values of the Ackermann function] {{en}}
* [http://www.xgc.com/benchmarks/benchmarks.htm Example use of the Ackermann function as a benchmark] {{Webarchive|url=https://web.archive.org/web/20040824145131/http://www.xgc.com/benchmarks/benchmarks.htm |date=2004-08-24}} {{en}}
* [http://www.kosara.net/thoughts/ackermann42.html L'expansió decimal de A(4,2)] {{Webarchive|url=https://web.archive.org/web/20080317104411/http://www.kosara.net/thoughts/ackermann42.html |date=2008-03-17}} {{en}}

{{Hiperoperacions}}
{{Autoritat}}

{{ORDENA:Funcio D'Ackermann}}
[[Categoria:Funcions usades en la teoria de nombres|Ackermann]]
[[Categoria:Computabilitat]]
[[Categoria:Funcions|Ackermann]]