Ackermannin funktio

Wikipedia
Loikkaa: valikkoon, hakuun

Ackermannin funktio on ei-primitiivirekursiivinen funktio, joka on nimetty saksalaisen matemaatikon Wilhelm Ackermannin mukaan. Ackermann julkaisi funktion vuonna 1928.

Funktio[muokkaa | muokkaa wikitekstiä]

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:[1]

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

Lausekkeen arvo nousee nopeasti, jopa pienten numeroiden käytöllä. Esimerkiksi A(4,2) on kokonaisluku, jossa on 19 729 numeroa.[2]

A(mn)
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[muokkaa | muokkaa wikitekstiä]

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.;[3] 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) = 3\uparrow\uparrow3^{3^3} = 3\uparrow\uparrow7625597484987 = \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 yksinkertainen kaava 44 yksin on suurempi kuin googolplex, joten jo neljäs Ackermannin luku on sangen iso.

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. The Ackermann Function Archive.org
  2. Decimal expansion of A(4,2) Archive.org
  3. John Horton Conway and Richard K. Guy. The Book of Numbers. New York: Springer-Verlag, pp. 60-61, 1996. ISBN 978-0-387-97993-9
Käännös suomeksi
Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja vieraskielisen Wikipedian artikkelista.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.