Cesko.wiki Ackermannova funkce
Author
Albert FloresAckermannova funkce je příkladem funkce, která je rekurzivní a přitom není primitivně rekurzivní. Hodnota Ackermannovy funkce A(n) 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ů v pozorovaném vesmíru. Jinak řečeno, Ackermannova funkce roste nade všechny rozumně představitelné meze a není omezitelná žádnou běžně používanou funkcí.
Definice
Ackermannova funkce dvou proměnných A: \mathbb{N}^2 \rarr \mathbb{N} je definovaná rekurentním vzorcem : A(m,n)= \begin{cases} n+1, & \mbox{pro }m=0 \\ A(m-1, 1), & \mbox{pro }m>0\,\,\mbox{a }n=0 \\ A(m-1, A(m, n-1)), & \mbox{jinak} \end{cases} .
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 Rózsa Péterová a Raphael Robinson. +more 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 = \begin{cases} 0, & \mbox{pro }x=0 \\ 1, & \mbox{pro }x=1 \\ z, & \mbox{pro }x>1 \end{cases} |
| 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 parametrů, pro x = 1 o násobení, pro x = 2 o mocnění atd. Vždy se iteruje předchozí operace.
Tabulka hodnot
Ackermannovu funkci dvou proměnných lze vyjádřit také ve formě nekonečné dvourozměrné tabulky. Její konstrukce je velice jednoduchá: Do prvního řádku se umístí přirozená čísla. +more Ostatní buňky se pak vyplní tím, že se opíše hodnota z předchozího řádku, ze sloupečku udaného hodnotou buňky, která je nalevo od vyplňované (první sloupeček se vyplní hodnotou sloupečku 1 z předchozího řádku). Levá horní část tabulky vypadá takto:.
| 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 | {2}^{n+3} - 3 |
| 4 | 13 | 65533 | 265536 − 3 | A(3, 265536 − 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)) |
Pro zápis velkých hodnot lze použít Knuthův zápis.
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 while).
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))
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 \alpha. +more Jelikož A(n) je pro n > 4 naprosto nepředstavitelná, je \alpha(n) menší než 5 pro všechny představitelné hodnoty n, pro všechny praktické účely lze tedy funkci \alpha považovat za konstantní. Tato inverzní funkce se objevuje při analýze složitosti některých algoritmů, například u Kruskalova algoritmu.
Externí odkazy
[url=http://mathworld.wolfram.com/AckermannFunction.html]Ackermannova funkce na encyklopedii MathWorld[/url] * [url=http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm]Tabulka hodnot[/url]