Ackermann-toiminto

Ackermann-funktio on yksinkertainen esimerkki kaikkialla määritellystä laskettavasta funktiosta , joka ei ole primitiivinen rekursiivinen . Se ottaa kaksi ei-negatiivista kokonaislukua parametreiksi ja palauttaa luonnollisen luvun , joka on merkitty . Tämä funktio kasvaa hyvin nopeasti, esimerkiksi luku on niin suuri, että numeroiden määrä tämän luvun järjestyksessä on monta kertaa suurempi kuin atomien lukumäärä universumin havaittavassa osassa . $A(m,\;n)$ $A(4,\;4)$

Historia

1920-luvun lopulla David Hilbertin matemaatikot Gabriel Sudan ja Wilhelm Ackermann tutkivat tietojenkäsittelyn perusteita. Sudan ja Ackerman ovat kuuluisia [1] siitä, että he ovat löytäneet kaikkialla määritellyn laskettavan funktion (jota joskus kutsutaan yksinkertaisesti "rekursiiviseksi"), joka ei ole primitiivinen rekursiivinen . Sudan löysi vähemmän tunnetun funktion Sudan , jonka jälkeen Ackerman hänestä riippumatta julkaisi tehtävänsä vuonna 1928 . Kolmen argumentin Ackermann-funktio määriteltiin siten, että se suoritti sille yhteen-, kerto- tai eksponentiooperaation: $\varphi$ $\varphi (m,\,n,\,p)$ $p=0,\;1,\;2$

\varphi (m,\,n,\,0)=m+n,

\varphi (m,\,n,\,1)=m\cdot n,

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

ja sitä on laajennettu käyttämällä Knuthin vuonna 1976 julkaistua nuolen merkintää: $p>2$

\varphi (m,\,n,\,p)=m\uparrow ^{p-1}(n+1)

(Sen lisäksi, että Ackermannin alkuperäinen funktio oli historiallinen rooli ensimmäisenä kaikkialla määriteltynä ei-primitiivisenä rekursiivisena laskettavana funktiona, se laajensi aritmeettisia perusoperaatioita eksponentioinnin ulkopuolelle, vaikkakaan ei yhtä hyvin dedikoituja toimintoja, kuten Goodsteinin hyperoperaattorisekvenssiä .)

Teoksessaan On the Infinite Hilbert arveli, että Ackermannin funktio ei ole primitiivisesti rekursiivinen, ja Ackerman (Hilbertin henkilökohtainen sihteeri ja entinen oppilas) osoitti tämän olettamuksen teoksessa On Hilbert's Construction of the Real Numbers. Rosa Peter ja Raphael Robinson esittelivät myöhemmin kaksiargumenttisen version Ackermann-funktiosta, jota monet kirjoittajat pitävät nykyään parempana kuin alkuperäinen [2] .

Määritelmä

Ackermann-funktio määritellään rekursiivisesti ei-negatiivisille kokonaisluvuille seuraavasti : $m$ $n$

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

Ei ehkä näytä itsestään selvältä, että rekursio päättyy aina. Tämä johtuu siitä, että rekursiivisessa kutsussa joko arvoa pienennetään tai arvo säilytetään, mutta arvoa pienennetään . Tämä tarkoittaa, että joka kerta kun paria pienennetään leksikografisen järjestyksen suhteen , mikä tarkoittaa, että arvo saavuttaa lopulta nollan: yhdelle arvolle on rajallinen määrä mahdollisia arvoja (koska ensimmäinen puhelu datalla oli tehty jollain tietyllä arvolla , ja lisäksi, jos arvo säilytetään, arvo voi vain pienentyä), ja mahdollisten arvojen määrä puolestaan on myös äärellinen. Kuitenkin, kun pienennetään , arvo, joka kasvaa arvolla, on rajoittamaton ja yleensä erittäin suuri. $m$ $m$ $n$ $(m,\;n)$ $m$ $m$ $n$ $m$ $n$ $m$ $n$ $m$ $m$ $n$

Arvotaulukko

Katso hyper-operaattorilta lisätietoja hyperistä .

$n$ $\|m$	$0$	$yksi$	$2$	$3$	$neljä$	$5$	$m$
$0$	$yksi$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hyper}}(2,\;m,\;3)-3$
$yksi$	$2$	$3$	$5$	$13$	$65533$	$\alasiviiva {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}-3$	${\mathrm {hyper}}(2,\;m,\;4)-3$
$2$	$3$	$neljä$	$7$	$29$	$2^{{65536}}-3$	$\alleviivaus {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{{\aliviiva {2^{{2^ {{ \cdot ^{{\cdot ^{{\cdot ^{2)))))))))))))_{{65536))))-3$	${\mathrm {hyper}}(2,\;m,\;5)-3$
$3$	$neljä$	$5$	$9$	$61$	$2^{{2^{{65536}}}}-3$	$A(4,\;\aliaisviiva {2^{{2^{{\cdot ^({\cdot ^({\cdot ^{2))))))))))))_({\aliaismerkki 2^ {{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536))))-3)$	${\mathrm {hyper}}(2,\;m,\;6)-3$
$neljä$	$5$	$6$	$yksitoista$	$125$	$2^{{2^{{2^{{65536}}}}}}-3$	$A(4,\;A(5,\;3))$	${\mathrm {hyper}}(2,\;m,\;7)-3$
$5$	$6$	$7$	$13$	$253$	$2^{{2^{{2^{{2^{{65536}}}}}}}}-3$	$A(4,\;A(5,\;4))$	${\mathrm {hyper}}(2,\;m,\;8)-3$
$n$	$n+1$	$n+2$	$2n+3$	$2^{{n+3}}-3$	$\alasiviiva {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{n+3}}-3$	$\aliviiva {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{({\aliviiva {\aliviiva {2^ {{ 2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}}{\vdots }}}}-3$ ( lohkot yhteensä ) $n$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))}$	${\mathrm {hyper}}(2,\;m,\;n+3)-3$

Käänteisfunktio

Koska funktio kasvaa hyvin nopeasti, käänteisfunktio , jota merkitään , kasvaa hyvin hitaasti. Tämä funktio on tavattu tutkittaessa joidenkin algoritmien monimutkaisuutta , esimerkiksi disjunktijoukkojen järjestelmää tai Chazell-algoritmia minimivirittävän puun rakentamiseen [3] . Analysoitaessa asymptotiikkaa voidaan olettaa, että kaikilla käytännössä esiintyvillä luvuilla tämän funktion arvo on pienempi kuin viisi, koska se ei ole pienempi kuin . $f(n)=A(n,\;n)$ $f^{{-1}}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}$ $\alpha$ ${\näyttötyyli A(4,\,4)}$ ${\displaystyle 10^{10^{10^{19500))))$

Käyttö suorituskykytesteissä

Ackerman-funktiolla on määritelmänsä perusteella erittäin syvä rekursiotaso, jonka avulla voidaan testata kääntäjän kykyä optimoida rekursio. Yngwie Sundblad [4] käytti ensimmäisenä Ackerman-funktiota tähän .

Brian Wichman ( Whetstone-benchmarkin toinen kirjoittaja ) otti tämän artikkelin huomioon kirjoittaessaan artikkelisarjan puhelun optimointitestauksesta [5] [6] [7] .

Esimerkiksi kääntäjä, joka pystyy laskentaa analysoidessaan tallentamaan väliarvot, esimerkiksi ja , voi nopeuttaa laskentaa satoja ja tuhansia kertoja. Myös suora arviointi rekursiivisen laajennuksen sijaan nopeuttaa laskentaa melkoisesti. Laskenta kestää lineaarista aikaa . Laskenta vaatii neliöaikaa, koska se laajenee O ( ) sisäkkäisiksi kutsuiksi eri . Laskenta-aika on verrannollinen . ${\näyttötyyli A(3,\,30)}$ ${\näyttötyyli A(3,\,n)}$ ${\näyttötyyli A(2,\,n)}$ ${\näyttötyyli A(3,\,30)}$ ${\näyttötyyli A(2,\,n)}$ $A(1,\,A(1,\,A(1,\,\ldots A(1,\,0)\ldots )))$ ${\näyttötyyli A(1,\,n)}$ $n$ ${\näyttötyyli A(2,\,n)}$ $n$ ${\näyttötyyli A(1,\,i)}$ $i$ ${\näyttötyyli A(3,\,n)}$ $4^{n+1}$

Arvoa ei voida laskea yksinkertaisella rekursiivisella sovelluksella kohtuullisessa ajassa. Sen sijaan rekursiivisten kutsujen optimointiin käytetään pikakaavoja, kuten . ${\näyttötyyli A(4,\,n)}$ $A(3,\,n)=8\cdot 2^{n}-3$

Yksi käytännöllisistä tavoista laskea Ackermann-funktion arvot on välitulosten muistiin tallentaminen . Kääntäjä voi soveltaa tätä tekniikkaa funktioon automaattisesti käyttämällä muistiofunktioita [8] [9] , kirjoittaja Donald Michie .

Muistiinpanot

↑ Cristian Calude, Solomon Marcus ja Ionel Tevy . Ensimmäinen esimerkki rekursiivisesta funktiosta, joka ei ole primitiivinen rekursiivinen // Historia Math . : päiväkirja. - 1979. - marraskuu ( osa 6 , nro 4 ). - s. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Raphael M. Robinson . Rekursio ja kaksoisrekursio (neopr.) // Bulletin of the American mathematical Society . - 1948. - T. 54 , nro 10 . - S. 987-993 . - doi : 10.1090/S0002-9904-1948-09121-2 . Arkistoitu alkuperäisestä 7. kesäkuuta 2011.
↑ Diskreetti matematiikka: Algoritmit. Vähimmäisvälit (linkki ei ole käytettävissä) . Haettu 13. elokuuta 2011. Arkistoitu alkuperäisestä 2. kesäkuuta 2010. (määrätön)
↑ Y. Sundblad . Ackermann-funktio. Teoreettinen, laskennallinen ja kaavamanipulaatiotutkimus (englanniksi) // BIT : Journal. - 1971. - Voi. 11 . - s. 107-119 . - doi : 10.1007/BF01935330 . (linkki ei saatavilla)
↑ Ackermannin funktio: Tutkimus kutsumenettelyjen tehokkuudesta (1975). Haettu 13. elokuuta 2011. Arkistoitu alkuperäisestä 23. helmikuuta 2012. (määrätön)
↑ Kuinka kutsua menettelyjä tai toisia ajatuksia Ackermannin funktiosta (1977). Haettu 13. elokuuta 2011. Arkistoitu alkuperäisestä 23. helmikuuta 2012. (määrätön)
↑ Viimeisimmät tulokset menettelyn kutsutestistä. Ackermannin funktio (1982). Haettu 13. elokuuta 2011. Arkistoitu alkuperäisestä 23. helmikuuta 2012. (määrätön)
↑ Michie, Donald Memo-toiminnot ja koneoppiminen, Luonto , no. 218, s. 19-22, 1968.
↑ Esimerkki: Ackermannin funktion eksplisiittinen muistiofunktion versio Arkistoitu 17. heinäkuuta 2011 Wayback Machinessa PL/SQL:llä toteutettuina.

Linkit

Weisstein, Eric W. Ackermann Function (englanniksi) Wolfram MathWorld -verkkosivustolla .

Isoja lukuja
Numerot	googol Shannonin numero Googolplex Skewesin numero Moser numero Grahamin numero PUU(3) Rayo numero
Toiminnot	Ackermann-toiminto Veblen-toiminto Buchholzin Psi-funktiot tetration Pentation Hyperoperaattori Nopeasti kasvava hierarkia Hierarkia kasvaa hitaasti Kova hierarkia
Merkinnät	Steinhaus-Moser-merkintä Knuthin nuolen merkintä Conway-nuolen merkintä Massiivinen Bowers-merkintä