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:[1]

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

On és la funció successora i és la funció potència (aquella que aplica f vegades).

Propietats modifica

  • Sigui  
  • Sigui  
  • Sigui  
  • Sigui  

A més, la funció d'Ackermann ( ) no és FRP (funció recursiva primitiva).[2] 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  , per tant  

Fent servir la premissa de la majoració, ha d'existir un valor   tal que  

Però llavors, com que això val per a tot  , també valdrà per a  .

 , fent servir la definició, trobem que:

 

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.[3]

Taula de valors modifica

Nombres de  
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  
4 13 65533    A(3,265536-3) A(3,A(4,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

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:

   
 
 
 
 

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.

   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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:

 

o els hiperoperadors:

 

Història modifica

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:

 
 
 

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

Anàlisi d'algorismes modifica

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ó modifica

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

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

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

Codi de Prolog modifica

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

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;

Codi en Python modifica

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

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

Bibliografia modifica

  • 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 modifica

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

Enllaços externs modifica