Ackermannova funkce

Z Wikipedie, otevřené encyklopedie

Ackermannova funkce je příkladem funkce, která je rekurzivní a přitom není primitivně rekurzivní. Hodnota Ackermannovy funkce roste velmi rychle a už pro velmi malá čísla (4, 5, …) je nemyslitelné tuto hodnotu spočítat. Např. A(4) je tak obrovské číslo, že už počet jeho číslic je vyšší než počet všech atomů ve vesmíru. Jinak řečeno, Ackermannova funkce roste nade všechny rozumně představitelné meze a není omezitelná žádnou běžně používanou funkcí.

[editovat] Definice

Ackermannova funkce $A: \mathbb{N}^2 \rarr \mathbb{N}$ je definovaná následujícími rekurentními vzorci:

$A(m,n)= \left\{ \begin{matrix} n+1,\qquad\qquad\qquad\quad\,&&\mbox{pro }m=0;\qquad\qquad \\ A(m-1, 1),\qquad\qquad\ \,&&\mbox{pro }m>0\mbox{ a }n=0; \\ A(m-1, A(m, n-1))\,&&\mbox{jinak.}\,\qquad\qquad \end{matrix} \right.$

Ackermannovu funkci jedné proměnné pak můžeme definovat jako $A (n) = A (n, n)$ . Zde uvedená Ackermannova funkce je tvar, na který funkci upravili Rosza Peter a Raphael Robinson. Původní funkce definovaná v roce 1928 Wilhelmem Ackermannem měla argumenty tři:

$A(0,y,z)\qquad\qquad = y+z$

$A(x+1,0,z)\qquad = \left\{ \begin{matrix} 0,\quad\,&&\mbox{pro }x=0; \\ 1,\quad\,&&\mbox{pro }x=1; \\ z,\quad\,&&\mbox{pro }x>1; \end{matrix} \right.$

$A(x+1,y+1,z)\quad = A(x, A(x+1,y,z), z)$

Myšlenka Ackermannovy funkce spočívá v tom, že pro x = 0 jde o sčítání dvou zbylých paramterů, pro x = 1 o násobení, pro x = 2 o mocnění atd. Vždy se iteruje předchozí operace.

[editovat] Tabulka hodnot

Hodnoty 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	$2 n + 3$
3	5	13	29	61	125	$2 n + 3 - 3$
4	13	65533	2⁶⁵⁵³⁶ − 3	A(3, 2⁶⁵⁵³⁶ − 3)	A(3, A(4, 3))	$\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3 dvojek}\end{matrix}$
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))

[editovat] Algoritmus

Lze dokázat, že nejen hodnotu, ale ani výpočetní složitost této funkce nelze omezit strukturovaným algoritmem, který by obsahoval pouze konečné množství cyklů typu for (a žádné cykly typu repeat nebo until).

 function ack(m, n)
     if m == 0
         return n+1
     else if m > 0 and n == 0
         return ack(m-1, 1)
     else
         return ack(m-1, ack(m, n-1))

[editovat] Inverzní funkce

Jelikož Ackermannova funkce $A (n)$ roste extrémně rychle, její inverze $A - 1$ roste extrémně pomalu. Tato inverzní funkce se někdy označuje jako $α$ . Jelikož $A (n)$ je pro $n > 4$ naprosto nepředstavitelná, je $α(n)$ menší než 5 pro všechny představitelné hodnoty n, pro všechny praktické účely lze tedy funkci $α$ považovat za konstantní. Tato inverzní funkce se objevuje při analýze složitosti některých algoritmů, například u Kruskalova algoritmu.