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:

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.

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.; 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 

Erikoisfunktiot
Aritmetiikka