Ackermann függvény

Az Ackermann függvény egy egyszerű példa egy mindenhol definiált kiszámítható függvényre , amely nem primitív rekurzív . Két nem negatív egész számot vesz paraméterként, és egy természetes számot ad vissza , amelyet jelöl . Ez a függvény nagyon gyorsan növekszik, például a szám olyan nagy, hogy a számsorrendben lévő számjegyek száma sokszorosa az Univerzum megfigyelhető részében lévő atomok számának . $A(m,\;n)$ $A(4;\;4)$

Történelem

Az 1920-as évek végén David Hilbert matematikusai , Gabriel Sudan és Wilhelm Ackermann a számítástechnika alapjait tanulmányozták. Sudan és Ackerman híresek [1] arról, hogy felfedeztek egy mindenhol definiált kiszámítható függvényt (amit néha egyszerűen "rekurzívnak" neveznek), amely nem primitív rekurzív . Szudán felfedezte a kevésbé ismert Szudán funkciót , ami után tőle függetlenül Ackerman 1928-ban publikálta funkcióját . A három argumentumból álló Ackermann-függvényt úgy határoztuk meg, hogy az összeadás, szorzás vagy hatványozás műveletét hajtotta végre: $\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},

és kibővítésre került Knuth 1976-ban közzétett nyíl jelölésével : $p>2$

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

(Amellett, hogy történelmi szerepe volt az első, mindenhol definiált, nem primitív rekurzív kiszámítható függvény, Ackermann eredeti függvénye kiterjesztette az alapvető aritmetikai műveleteket a hatványozáson túlra, bár nem olyan jól az olyan dedikált függvényeket, mint a Goodstein -féle hiperoperátor sorozat .)

A végtelenről című művében Hilbert azt sejtette, hogy Ackermann függvénye nem primitíven rekurzív, és Ackerman (Hilbert személyi titkára és egykori tanítványa) bebizonyította ezt a sejtést Hilbert A valós számok felépítése című művében. Rosa Peter és Raphael Robinson később bemutatta az Ackermann-függvény kétargumentumos változatát, amelyet sok szerző most az eredetivel szemben preferál [2] .

Definíció

Az Ackermann-függvény rekurzív módon van definiálva nemnegatív egész számokhoz , és a következőképpen: $m$ $n$

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

Talán nem tűnik nyilvánvalónak, hogy a rekurzió mindig véget ér. Ez abból következik, hogy egy rekurzív hívásnál vagy az értéke csökken , vagy az értéke megmarad, de az értéke csökken . Ez azt jelenti, hogy minden alkalommal, amikor a pár lexikográfiai sorrendben csökken , ami azt jelenti, hogy az érték végül eléri a nullát: egy értékhez véges számú lehetséges érték van (mivel az első hívás az adatokkal valamilyen meghatározott értékkel készült , és ha az érték megmarad, az érték csak csökkenhet), és a lehetséges értékek száma is véges. Csökkentésekor azonban a -kal növekvő érték korlátlan és általában nagyon nagy. $m$ $m$ $n$ $(m,\;n)$ $m$ $m$ $n$ $m$ $n$ $m$ $n$ $m$ $m$ $n$

Értéktáblázat

Lásd a hyper operátort a hyper részleteiért .

$n$ $\|m$	$0$	$egy$	$2$	$3$	$négy$	$5$	$m$
$0$	$egy$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hiper}}(2,\;m,\;3)-3$
$egy$	$2$	$3$	$5$	$13$	$65533$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}-3$	${\mathrm {hiper}}(2,\;m,\;4)-3$
$2$	$3$	$négy$	$7$	$29$	$2^{{65536}}-3$	$\kapcsos zárójel {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{{\kapcsos zárójel {2^{{2^ {{ \cdot ^{{\cdot ^{{\cdot ^{2))))))))))))_{{65536))))-3$	${\mathrm {hiper}}(2,\;m,\;5)-3$
$3$	$négy$	$5$	$9$	$61$	$2^{{2^{{65536}}}}-3$	$A(4,\;\zárójel {2^{{2^{{\cdot ^({\cdot ^({\cdot ^{2))))))))))))_({\kapcsos zárójel { 2^ {{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536))))-3)$	${\mathrm {hiper}}(2,\;m,\;6)-3$
$négy$	$5$	$6$	$tizenegy$	$125$	$2^{{2^{{2^{{65536}}}}}}-3$	$A(4;\;A(5;\;3))$	${\mathrm {hiper}}(2,\;m,\;7)-3$
$5$	$6$	$7$	$13$	$253$	$2^{{2^{{2^{{2^{{65536}}}}}}}}-3$	$A(4;\;A(5;\;4))$	${\mathrm {hiper}}(2,\;m,\;8)-3$
$n$	$n+1$	$n+2$	$2n+3$	$2^{{n+3}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{n+3}}-3$	$\kapcsos zárójel {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{({\aláírásos {\kapcsos zárójel {2^ {{ 2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}}{\vdots }}}}-3$ (összes blokk ) $n$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))}$	${\mathrm {hiper}}(2,\;m,\;n+3)-3$

Inverz függvény

Mivel a függvény nagyon gyorsan növekszik, az inverz függvény , amelyet jelöl , nagyon lassan növekszik. Ezzel a függvénnyel találkozhatunk néhány algoritmus komplexitásának tanulmányozása során , például egy diszjunkt halmazrendszer vagy a Chazell-algoritmus egy minimális feszítőfa létrehozására [3] . Az aszimptotika elemzésekor feltételezhetjük, hogy minden gyakorlatilag előforduló számra ennek a függvénynek az értéke kisebb, mint öt, mivel nem kisebb, mint . $f(n)=A(n,\;n)$ $f^{{-1}}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}$ $\alpha$ $A(4,\,4)$ ${\displaystyle 10^{10^{10^{19500))))$

Használat teljesítménytesztekben

Az Ackerman függvény definíciójából adódóan nagyon mély rekurziós szinttel rendelkezik, amellyel tesztelhető a fordító rekurzióoptimalizáló képessége. Yngwie Sundblad [4] volt az első, aki erre az Ackerman függvényt használta .

Brian Wichman ( a Whetstone benchmark társszerzője ) figyelembe vette ezt a cikket, amikor cikksorozatot írt a hívásoptimalizálás teszteléséről [5] [6] [7] .

Például egy olyan fordító, amely egy számítás elemzésekor képes közbenső értékeket tárolni, például és , száz- és ezerszeresére gyorsíthatja a számítást . A rekurzív kibővítés helyett közvetlen kiértékelés is jelentősen felgyorsítja a számítást. A számítás lineáris időt vesz igénybe . A számítás másodfokú időt igényel, mivel O ( ) beágyazott hívásokká bővül a különböző . A számítási idő arányos . $A(3,\,30)$ $A(3,\,n)$ $A(2,\,n)$ $A(3,\,30)$ $A(2,\,n)$ $A(1,\,A(1,\,A(1,\,\ldots A(1,\,0)\ldots )))$ $A(1,\,n)$ $n$ $A(2,\,n)$ $n$ $A(1,\,i)$ $én$ $A(3,\,n)$ $4^{n+1}$

Az érték egyszerű rekurzív alkalmazással ésszerű időn belül nem számítható ki. Ehelyett gyorsírási képleteket használnak a rekurzív hívások optimalizálására, például . $A(4,\,n)$ $A(3,\,n)=8\cdot 2^{n}-3$

Az Ackermann-függvény értékeinek kiszámításának egyik gyakorlati módja a köztes eredmények memorizálása . A fordító ezt a technikát automatikusan alkalmazhatja egy függvényre Donald Michie memo függvényeinek [8] [9] segítségével .

Jegyzetek

↑ Cristian Calude, Solomon Marcus és Ionel Tevy . Az első példa egy rekurzív függvényre, amely nem primitív rekurzív // Historia Math . : folyóirat. - 1979. - november ( 6. köt. , 4. sz.). - P. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Raphael M. Robinson . Rekurzió és kettős rekurzió (neopr.) // Bulletin of the American Mathematical Society . - 1948. - T. 54 , 10. sz . - S. 987-993 . - doi : 10.1090/S0002-9904-1948-09121-2 . Archiválva az eredetiből 2011. június 7-én.
↑ Diszkrét matematika: Algoritmusok. Minimálisan átívelő fák (a link nem érhető el) . Letöltve: 2011. augusztus 13. Az eredetiből archiválva : 2010. június 2. (неопр.)
↑ Y. Sundblad . Az Ackermann függvény. Elméleti, számítási és képletmanipulációs tanulmány (angol) // BIT : folyóirat. - 1971. - 1. évf. 11 . - 107-119 . o . - doi : 10.1007/BF01935330 . (nem elérhető link)
↑ Ackermann-függvény: Tanulmány a hívási eljárások hatékonyságáról (1975). Letöltve: 2011. augusztus 13. Az eredetiből archiválva : 2012. február 23.. (неопр.)
↑ Hogyan nevezzük az eljárásokat, avagy második gondolatok Ackermann függvényéről (1977). Letöltve: 2011. augusztus 13. Az eredetiből archiválva : 2012. február 23.. (неопр.)
↑ Az eljáráshívási teszt legfrissebb eredményei. Ackermann függvénye (1982). Letöltve: 2011. augusztus 13. Az eredetiből archiválva : 2012. február 23.. (неопр.)
↑ Michie, Donald Memo funkciók és gépi tanulás, Nature , no. 218, pp. 1968. 19-22.
↑ Példa: Ackermann függvény explicit memo függvény verziója Archiválva 2011. július 17-én a Wayback Machine -nél PL/SQL-ben implementálva.

Linkek

Weisstein, Eric W. Ackermann függvény (angolul) a Wolfram MathWorld webhelyen .

Nagy számok
Számok	googol Shannon szám Googolplex Skewes szám Moser szám Graham szám FA (3) Rayo szám
Funkciók	Ackermann függvény Veblen funkció Buchholz Pszi-függvényei tetració Pentation Hiperoperátor Gyorsan növekvő hierarchia Lassan növekvő hierarchia Hardy hierarchia
Jelölések	Steinhaus-Moser jelölés Knuth nyíl jelölése Conway nyíl jelölése Massive Bowers jelölés