Ackermannin funktio on ei-primitiivirekursiivinen funktio[1], 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:[2]
Lausekkeen arvo nousee nopeasti, nopeammin kuin eksponenttifunktio[1]. Näin käy jopa pienten numeroiden käytöllä. Esimerkiksi A(4,2) on kokonaisluku, jossa on 19 729 numeroa.[3]
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.;[4] 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
↑ abAckermann Function from Wolfram MathWorld mathworld.wolfram.com. Viitattu 2.9.2014.