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, $\varphi (m,n,p)\,\!$, on määritelty siten, että arvoilla p = 0, 1, 2, se tuottaa peruslaskutoimitukset yhteenlasku, kertolasku ja potenssiinkorotus seuraavasti:

$\varphi (m,n,0)=m+n,\,\!$

$\varphi (m,n,1)=m\cdot n,\,\!$

$\varphi (m,n,2)=m^{n},\,\!$

Ja arvoilla p > 2 se laajenee peruslaskutoimituksia edemmäksi, jota voi kuvata Knuthin nuolinotaatiolla:

$\varphi (m,n,p)=m\uparrow ^{p-1}n.\,\!$

Eräs yleisimmin käytetyistä versioista on kahden argumentin Ackermann–Péter funktio, joka määritellään positiivisilla muuttujilla m ja n:

$A(m,n)={\begin{cases}n+1&{\mbox{jos }}m=0\\A(m-1,1)&{\mbox{jos }}m>0{\mbox{ ja }}n=0\\A(m-1,A(m,n-1))&{\mbox{jos }}m>0{\mbox{ ja }}n>0.\end{cases}}$

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.

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+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13 =${2^{2^{2}}}-3$	65533 =${2^{2^{2^{2}}}}-3$	265536 − 3 =${2^{2^{2^{2^{2}}}}}-3$ =A(4,2)	${2^{2^{65536}}}-3$ =${2^{2^{2^{2^{2^{2}}}}}}-3$	${2^{2^{2^{65536}}}}-3$ =${2^{2^{2^{2^{2^{2^{2}}}}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\mbox{ + 3}}\end{matrix}}$

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↑ⁿn (n = 1, 2, 3, ...), missä m↑^kn on Knuthin nuolinotaatio-versio Ackermannin funktiosta.

Ensimmäiset Ackermannin numerot ovat:

• 1↑1 = 1¹ = 1,
• 2↑↑2 = 2↑2 = 2² = 4,
• 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = $3\uparrow \uparrow 3^{3^{3}}=3\uparrow \uparrow 7625597484987=\underbrace {3^{3^{3^{3^{.^{.^{.^{3}}}}}}}} _{7625597484987{\rm {\ kolmosta}}}$

Neljäs numero, 4↑↑↑↑4, voidaan muodostaa tetraatiotorneilla seuraavasti:

• 4↑↑↑↑4 = 4↑↑↑4↑↑↑4↑↑↑4 = 4↑↑↑4↑↑↑(4↑↑4↑↑4↑↑4)

$=\underbrace {~~^{^{^{^{^{^{^{^{4}.}.}.}4}4}4}4}4~~} _{\underbrace {~^{^{^{^{^{4}.}.}.}4}4~} _{^{^{^{4}4}4}4{\rm {\ nelosta}}}{\rm {nelosta}}}$

Selitys: keskimmäisessä kerroksessa on tetraatiotorni, jonka korkeus on$^{^{^{4}4}4}4$ ja lopputulos on ylin kerros tetraatio-nelosia, joiden lukumäärä vastaa keskimmäisen kerroksen tulosta. Vertailun vuoksi on yksinkertainen lauseke ⁴4 yksin suurempi kuin googolplex, joten jo neljäs Ackermannin luku on sangen iso.