Ackermannin funktio

Malline:Lähteetön Ackermannin funktio on ei-primitiivirekursiivinen funktio, joka on nimetty saksalaisen matemaatikon Wilhelm Ackermannin mukaan. Ackermann julkaisi funktion vuonna 1928.

Funktio

Ackermannin kolmen argumentin funktio, $\phi (m,n,p)$, on määritelty siten, että arvoilla p = 0, 1, 2, se tuottaa peruslaskutoimitukset yhteenlasku, kertolasku ja potenssiinkorotus seuraavasti:

$\phi (m,n,0)=m+n,$

$\phi (m,n,1)=m\cdot n,$

$\phi (m,n,2)=m^n,$

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

$\phi (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{array}{cc}n+1& \text{jos }m=0\\ A(m-1,1)& \text{jos }m>0\text{ ja }n=0\\ A(m-1,A(m,n-1))& \text{jos }m>0\text{ ja }n>0.\end{array}$

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{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\\ n\text{ + 3}\end{array}$

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=\underset{7625597484987\mathrm{k}\mathrm{o}\mathrm{l}\mathrm{m}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{a}}{\underbrace{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)

$=\underset{\underset{{}^{{}^{{}^{4}4}4}4\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{a}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{a}}{\underbrace{{}^{{}^{{}^{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}4}4}4}}$

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.