Акерманова функција

У теорији израчунљивости, Акерманова функција или Акерман-Петерова функција је једноставан пример израчунљиве функције која није примитивно рекурзивна. Као аргументе има два природна броја, а враћа такође природан број. Њене вредности расту екстремно брзо; чак и за мале улазне вредности, на пример (4,3), вредности Акерманове функције су толико велике да у пракси не могу да се израчунају. Децимални запис ових вредности има више цифара него што постоји честица у познатом свемиру.

Историја

Крајем 1920-их, математичари Габријел Судан и Вилхелм Акерман, ученици Давида Хилберта, су проучавали основе израчунљивости. Судану се приписује дефинисање мање познате Суданове функције, прве објављене функције која је рекурзивна, али није примитивно рекурзивна. Убрзо потом, и независно, 1928, Акерман је објавио своју рекурзивну али не примитивно рекурзивну функцију.^[1]

Акерман је првобино разматрао функцију A(m, n, p) са три променљиве, p-тоструко понављани експонент n над m. Када је p = 1, онда је mⁿ, што значи m помножено самим собом n пута. Када је p = 2, добијамо низ експонената ${{m^{m}}^{{\cdot }^{{\cdot }^{{\cdot }^{m}}}}}$ са n нивоа, или m подигнуто n пута на степен m, што се такође може записати као ⁿm. Са оваквим генерализацијама се може наставити у бесконачно како p расте.

Акерман је доказао да је A рекурзивна функција, функција коју рачунар са неограниченом меморијом може да израчуна, али да није примитивно рекурзивна функција, што представља класу функција у коју спадају скоро све познате функције као што су сабирање или факторијел.

У делу On the Infinite, Давид Хилберт је изнео хипотезу да Акерманова функција није примитивно рекурзивна, али је Акерман, Хилбертов лични секретар и некадашњи студент, у ствари доказао ову хипотезу у свом раду On Hilbert’s Construction of the Real Numbers. On the Infinite је био Хилбертов најзначајнији рад о основама математике, и био је срце Хилбертовог програма који обезбеђује основе трансфинитних бројева тако што их базира на финитним методама. Овај рад такође скицира доказ хипотезе континуума и представљао је важан утицај на Курта Гедела у студији комплетности и конзистентности математике, што је довело до Геделове теореме непотпуности.

Сличну функцију са две променљиве су касније дефинисали Роза Петер и Рафаел Робинсон; њена дефиниција је дата ниже.

Дефиниција и својства

Акерманова функција је дефинисана рекурзивно за ненегативне целе бројеве m и n на следећи начин (ово је представљање Розе Петера):

A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}

Можда није одмах очигледно да се израчунавање ових функција увек завршава. Рекурзија је ограничена јер се у сваком нивоу рекурзије или 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 за 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, која је очигледно израчунљива на машини са неограниченом меморијом као што је Тјурингова машина, и тиме израчунљива функција, расте брже од било које примитивно рекурзивне функције, што значи да није примитивно рекурзивна. Заједно са применама Акерманове функције у анализи алгоритама (даље у тексту), ово оповргава теорију да су све употребљиве или једноставне функције примитивно рекурзивне. (Али, ту није крај: функције Вредних даброва расту брже од било које рекурзивне функције, и може се показати да ако би могле да се реше у општем случају, могли бисмо да решимо халтинг проблем па је израчунавање коришћењем алгоритма немогуће.)

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

Таблица вредности

Израчунавање Акерманове функције се може изразити и у терминима бесконачне таблице. Поређамо природне бројеве у прву врсту. Како бисмо одредили број на одређеном месту у табели, узмемо број који се налази одмах слева, а затим потражимо број у претходној врсти, у колони коју одређује број који смо видели. Ако са леве стране нема броја, једноставно узмемо број из колоне 1 из претходне врсте. Следи мали одломак овакве табеле:

Вредности за 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	$2n+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 twos}}\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))

A(4, 2) је веће од броја честица у познатом свемиру, подигнутог на степен 200. A(5, 2) је број у колони A(5, 1) у m = 4 врсти, и не може бити записан у децималном развоју у познатом свемиру. После врсте 4 и колоне 1, вредности функције више не могу практично да се запишу ни у једној стандардној нотацији осим саме Акерманове функције — записивање ових бројева децимално, или чак позивање на врсте са мањим m није могуће.

Упркос незамисливо великим вредностима које се појављују већ на почетку табеле, неки чак већи бројеви су дефинисани, као што је Грејемов број, који се не може записати помоћу малог (или чак записивог) броја Кнутових стрелица. Овај број је конструисан техником сличном примењивању Акерманове функције на саму себе рекурзивно.

Објашњење

Како би се видело на који начин Акерманова функција расте тако брзо, од користи би било извести израчунавање за неке мање вредности. На пример, можемо у потпуности да израчунамо A(1, 2) на следећи начин:

A(1, 2) = A(0, A(1,1))
 = A(0, A(0, A(1,0)))
 = A(0, A(0, A(0,1)))
 = A(0, A(0, 2))
 = A(0, 3)
 = 4

Покушајмо сада са компликованијим A(4, 3), првом вредности са релативно малим n, која се не може децимално записати у познатом свемиру:

A(4, 3) = A(3, A(4, 2))
 = A(3, A(3, A(4, 1)))
 = A(3, A(3, A(3, A(4, 0))))
 = A(3, A(3, A(3, A(3, 1))))
 = A(3, A(3, A(3, A(2, A(3, 0)))))
 = A(3, A(3, A(3, A(2, A(2, 1)))))
 = A(3, A(3, A(3, A(2, A(1, A(2, 0))))))
 = A(3, A(3, A(3, A(2, A(1, A(1, 1))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, 2))))))
 = A(3, A(3, A(3, A(2, A(1, 3)))))
 = A(3, A(3, A(3, A(2, A(0, A(1, 2))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, 3)))))
 = A(3, A(3, A(3, A(2, A(0, 4)))))
 = A(3, A(3, A(3, A(2, 5))))
 = ...
 = A(3, A(3, A(3, 13)))
 = ...
 = A(3, A(3, 65533))
 = ...

Овде стајемо, јер A(3, 65533) враћа 2⁶⁵⁵³⁶ − 3, број много већи од броја атома у видљивом свемиру. Након овога, број 2 се подиже на овај степен да би се добио коначан резултат.

Инверз

Како функција f (n) = A(n, n), разматрана горе расте врло брзо, њена инверзна функција, f⁻¹, расте врло споро. Ова инверзна Акерманова функција f⁻¹ се обично означава са α. У ствари, α(n) је мање од 5 за сваку замисливу вредност улазног аргумента n. За све практичне примене, f⁻¹(n) се може сматрати константном.

Ова инверзна функција се појављује у временској комплексности неких алгоритама, као што су структуре података дисјунктних скупова, и Шазелов алгоритам за минимална разапињућа стабла. Понекад се оригинална Акерманова функција или неке варијације користе у овим оквирима, али оне све расту сличним темпом. На пример, неке модификоване функције поједностављују израз елиминацијом −3 и слично.

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

\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.

Ова функција се појављује у прецизнијим анализама алгоритама, поменутим горе. У скруктури података дисјунктних скупова, m представља број операција, а n представља број елемената; у алгоритму за минимално разапињуће стабло, m представља број ивица, док n представља број врхова графа. Постоји неколико дефиниција α(m, n), које се благо разликују; на пример, log₂ n се понекад замењује са n, а доње ограничење се понекад замењује горњим.

Коришћење за упоређивање

Акерманова функција, услед своје дефиниције преко екстремно дубоке рекурзије, може да се користи за упоређивање способности различитих програмских преводилаца да оптимизују рекурзију. У Обрачуну рачунарских језика, на пример, се користи потребно време да се израчуна ова функција за фиксне аргументе у различитим имплементацијама програмских језика.^[2]

На пример, преводилац који је при анализирању израчунавања A(3, 30), у стању да сачува међувредности као што су A(3, n) иA(2, n) у израчунавању, уместо да их поново рачуна, може да убрза време израчунавања A(3, 30) за фактор стотина хиљада. Такође, ако се A(2, n) рачуна директно уместо помоћу рекурзивне експанзије у форми A(1, A(1, A(1,...A(1, 0)...))), уштедеће се значајна количина времена. За израчунавање A(1, n) је потребно линеарно време. Израчунавање A(2, n) захтева квадратно време, јер је потребно O(n) угњеждених позива A(1, i) за различите i. За израчунавање A(3, n) је потребно време пропорционално 4ⁿ⁺¹. Израчунавање A(3, 1), на пример захтева 16 (4²) корака.

Вредност A(4, 2), која се може наћи у децималном запису на разним веб-сајтовима, не може да се израчуна рекурзивном применом Акерманове функције за приближно прихватљиво време. Уместо тога се користе формуле као што је A(3, n) = 8×2ⁿ−3 да би се брзо завршили неки рекурзивни позиви.

Акерманови бројеви

Повезани са Акермановом функцијом, али у ствари различити су Акерманови бројеви, низ, чији n-ти члан гласи:

{\begin{matrix}n\ \underbrace {\uparrow \dots \uparrow } \ n\\n\end{matrix}}

Где $\uparrow$ означава Кнутову стрелицу нагоре.

На пример, прва три Акерманова броја су

1 $\uparrow$ 1,
2 $\uparrow \uparrow$ 2
3 $\uparrow \uparrow \uparrow$ 3

што је једнако:

1
4
${\begin{matrix}\underbrace {\qquad \quad 3^{3^{3^{3^{3^{3^{.^{.^{.^{3}}}}}}}}}\qquad \quad } \\7625597484987{\rm {\ trojki}}\end{matrix}}$

Покушај да се изрази четврти Акерманов број, 4 $\uparrow \uparrow \uparrow \uparrow$ 4, коришћењем итеративне експоненцијације као што је приказано горе, би био изразито компликован. Међутим, могуће га је записати коришћењем тетрације у три слоја:

${\begin{matrix}\underbrace {\begin{matrix}\underbrace {4^{4^{4^{4^{4^{.^{.^{.^{4}}}}}}}}} \\4^{4^{4^{4^{4^{.^{.^{.^{4}}}}}}}}\end{matrix}} \\4^{4^{4^{4}}}\end{matrix}}$

Види још

Литература

Wilhelm Ackermann (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Math. Annalen 99: 118–133.
ван Хејенорт. Од Фрегеа до Гедела, 1967. Незамењива референца за разумевање контекста Акермановог рада О Хилбертовој конструкцији реалних бројева, која садржи и његов рад, као и Хилбертов О бесконачном и Геделова два рада о комплетности и конзистентности математике.
Raphael M. Robinson (1948). "Recursion and Double Recursion". Bull. Amer. Math. Soc. 54: 987–93.

Референце

^ Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). „The first example of a recursive function which is not primitive recursive”. Historia Math. 6 (4): 380—84. doi:10.1016/0315-0860(79)90024-7. . Сумирао Бил Дубуку (1997.). "Ackermann vs. Sudan". sci.logic. (Google Groups). Приступљено 13. јуна 2006.
^ Intel Pentium 4 Computer Language Shootout Архивирано на сајту Wayback Machine (24. септембар 2006), Приступљено 4. 5. 2013.

Спољашње везе

Страница Ериха Фрицмана о Акерману Архивирано на сајту Wayback Machine (10. септембар 2006) на Стетсон универзитету
Скот Аронсон, Ко може да именује највећи број? (1999.)
Неке вредности Акерманове функције.
Децимални развој A(4,2)
Хипер-оператори - Пост на научном форуму који расправља о аритметичким операторима Акерманове функције и њиховим инверзним операторима, са линком на шири чланак о тој теми.
Роберт Мунафове верзије Акерманове функције - опис неколико варијација у дефинисању A.
Зах, Ричард,
„Хилбертов програм", Станфордова енциклопедија филозофије (Fall 2003 Edition), Edward N. Zalta (ed.)
Пол Е. Блек, Акерманова функција на НИСТ речнику алгоритама и структура података

[1] Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). „The first example of a recursive function which is not primitive recursive”. Historia Math. 6 (4): 380—84. doi:10.1016/0315-0860(79)90024-7. . Сумирао Бил Дубуку (1997.). "Ackermann vs. Sudan". sci.logic. (Google Groups). Приступљено 13. јуна 2006.

[2] Intel Pentium 4 Computer Language Shootout Архивирано на сајту Wayback Machine (24. септембар 2006), Приступљено 4. 5. 2013.

[1]

[2]