Función de Ackermann

Na teoría da computación, unha función de Ackermann é unha función matemática recursiva atopada en 1926 por Wilhelm Ackermann. Esta función ten un crececemento moi rápido, grazas a isto e relevante na ciencia computacional teórica e a teoría da computabilidade. A día de hoxe existen varias funcións as que se lle denominan funcións de Ackermann, todas elas teñen unha forma semellante a función orixinal e tamén cun crecemento moi rápido. Na súa versión moderna estándar, esta función toma dous números naturais como argumentos e devolve un único número natural, e pódese definir da seguinte maneira:

A(m,n)={\begin{cases}n+1,&{\mbox{se }}m=0;\\A(m-1,1),&{\mbox{se }}m>0{\mbox{ e }}n=0;\\A(m-1,A(m,n-1)),&{\mbox{se }}m>0{\mbox{ e  }}n>0\end{cases}}

Propiedades

Sexa $k\in \mathbb {N} ,\;f_{k}\in \mathrm {FRP}$ (función recursiva primitiva)
Sexa $\;a>b,\;f_{k}(a)>f_{k}(b)$
Sexa $\;x,k\in \mathbb {N} ,\;f_{k}(x)>x$
Sexa $\;k\in \mathbb {N} ,\;f_{k+1}(x)>f_{k}(x)$

Ademais a función de Ackerman ( $\mathrm {ACK} (x)=f_{x}(x)$ ) non é unha función recursiva primitiva. Isto pódese demostrar facendo unha redución ao absurdo, utilizando o lema de que toda función recursiva primitiva está maiorada por unha función de Ackermann.

Comezamos supoñendo que, $\mathrm {ACK} (x)\in \mathrm {FRP}$ por tanto $\mathrm {ACK} (x)+1\in \mathrm {FRP}$

Usando o lema da maioración, debe existir un k tal que

$\mathrm {ACK} (x)+1\leq f_{k}(x)$

Pero entón, como isto vale para todo x, tamén valerá para x=k.

$\mathrm {ACK} (k)+1\leq f_{k}(k)$ , usando a definición, chegamos a que:

$\mathrm {ACK} (k)+1\leq \mathrm {ACK} (k)$

O cal é absurdo.

O crecemento desta función e esaxeradamente rápido: o valor A(4,2) xa ten case $2\cdot 10^{5}$ díxitos. Este crecemento desmesurado podémolo utlizar para probar que a función computable f(n) = A(n, n) crece máis rápido que calquera función recursiva primitiva, e por iso non pode ser recursiva primitiva.

Táboa de valores

Para calcular a función de Ackermann, esta pódese reformular en termos dunha táboa infinita. En primeiro lugar, coloque os números naturais ao longo da fila superior. Para determinar un valor na táboa, tome o número inmediatamente á esquerda. A continuación, use ese número para procurar o número necesario na columna indicada por ese número e unha fila cara arriba. Se non hai ningún número á súa esquerda, basta con mirar a columna encabezada "1" na fila anterior. Aquí temos unha pequena parte da táboa comezando por arriba e a esquerda:

Valores de A(m, n)
n m	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	2⁶⁵⁵³⁶ − 3	${2^{2^{65536}}}-3$	${2^{2^{2^{65536}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$
	$={2^{2^{2}}}-3$ $=2\uparrow \uparrow 3-3$	$={2^{2^{2^{2}}}}-3$ $=2\uparrow \uparrow 4-3$	$={2^{2^{2^{2^{2}}}}}-3$ $=2\uparrow \uparrow 5-3$	$={2^{2^{2^{2^{2^{2}}}}}}-3$ $=2\uparrow \uparrow 6-3$	$={2^{2^{2^{2^{2^{2^{2}}}}}}}-3$ $=2\uparrow \uparrow 7-3$
	$={2^{2^{2}}}-3$ $=2\uparrow \uparrow 3-3$	$={2^{2^{2^{2}}}}-3$ $=2\uparrow \uparrow 4-3$	$={2^{2^{2^{2^{2}}}}}-3$ $=2\uparrow \uparrow 5-3$	$={2^{2^{2^{2^{2^{2}}}}}}-3$ $=2\uparrow \uparrow 6-3$	$={2^{2^{2^{2^{2^{2^{2}}}}}}}-3$ $=2\uparrow \uparrow 7-3$	$=2\uparrow \uparrow (n+3)-3$
5	65533 $=2\uparrow \uparrow (2\uparrow \uparrow 2)-3$ $=2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
m	$(2\to 3\to (m-2))-3$	$(2\to 4\to (m-2))-3$	$(2\to 5\to (m-2))-3$	$(2\to 6\to (m-2))-3$	$(2\to 7\to (m-2))-3$	$(2\to (n+3)\to (m-2))-3$

Os números que aquí se expresan só con exponenciación recursiva ou frechas de Knuth son moi grandes e ocuparían demasiado espazo para anotarse en díxitos decimais simples.

A magnitude destes valores é tal, que por exemplo A(4,2) é maior que o número de partículas que forman o universo elevado á potencia de 200, e o valor de A(5,2) non se podería escribir, xa que non entraría no Universo físico. En xeral, por baixo da fila 4 xa non é posible escribir todos os díxitos do resultado da función.

Agora imos mostrar unha repetición da táboa anterior, mais os valores son substituídos pola expresión relevante da definición da función para mostrar claramente o modelo:

Valores de A(m, n)
n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(0, 1)	A(0, A(1, 0)) = A(0, 2)	A(0, A(1, 1)) = A(0, 3)	A(0, A(1, 2)) = A(0, 4)	A(0, A(1, 3)) = A(0, 5)	A(0, A(1, n−1))
2	A(1, 1)	A(1, A(2, 0)) = A(1, 3)	A(1, A(2, 1)) = A(1, 5)	A(1, A(2, 2)) = A(1, 7)	A(1, A(2, 3)) = A(1, 9)	A(1, A(2, n−1))
3	A(2, 1)	A(2, A(3, 0)) = A(2, 5)	A(2, A(3, 1)) = A(2, 13)	A(2, A(3, 2)) = A(2, 29)	A(2, A(3, 3)) = A(2, 61)	A(2, A(3, n−1))
4	A(3, 1)	A(3, A(4, 0)) = A(3, 13)	A(3, A(4, 1)) = A(3, 65533)	A(3, A(4, 2))	A(3, A(4, 3))	A(3, A(4, n−1))
5	A(4, 1)	A(4, A(5, 0))	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	A(4, A(5, n−1))
6	A(5, 1)	A(5, A(6, 0))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))	A(5, A(6, n−1))

Explicación intuitiva

É fácil de ver que a primeira fila da función contén todos os enteiros positivos xa que A(0,n) consiste en facer $n+1$ . O resto das filas pódense ver como indireccións cara á primeira. No caso de m = 1, rediríxese cara a A(0, n + 1); con todo, a simplificación é algo 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.$

E agora un valor extremadamente grande:

{\begin{aligned}A(4,3)&\rightarrow A(3,A(4,2))\\&\rightarrow A(3,A(3,A(4,1)))\\&\rightarrow A(3,A(3,A(3,A(4,0))))\\&\rightarrow A(3,A(3,A(3,A(3,1))))\\&\rightarrow A(3,A(3,A(3,A(2,A(3,0)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,4)))))\\&\rightarrow A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}

Descrición explícita

Intuitivamente, a función de Ackermann define a xeneralización de $x\times 2$ , como sumas iteradas da forma $x+1\cdots +1$ ( con x iteracións), o mesmo coas potencias de forma $2^{x}$ con produtos iterados da forma $2\times \ldots \times 2$ (con x iteracións). Así se pode facer a exponenciación iterada (con iteracións das potencias) e así consecutivamente coas seguintes operacións. Pode expresarse de forma concisa e non recursiva mediante a notación de frecha de Conway:

A(m,n)=2\rightarrow (n+3)\rightarrow (m-2)-3

ou os hiper operadores:

A(m,n)={\text{hyper}}(2,n+3,m-2)+3

Historia

A primeira función dobremente recursiva que non é recursiva primitiva foi descuberta por Gabriel Sudan en 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$

Tanto Sudan como Ackermann eran alumnos de David Hilbert nese momento.

En 1928, Wilhelm Ackermann considerou unha función dobremente recursiva A(m, n, p) de tres variables: m → n → p na notación de Conway. Ackermann demostrou que se trata dunha función recursiva que non é primitiva recursiva. Esa definición foi simplificada por Rózsa Péter e Raphael Robinson á versión de dúas variables. Rozsa Peter tamén demostrou que a dobre recursión non se pode reducir a recursión primitiva (e que de igual forma a tripla recursión non se pode reducir a recursión primitiva e dobre recursión, etc).

Análise de algoritmos

Xa vimos antes que a función f(n)= A(n,n) crece moi rápidamente, pola contra a súa inversa crece moi lentamente e utilízase frecuentemente en análise de algoritmos. Nese contexto, non se emprega a función de Ackermann, senón que se substitúe por outra de comportamento asintótico similar. Aínda que o resultado destas variantes non é idéntico ao da función orixinal, pódense ver como similares ao poder limitar a diferenza. No caso da inversa da función diagonal, o seu resultado é inferior a 4 para entradas de practicamente calquera tamaño, de maneira que se asemella a unha función constante.

Medida de comparación

Dado que é unha función profundamente recursiva, a función de Ackermann utilízase con frecuencia para comparar compiladores en canto á súa habilidade para optimizar a recursión. Por exemplo, un compilador que sexa capaz de notar que A(3, 30) pódese calcular baseándose en potencias de 2, ou que vai gardando certos resultados intermedios tales como A(3, n) e A(2, n) para non ter que recalcularlos cada vez, aforrando así moito tempo de execución por un factor de 100 ou 1000.Tamén, ao calcular directamente A(1, n) , A(2,n) ou A(3,n) en lugar de facer unha chamada recursiva realízanse aforros significativos.

Pódese calcular o termo A(4, 2), non recursivamente, senón por outros medios.

Véxase tamén

Outros artigos

Número de Graham

Bibliografía

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. Dispoñible en liña.
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.