Usuario:PSPX10/Función de Ackermann

Wilhelm Ackermann, matemático alemán, creador da 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 computabilidad. 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 é 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 \mathrm {ACK} (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

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, $2^{65536}-3$)	A(3, A(4,3)	$2^{2^{\ldots ^{2}}}-3(n+3{\text{ términos}})$
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))

A magnitude destes valores e tal, que por exemplo A(4,2) é maior que o número de partículas que forman o universo elevado a 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.

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 indirecciones 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\,$

Un exemplo máis complicado sería A(4, 3), o primeiro valor que non cabe no universo físico.$F_{0}(x,y)=x+y,\,$

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

Sabemos que A(2,5) vale 13, entón avería que facer A(3,13), dando 65533. E teríamos que facer A(3, 65533) = x, x é comparable ao número de átomos no Universo elevado a unha potencia de máis de 12. E por último faríamos A(3,x), pero xa non podríamos escribir os díxitos no universo físico.

Este resultado alcánzase, simplemente facendo composicións da única operación que se utiliza, é dicir, o incremento en un dun valor (no cálculo de A(0,n))

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$

Tanto Sudan como Ackermann eran alumnos de David Hilbert nese entón.

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

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

Enlaces externos

• Some values of the Ackermann function.
• Example use of the Ackermann function as a benchmark.

[[Categoría:1926]]