Funció d'Ackermann

De Viquipèdia
Dreceres ràpides: navegació, cerca

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{ y }n=0;
 \\
 A(m-1, A(m, n-1)), &\mbox{si }m>0\mbox{ y }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ó successor i f^{n}(x) és la funció potència (aquella que aplica f n vegades).

Propietats[modifica | modifica el codi]

  • 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 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 premisa que tota funció recursiva primitiva està majorada per una funció Ackermann.

Comencem suposant que  Ack(x) \in Frp , per tant  Ack(x)+1 \in Frp

Fent servir la premisa de la majoració, ha d'existir un k tal que  Ack(x)+1 \le f_{k}(x)

Però llavors, com que això val per a tot x, també valdrà per a x=k

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

ACK(k)+1 \le 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[modifica | modifica el codi]

Nombres de A(m{,}n)
m\n 0 1 2 3 4 n
0 1 2 3 4 5 n + 1
1 2 3 4 5 6 n + 2
2 3 5 7 9 11 2n + 3
3 5 13 29 61 125 8\cdot 2^n-3
4 13 65533 2^{65536}-3 \approx 2 \cdot 10^{19728}  A(3,265536-3) A(3,A(4,3)) 2^{2^{\dots^2}}-3 (n+3 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[modifica | modifica el codi]

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 \,(1, 2)
 
 
 
 
= 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 \,(4, 3)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
= 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[modifica | modifica el codi]

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[modifica | modifica el codi]

El 1928, Wilhelm Ackermann va considerar una funció doblement recursiva A (mnp) 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 \ge 0\,
F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,

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

Anàlisi d'algoritmes[modifica | modifica el codi]

Així com la funció diagonal  f  (n)  = A (nn) creix molt ràpidament, la seva inversa creix molt lentament i s'utilitza freqüentment en anàlisi d'algoritmes. 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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

El codi en C és el següent:

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));
}

Codi d'Haskell[modifica | modifica el codi]

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

ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))
Vegeu també: Haskell

Codi de Prolog[modifica | modifica el codi]

El codi en Prolog és el següent:

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).

Codi d'Ada[modifica | modifica el codi]

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

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;

Bibliografia[modifica | modifica el codi]

  • Ackermann, Wilhelm: Zum Hilbertschen Aufbau der reelen Zahlen. Math. Annalen 99 (1928), pp. 118-133.
  • von Heijenoort, J. (ed.): From Frege to Gödel: A Source Book in Mathematical Logic. Cambridge: Harvard University Press, 1967. Disponible en línea.
  • 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.

Enllaços externs[modifica | modifica el codi]