Ackermannin funktio

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

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

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

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

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

${\displaystyle \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:^[2]

${\displaystyle 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^[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	${\displaystyle n+1}$
1	2	3	4	5	6	${\displaystyle n+2=2+(n+3)-3}$
2	3	5	7	9	11	${\displaystyle 2n+3=2\cdot (n+3)-3}$
3	5	13	29	61	125	${\displaystyle 2^{(n+3)}-3}$
4	13 =${\displaystyle {2^{2^{2}}}-3}$	65533 =${\displaystyle {2^{2^{2^{2}}}}-3}$	265536 − 3 =${\displaystyle {2^{2^{2^{2^{2}}}}}-3}$ =A(4,2)	${\displaystyle {2^{2^{65536}}}-3}$ =${\displaystyle {2^{2^{2^{2^{2^{2}}}}}}-3}$	${\displaystyle {2^{2^{2^{65536}}}}-3}$ =${\displaystyle {2^{2^{2^{2^{2^{2^{2}}}}}}}-3}$	${\displaystyle {\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.;^[4] 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) = ${\displaystyle 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)

${\displaystyle =\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${\displaystyle ^{^{^{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.

Lähteet

Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista.