Funció de Ackermann

Wilhelm Ackermann, matemàtic alemà, creador de la Funció de Ackermann.

En teoria de la computació, una funció de Ackermann és una funció matemàtica recursiva trobada en 1926 per Wilhelm Ackermann. Té un creiximent extremadament ràpit, lo que és d'interés per a la ciència computacional teòrica i la teoria de la computabilidad. Hui en dia hi ha una série de funcions que són cridades funcions de Ackermann. Totes elles tenen una forma pareguda a la funció original de Ackermann i també tenen un comportament de creiximent similar. En la seua versió moderna estàndar, esta funció pren dos número natural com a arguments i torna un únic número natural, i es pot definir de la següent manera:

$A(m,n)=\{\begin{array}{cc}n+1,& \text{si }m=0;\\ A(m-1,1),& \text{si }m>0\text{ y }n=0;\\ A(m-1,A(m,n-1)),& \text{si }m>0\text{ y }n>0\end{array}$

Propietats

• Siga $k\in \mathbb{N},f_k\in \mathrm{F}\mathrm{R}\mathrm{P}$
• Siga $a>b,f_k(a)>f_k(b)$
• Siga $x,k\in \mathbb{N},f_k(x)>x$
• Siga $k\in \mathbb{N},f_{k+1}(x)>f_k(x)$

Ademés la funció de Ackerman ($\mathrm{A}\mathrm{C}\mathrm{K}(x)=f_x(x)$) no és FRP (funció recursiva primitiva). La demostració d'esta teorema es porta a terme per reducció a l'absurt i utilisant el lema de que tota funció recursiva primitiva està mayorada per una funció de Ackermann.

Comencem suponent que $\mathrm{A}\mathrm{C}\mathrm{K}(x)\in \mathrm{F}\mathrm{R}\mathrm{P}$, per tant $\mathrm{A}\mathrm{C}\mathrm{K}(x)+1\in \mathrm{F}\mathrm{R}\mathrm{P}$

Usant el lema de la mayoración, deu existir un k tal que $\mathrm{A}\mathrm{C}\mathrm{K}(x)+1\le f_k(x)$

Pero llavors, com açò val per a tot x, també valdrà per a x=k.

$\mathrm{A}\mathrm{C}\mathrm{K}(k)+1\le f_k(k)$, usant la definició, apleguem a que:

$\mathrm{A}\mathrm{C}\mathrm{K}(k)+1\le \mathrm{A}\mathrm{C}\mathrm{K}(k)$

La qual cosa és absurt.

Esta funció creix extremadament ràpit: el valor A(4,2) ya té 19.729 dígits. Este creiximent desmesurat es pot utilisar per a demostrar que la funció computable f(n) = A(n, n) creix més ràpit que qualsevol funció recursiva primitiva, i per això no és recursiva primitiva.

Taula de valors

Números de $(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$ térmens)
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 a fer-se una idea de la magnitut dels valors que apareixen de la fila 4 en avant, es pot destacar que, per eixemple, A(4, 2) és major que el número de partícules que formen l'univers elevat a la potència 200 i el resultat de A(5, 2) no es pot escriure ya que no cabria en l'Univers físic. En general, per baix de la fila 4 ya no és possible escriure tots els dígits del resultat de la funció.

Vore també

• Número de Graham

Bibliografia

• Ackermann, Wilhelm: Zoom 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 llí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.