Ackermannova funkce: Porovnání verzí

'''Ackermannova funkce''' je příkladem [[funkce (matematika)|funkce]], která je [[rekurzivní funkce (matematika)|rekurzivní]] a přitom není [[primitivně rekurzivní funkce|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ů 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í.

Ackermannovu funkci jedné proměnné pak můžeme definovat jako <math>A(n)=A(n,n)</math>. Zde uvedená Ackermannova funkce je tvar, na který funkci upravili [[Rózsa Péterová]] a [[Raphael Robinson]]. Původní funkce definovaná v &nbsp;roce 1928 [[Wilhelm Ackermann|Wilhelmem Ackermannem]] měla argumenty tři:

Myšlenka Ackermannovy funkce spočívá v &nbsp;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.

Ackermannovu funkci dvou proměnných lze vyjádřit také ve formě nekonečné dvourozměrné tabulky,. jejížJejí konstrukce je velice jednoduchá: Do prvního řádku se umístí [[přirozená čísla]]. Ostatní buňky se pak vyplní tím, že se opíše hodnota z &nbsp;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 &nbsp;předchozího řádku). Levá horní část tabulky vypadá takto: