Ackermannin funktio

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