Akermanova funkcija

U teoriji izračunljivosti, Akermanova funkcija ili Akerman-Peterova funkcija je jednostavan primer izračunljive funkcije koja nije primitivno rekurzivna. Kao argumente ima dva prirodna broja, a vraća takođe prirodan broj. Njene vrednosti rastu ekstremno brzo; čak i za male ulazne vrednosti, na primer (4,3), vrednosti Akermanove funkcije su toliko velike da u praksi ne mogu da se izračunaju. Decimalni zapis ovih vrednosti ima više cifara nego što postoji čestica u poznatom svemiru.

Istorija[uredi | uredi izvor]

Krajem 1920-ih, matematičari Gabrijel Sudan i Vilhelm Akerman, učenici Davida Hilberta, su proučavali osnove izračunljivosti. Sudanu se pripisuje definisanje manje poznate Sudanove funkcije, prve objavljene funkcije koja je rekurzivna, ali nije primitivno rekurzivna. Ubrzo potom, i nezavisno, 1928, Akerman je objavio svoju rekurzivnu ali ne primitivno rekurzivnu funkciju.^[1]

Akerman je prvobino razmatrao funkciju A(m, n, p) sa tri promenljive, p-tostruko ponavljani eksponent n nad m. Kada je p = 1, onda je mⁿ, što znači m pomnoženo samim sobom n puta. Kada je p = 2, dobijamo niz eksponenata ${{m^{m}}^{{\cdot }^{{\cdot }^{{\cdot }^{m}}}}}$ sa n nivoa, ili m podignuto n puta na stepen m, što se takođe može zapisati kao ⁿm. Sa ovakvim generalizacijama se može nastaviti u beskonačno kako p raste.

Akerman je dokazao da je A rekurzivna funkcija, funkcija koju računar sa neograničenom memorijom može da izračuna, ali da nije primitivno rekurzivna funkcija, što predstavlja klasu funkcija u koju spadaju skoro sve poznate funkcije kao što su sabiranje ili faktorijel.

U delu On the Infinite, David Hilbert je izneo hipotezu da Akermanova funkcija nije primitivno rekurzivna, ali je Akerman, Hilbertov lični sekretar i nekadašnji student, u stvari dokazao ovu hipotezu u svom radu On Hilbert’s Construction of the Real Numbers. On the Infinite je bio Hilbertov najznačajniji rad o osnovama matematike, i bio je srce Hilbertovog programa koji obezbeđuje osnove transfinitnih brojeva tako što ih bazira na finitnim metodama. Ovaj rad takođe skicira dokaz hipoteze kontinuuma i predstavljao je važan uticaj na Kurta Gedela u studiji kompletnosti i konzistentnosti matematike, što je dovelo do Gedelove teoreme nepotpunosti.

Sličnu funkciju sa dve promenljive su kasnije definisali Roza Peter i Rafael Robinson; njena definicija je data niže.

Definicija i svojstva[uredi | uredi izvor]

Akermanova funkcija je definisana rekurzivno za nenegativne cele brojeve m i n na sledeći način (ovo je predstavljanje Roze Petera):

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}}

Možda nije odmah očigledno da se izračunavanje ovih funkcija uvek završava. Rekurzija je ograničena jer se u svakom nivou rekurzije ili m smanjuje, ili m ostaje isto, a n se smanjuje. Svaki put kad n dođe do nule, m se umanjuje, tako da će i m u jednom trenutku doći do nule. (Tehnički rečeno, u svakom slučaju, par (m, n) opada u leksikografskom poretku, što očuvava dobru uređenost nenegativnih celih brojeva.) Međutim, kad se m smanjuje, ne postoji gornja granica koliko n može da se poveća - i često ono raste jako puno.

Akermanova funkcija može da se izrazi nerekurzivno upotrebom Konvejeve notacije sa lančanim strelicama:

A(m, n) = (2 → (n+3) → (m − 2)) − 3 za m > 2

stoga

2 → n → m = A(m+2,n-3) + 3 za n > 2

(n=1 i n=2 bi odgovaralo A(m,−2) = −1 i A(m,−1) = 1, što bi logički bilo dodato).

ili sa hiper operatorima:

A(m, n) = hyper(2, m, n + 3) − 3.

Za male vrednosti m kao što su 1, 2, ili 3, Akermanova funkcija raste relativno sporo u odnosu na n (u najboljem slučaju eksponencijalno). Za m ≥ 4, međutim, ona raste mnogo brže; već A(4, 2) je oko 2×10¹⁹⁷²⁸, a decimalni razvoj A(4, 3) ne može biti zapisan u poznatom svemiru. Ako definišemo funkciju f (n) = A(n, n), koja povećava i m i n u isto vreme, dobijamo funkciju sa jednom promenljivom, u odnosu na koju sve primitivno rekurzivne funkcije jedva da rastu, uključujući vrlo brzo rastuće funkcije kao što su eksponencijalna funkcija, faktorijel, multi- i superfaktorijel, pa čak i funkcije definisane pomoću Knutove notacije (osim kad se koristi indeksirana strelica nagore).

Ovaj ekstremni rast se može iskoristiti da se pokaže da f, koja je očigledno izračunljiva na mašini sa neograničenom memorijom kao što je Tjuringova mašina, i time izračunljiva funkcija, raste brže od bilo koje primitivno rekurzivne funkcije, što znači da nije primitivno rekurzivna. Zajedno sa primenama Akermanove funkcije u analizi algoritama (dalje u tekstu), ovo opovrgava teoriju da su sve upotrebljive ili jednostavne funkcije primitivno rekurzivne. (Ali, tu nije kraj: funkcije Vrednih dabrova rastu brže od bilo koje rekurzivne funkcije, i može se pokazati da ako bi mogle da se reše u opštem slučaju, mogli bismo da rešimo halting problem pa je izračunavanje korišćenjem algoritma nemoguće.)

Jedan iznenađujući aspekt Akermanove funkcije je da su jedine aritmetičke operacije koje koristi sabiranje i oduzimanje jedinice. Njena svojstva slede isključivo iz neograničene rekurzije. Ovo takođe znači da je vreme izvršavanja najmanje proporcionalno rezultatu, koji je ekstremno velik. Realno, za većinu slučajeva, vreme izvršavanja je mnogo veće od rezultata; vidi ispod.

Tablica vrednosti[uredi | uredi izvor]

Izračunavanje Akermanove funkcije se može izraziti i u terminima beskonačne tablice. Poređamo prirodne brojeve u prvu vrstu. Kako bismo odredili broj na određenom mestu u tabeli, uzmemo broj koji se nalazi odmah sleva, a zatim potražimo broj u prethodnoj vrsti, u koloni koju određuje broj koji smo videli. Ako sa leve strane nema broja, jednostavno uzmemo broj iz kolone 1 iz prethodne vrste. Sledi mali odlomak ovakve tabele:

Vrednosti za 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) je veće od broja čestica u poznatom svemiru, podignutog na stepen 200. A(5, 2) je broj u koloni A(5, 1) u m = 4 vrsti, i ne može biti zapisan u decimalnom razvoju u poznatom svemiru. Posle vrste 4 i kolone 1, vrednosti funkcije više ne mogu praktično da se zapišu ni u jednoj standardnoj notaciji osim same Akermanove funkcije — zapisivanje ovih brojeva decimalno, ili čak pozivanje na vrste sa manjim m nije moguće.

Uprkos nezamislivo velikim vrednostima koje se pojavljuju već na početku tabele, neki čak veći brojevi su definisani, kao što je Grejemov broj, koji se ne može zapisati pomoću malog (ili čak zapisivog) broja Knutovih strelica. Ovaj broj je konstruisan tehnikom sličnom primenjivanju Akermanove funkcije na samu sebe rekurzivno.

Objašnjenje[uredi | uredi izvor]

Kako bi se videlo na koji način Akermanova funkcija raste tako brzo, od koristi bi bilo izvesti izračunavanje za neke manje vrednosti. Na primer, možemo u potpunosti da izračunamo A(1, 2) na sledeći način:

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

Pokušajmo sada sa komplikovanijim A(4, 3), prvom vrednosti sa relativno malim n, koja se ne može decimalno zapisati u poznatom svemiru:

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))
 = ...

Ovde stajemo, jer A(3, 65533) vraća 2⁶⁵⁵³⁶ − 3, broj mnogo veći od broja atoma u vidljivom svemiru. Nakon ovoga, broj 2 se podiže na ovaj stepen da bi se dobio konačan rezultat.

Inverz[uredi | uredi izvor]

Kako funkcija f (n) = A(n, n), razmatrana gore raste vrlo brzo, njena inverzna funkcija, f⁻¹, raste vrlo sporo. Ova inverzna Akermanova funkcija f⁻¹ se obično označava sa α. U stvari, α(n) je manje od 5 za svaku zamislivu vrednost ulaznog argumenta n. Za sve praktične primene, f⁻¹(n) se može smatrati konstantnom.

Ova inverzna funkcija se pojavljuje u vremenskoj kompleksnosti nekih algoritama, kao što su strukture podataka disjunktnih skupova, i Šazelov algoritam za minimalna razapinjuća stabla. Ponekad se originalna Akermanova funkcija ili neke varijacije koriste u ovim okvirima, ali one sve rastu sličnim tempom. Na primer, neke modifikovane funkcije pojednostavljuju izraz eliminacijom −3 i slično.

Dvoparametarska varijacija inverzne Akermanove funkcije se može definisati na sledeći način:

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

Ova funkcija se pojavljuje u preciznijim analizama algoritama, pomenutim gore. U skrukturi podataka disjunktnih skupova, m predstavlja broj operacija, a n predstavlja broj elemenata; u algoritmu za minimalno razapinjuće stablo, m predstavlja broj ivica, dok n predstavlja broj vrhova grafa. Postoji nekoliko definicija α(m, n), koje se blago razlikuju; na primer, log₂ n se ponekad zamenjuje sa n, a donje ograničenje se ponekad zamenjuje gornjim.

Korišćenje za upoređivanje[uredi | uredi izvor]

Akermanova funkcija, usled svoje definicije preko ekstremno duboke rekurzije, može da se koristi za upoređivanje sposobnosti različitih programskih prevodilaca da optimizuju rekurziju. U Obračunu računarskih jezika, na primer, se koristi potrebno vreme da se izračuna ova funkcija za fiksne argumente u različitim implementacijama programskih jezika.^[2]

Na primer, prevodilac koji je pri analiziranju izračunavanja A(3, 30), u stanju da sačuva međuvrednosti kao što su A(3, n) iA(2, n) u izračunavanju, umesto da ih ponovo računa, može da ubrza vreme izračunavanja A(3, 30) za faktor stotina hiljada. Takođe, ako se A(2, n) računa direktno umesto pomoću rekurzivne ekspanzije u formi A(1, A(1, A(1,...A(1, 0)...))), uštedeće se značajna količina vremena. Za izračunavanje A(1, n) je potrebno linearno vreme. Izračunavanje A(2, n) zahteva kvadratno vreme, jer je potrebno O(n) ugnježdenih poziva A(1, i) za različite i. Za izračunavanje A(3, n) je potrebno vreme proporcionalno 4ⁿ⁺¹. Izračunavanje A(3, 1), na primer zahteva 16 (4²) koraka.

Vrednost A(4, 2), koja se može naći u decimalnom zapisu na raznim veb-sajtovima, ne može da se izračuna rekurzivnom primenom Akermanove funkcije za približno prihvatljivo vreme. Umesto toga se koriste formule kao što je A(3, n) = 8×2ⁿ−3 da bi se brzo završili neki rekurzivni pozivi.

Akermanovi brojevi[uredi | uredi izvor]

Povezani sa Akermanovom funkcijom, ali u stvari različiti su Akermanovi brojevi, niz, čiji n-ti član glasi:

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

Gde $\uparrow$ označava Knutovu strelicu nagore.

Na primer, prva tri Akermanova broja su

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

što je jednako:

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

Pokušaj da se izrazi četvrti Akermanov broj, 4 $\uparrow \uparrow \uparrow \uparrow$ 4, korišćenjem iterativne eksponencijacije kao što je prikazano gore, bi bio izrazito komplikovan. Međutim, moguće ga je zapisati korišćenjem tetracije u tri sloja:

${\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}}$

Vidi još[uredi | uredi izvor]

Literatura[uredi | uredi izvor]

Wilhelm Ackermann (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Math. Annalen 99: 118–133.
van Hejenort. Od Fregea do Gedela, 1967. Nezamenjiva referenca za razumevanje konteksta Akermanovog rada O Hilbertovoj konstrukciji realnih brojeva, koja sadrži i njegov rad, kao i Hilbertov O beskonačnom i Gedelova dva rada o kompletnosti i konzistentnosti matematike.
Raphael M. Robinson (1948). "Recursion and Double Recursion". Bull. Amer. Math. Soc. 54: 987–93.

Reference[uredi | uredi izvor]

^ 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. . Sumirao Bil Dubuku (1997.). "Ackermann vs. Sudan". sci.logic. (Google Groups). Pristupljeno 13. juna 2006.
^ Intel Pentium 4 Computer Language Shootout Arhivirano na sajtu Wayback Machine (24. septembar 2006), Pristupljeno 4. 5. 2013.

Spoljašnje veze[uredi | uredi izvor]

Stranica Eriha Fricmana o Akermanu Arhivirano na sajtu Wayback Machine (10. septembar 2006) na Stetson univerzitetu
Skot Aronson, Ko može da imenuje najveći broj? (1999.)
Neke vrednosti Akermanove funkcije.
Decimalni razvoj A(4,2)
Hiper-operatori - Post na naučnom forumu koji raspravlja o aritmetičkim operatorima Akermanove funkcije i njihovim inverznim operatorima, sa linkom na širi članak o toj temi.
Robert Munafove verzije Akermanove funkcije - opis nekoliko varijacija u definisanju A.
Zah, Ričard,
„Hilbertov program", Stanfordova enciklopedija filozofije (Fall 2003 Edition), Edward N. Zalta (ed.)
Pol E. Blek, Akermanova funkcija na NIST rečniku algoritama i struktura podataka

[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. . Sumirao Bil Dubuku (1997.). "Ackermann vs. Sudan". sci.logic. (Google Groups). Pristupljeno 13. juna 2006.

[2] Intel Pentium 4 Computer Language Shootout Arhivirano na sajtu Wayback Machine (24. septembar 2006), Pristupljeno 4. 5. 2013.

[1]

[2]