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

м
→‎Дефиниција и својства: форматирање итд.
м (Бот Мења: ja:アッカーマン関数)
м (→‎Дефиниција и својства: форматирање итд.)
Можда није одмах очигледно да се израчунавање ових функција увек завршава. Рекурзија је ограничена јер се у сваком нивоу рекурзије или ''m'' смањује, или ''m'' остаје исто, а ''n'' се смањује. Сваки пут кад ''n'' дође до нуле, ''m'' се умањује, тако да ће и ''m'' у једном тренутку доћи до нуле. (Технички речено, у сваком случају, пар (''m'', ''n'') опада у лексикографском поретку, што очувава добру уређеност ненегативних целих бројева.) Међутим, кад се ''m'' смањује, не постоји горња граница колико ''n'' може да се повећа - и често оно расте јако пуно.
 
АкерманофаАкерманова функција може да се изрази нерекурзивно употребом Конвејеве нотације са ланчаним стрелицама:
 
:-{''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,&nbsp;2) је око 2&times;10<sup>19728</sup>, а децимални развој ''A''(4,&nbsp;3) не може бити записан у познатом свемиру. Ако дефинишемо функцију -{''f''&nbsp;(''n'')&nbsp;=&nbsp;''A''(''n'',&nbsp;''n'')}-, која повећава и ''m'' и ''n'' у исто време, добијамо функцију са једном променљивом, у односу на коју све примитивно рекурзивне функције једва да расту, укључујући врло брзо растуће функције као што су [[експоненцијална функција]], [[факторијел]], мулти- и суперфакторијел, па чак и функције дефинисане помоћу Кнутове нотације (осим кад се користи индексирана стрелица на горе).
 
Овај екстремни раст се може искористити да се покаже да -{''f''}-, која је очигледно израчунљива на машини са неограниченом меморијом, као што је [[Тјурингова машина]], и да је стогатиме [[израчунљива функција]], расте брже од било које примитивно рекурзивне функције, што значи да није примитивно рекурзивна. Заједно са применама Акерманове функције у анализи алгоритама (даље у тексту), ово оповргава теорију да су све употребљиве или једноставне функције примитивно рекурзивне. (Али, ту није крај: Функцијефункције [[Вредни даброви|Вредних даброва]] расту брже од било које рекурзивне функције, и може се показати да ако би могле да се реше у општем случају, могли бисмо да решимо [[халтинг проблем]] па је израчунавање коришћењем алгоритма немогуће.)
 
Један изненађујући аспект Акерманове функције је да су једине аритметичке операције које користи сабирање и одузимање јединице. Њена својства долазеследе искључиво из неограничене рекурзије. Ово такође значи да је време извршавања најмање пропорционално аутпутурезултату, који је екстремно велик. Реално, за већину случајева, време извршавања је много веће од аутпутарезултата; види испод.
 
== Таблица вредности ==
217

измена