Ackermannin funktio

Wikipedia
Loikkaa: valikkoon, hakuun

Ackermannin funktio on ei-primitiivirekursiivinen funktio[1], 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:[2]

 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, 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(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.;[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) = 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. a b Ackermann Function from Wolfram MathWorld Viitattu 2.9.2014.
  2. The Ackermann Function Archive.org
  3. Decimal expansion of A(4,2) Archive.org
  4. 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.