Акерманова функција — разлика између измена

АкерманофаАкерманова функција може да се изрази нерекурзивно употребом Конвејеве нотације са ланчаним стрелицама:

:-{''A''(''m'', ''n'') = (2 → (''n''+3) → ''(m'' − 2)) − 3}- за -{''m'' > 2}-

:-{2 → ''n'' → ''m'' = ''A''(''m''+2,''n''-3)}- + 3 forза -{''n'' > 2}-

(-{''n''=1}- и -{''n''=2}- би одговарало ''A''(''m'',−2) = −1 и ''A''(''m'',−1) = 1, што би логички било додато).

:-{''A''(''m'', ''n'') = hyper(2, m, n + 3) − 3}-.

За мале вредности ''m'' као што су 1, 2, или 3, Акерманова функција расте релативно споро у односу на ''n'' (у најбољем случају [[експоненцијални раст|експоненцијално]]). За ''m'' ≥ 4, међутим, она расте много брже; чаквећ ''A''(4, 2) је око 2×10¹⁹⁷²⁸, а децимални развој ''A''(4, 3) не може бити записан у познатом свемиру. Ако дефинишемо функцију -{''f'' (''n'') = ''A''(''n'', ''n'')}-, која повећава и ''m'' и ''n'' у исто време, добијамо функцију са једном променљивом, у односу на коју све примитивно рекурзивне функције једва да расту, укључујући врло брзо растуће функције као што су [[експоненцијална функција]], [[факторијел]], мулти- и суперфакторијел, па чак и функције дефинисане помоћу Кнутове нотације (осим кад се користи индексирана стрелица на горе).

Овај екстремни раст се може искористити да се покаже да -{''f''}-, која је очигледно израчунљива на машини са неограниченом меморијом, као што је [[Тјурингова машина]], и да је стогатиме [[израчунљива функција]], расте брже од било које примитивно рекурзивне функције, што значи да није примитивно рекурзивна. Заједно са применама Акерманове функције у анализи алгоритама (даље у тексту), ово оповргава теорију да су све употребљиве или једноставне функције примитивно рекурзивне. (Али, ту није крај: Функцијефункције [[Вредни даброви|Вредних даброва]] расту брже од било које рекурзивне функције, и може се показати да ако би могле да се реше у општем случају, могли бисмо да решимо [[халтинг проблем]] па је израчунавање коришћењем алгоритма немогуће.)

Један изненађујући аспект Акерманове функције је да су једине аритметичке операције које користи сабирање и одузимање јединице. Њена својства долазеследе искључиво из неограничене рекурзије. Ово такође значи да је време извршавања најмање пропорционално аутпутурезултату, који је екстремно велик. Реално, за већину случајева, време извршавања је много веће од аутпутарезултата; види испод.