Ackermannin funktio on ei-primitiivirekursiivinen funktio, joka on nimetty saksalaisen matemaatikon Wilhelm Ackermannin mukaan. Ackermann julkaisi funktion vuonna 1928.
Funktio Ackermannin kolmen argumentin funktio, , on määritelty siten, että arvoilla p = 0, 1, 2, se tuottaa peruslaskutoimitukset yhteenlasku, kertolasku ja potenssiinkorotus seuraavasti:
Ja arvoilla p > 2 se laajenee peruslaskutoimituksia edemmäksi, jota voi kuvata Knuthin nuolinotaatiolla:
Eräs yleisimmin käytetyistä versioista on kahden argumentin Ackermann–Péter funktio, joka määritellään positiivisilla muuttujilla m ja n:The Ackermann Function Archive.org
Lausekkeen arvo nousee nopeasti, nopeammin kuin eksponenttifunktio. Näin käy jopa pienten numeroiden käytöllä. Esimerkiksi A(4,2) on kokonaisluku, jossa on 19 729 numeroa.Decimal expansion of A(4,2) Archive.org
+ A(m, n) m\n 0 1 2 3 4 n 0 1 2 3 4 5 1 2 3 4 5 6 2 3 5 7 9 11 3 5 13 29 61 125 4 13 = 65533 = 265536 − 3 ==A(4,2) = =
Ackermannin numerot Kirjassaan The Book of Numbers, John Horton Conway ja Richard K. Guy määrittelevät että Ackermannin numerot ovat muotoa 1↑1, 2↑↑2, 3↑↑↑3, jne.;John Horton Conway and Richard K. Guy. The Book of Numbers. New York: Springer-Verlag, s. 60–61, 1996. eli ”n”:s Ackermannin numero on n↑nn (n = 1, 2, 3, ...), missä m↑kn on Knuthin nuolinotaatio-versio Ackermannin funktiosta.
Ensimmäiset Ackermannin numerot ovat: 1↑1 = 11 = 1, 2↑↑2 = 2↑2 = 22 = 4, 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) =
Neljäs numero, 4↑↑↑↑4, voidaan muodostaa tetraatiotorneilla seuraavasti:
4↑↑↑↑4 = 4↑↑↑4↑↑↑4↑↑↑4 = 4↑↑↑4↑↑↑(4↑↑4↑↑4↑↑4)
Selitys: keskimmäisessä kerroksessa on tetraatiotorni, jonka korkeus on ja lopputulos on ylin kerros tetraatio-nelosia, joiden lukumäärä vastaa keskimmäisen kerroksen tulosta. Vertailun vuoksi on yksinkertainen lauseke 44 yksin suurempi kuin googolplex, joten jo neljäs Ackermannin luku on sangen iso.
Lähteet
Luokka:Erikoisfunktiot Luokka:Aritmetiikka