Ackermannin funktio

Wikipediasta
Siirry navigaatioon Siirry hakuun

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

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

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

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

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
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
4 13

=
65533

=
265536 − 3

=

=A(4,2)


=


=

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) =

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

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

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

  1. a b Ackermann Function from Wolfram MathWorld mathworld.wolfram.com. 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
Käännös suomeksi
Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.