Ackermann funktion

Ackermann-funktionen är ett enkelt exempel på en överallt definierad beräkningsbar funktion som inte är primitiv rekursiv . Den tar två icke-negativa heltal som parametrar och returnerar ett naturligt tal , betecknat med . Denna funktion växer mycket snabbt, till exempel är antalet så stort att antalet siffror i ordningen för detta nummer är många gånger större än antalet atomer i den observerbara delen av universum . $A(m,\;n)$ $A(4,\;4)$

Historik

I slutet av 1920-talet studerade David Hilberts matematiker , Gabriel Sudan och Wilhelm Ackermann , grunderna för datoranvändning. Sudan och Ackerman är kända [1] för att ha upptäckt en överallt definierad beräkningsbar funktion (ibland kallad helt enkelt "rekursiv") som inte är primitiv rekursiv . Sudan upptäckte den mindre kända funktionen Sudan , varefter Ackerman, oberoende av honom, publicerade sin funktion 1928 . Ackermann-funktionen för tre argument definierades på ett sådant sätt att den utförde operationen addition, multiplikation eller exponentiering: $\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},

och för det utökas med Knuths pilnotation , publicerad 1976: $p>2$

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

(Förutom sin historiska roll som den första överallt definierade icke-primitiva rekursiva beräkningsbara funktionen, utökade Ackermanns ursprungliga funktion grundläggande aritmetiska operationer bortom exponentiering, dock inte lika bra som dedikerade funktioner som Goodsteins hyperoperatorsekvens .)

I On the Infinite antog Hilbert att Ackermanns funktion inte är primitivt rekursiv, och Ackerman (Hilberts personliga sekreterare och tidigare student) bevisade denna gissning i On Hilberts Construction of the Real Numbers. Rosa Peter och Raphael Robinson presenterade senare en tvåargumentversion av Ackermann-funktionen, som många författare nu föredrar framför originalet [2] .

Definition

Ackermann-funktionen definieras rekursivt för icke-negativa heltal och enligt följande: $m$ $n$

A(m,\;n)=\begin{fall}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}

Det kanske inte verkar självklart att rekursion alltid tar slut. Detta följer av det faktum att i ett rekursivt anrop minskas antingen värdet på , eller så bevaras värdet, men värdet reduceras . Detta innebär att varje gång paret reduceras i termer av lexikografisk ordning , vilket betyder att värdet så småningom kommer att nå noll: för ett värde finns det ett ändligt antal möjliga värden (eftersom det första samtalet med data var gjord med ett visst värde , och vidare, om värdet bevaras, kan värdet bara minska), och antalet möjliga värden är i sin tur också ändligt. Men vid minskning är värdet som ökar med obegränsat och vanligtvis mycket stort. $m$ $m$ $n$ $(m,\;n)$ $m$ $m$ $n$ $m$ $n$ $m$ $n$ $m$ $m$ $n$

Värdetabell

Se hyperoperatorn för detaljer om hyper .

$n$ $\|m$	$0$	$ett$	$2$	$3$	$fyra$	$5$	$m$
$0$	$ett$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hyper}}(2,\;m,\;3)-3$
$ett$	$2$	$3$	$5$	$13$	$65533$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536}}-3$	${\mathrm {hyper}}(2,\;m,\;4)-3$
$2$	$3$	$fyra$	$7$	$29$	$2^{{65536}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{{\underbrace {2^{{2^ {{ \cdot ^{{\cdot ^{{\cdot ^{2)))))))))))))_{{65536))))-3$	${\mathrm {hyper}}(2,\;m,\;5)-3$
$3$	$fyra$	$5$	$9$	$61$	$2^{{2^{{65536}}}}-3$	$A(4,\;\underbrace {2^{{2^{{\cdot ^({\cdot ^({\cdot ^{2))))))))))))_({\underbrace { 2^ {{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536)))))-3)$	${\mathrm {hyper}}(2,\;m,\;6)-3$
$fyra$	$5$	$6$	$elva$	$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$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{n+3}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{({\underset {\underbrace {2^ {{ 2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536}}}{\vdots }}}}-3$ (totalt antal block ) $n$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))}$	${\mathrm {hyper}}(2,\;m,\;n+3)-3$

Invers funktion

Eftersom funktionen växer mycket snabbt, växer den omvända funktionen , betecknad med , mycket långsamt. Denna funktion påträffas i studiet av komplexiteten hos vissa algoritmer , till exempel ett system av disjunkta uppsättningar eller Chazell-algoritmen för att konstruera ett minsta spännträd [3] . När vi analyserar asymptotikerna kan vi anta att för alla praktiskt förekommande tal är värdet på denna funktion mindre än fem, eftersom det inte är mindre än . $f(n)=A(n,\;n)$ $f^{{-1}}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}$ $\alfa$ $A(4,\,4)$ ${\displaystyle 10^{10^{10^{19500))))$

Användning i prestandatester

Ackerman-funktionen har i kraft av sin definition en mycket djup nivå av rekursion, som kan användas för att testa kompilatorns förmåga att optimera rekursion. Yngwie Sundblad [4] var den första som använde Ackerman-funktionen för detta .

Brian Wichman (medförfattare till Whetstone benchmark ) tog hänsyn till denna artikel när han skrev en serie artiklar om samtalsoptimeringstestning [5] [6] [7] .

Till exempel kan en kompilator som vid analys av en beräkning kan lagra mellanvärden, till exempel och , påskynda beräkningen hundratals och tusentals gånger. Att även utvärdera direkt istället för att expandera rekursivt kommer att påskynda beräkningen en hel del. Beräkningen tar linjär tid . Beräkningen kräver kvadratisk tid, eftersom den expanderar till O ( ) kapslade anrop för olika . Beräkningstiden är proportionell mot . $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)$ $i$ $A(3,\,n)$ $4^{n+1}$

Värdet kan inte beräknas med en enkel rekursiv applikation inom rimlig tid. Istället används stenografiformler för att optimera rekursiva anrop, som . $A(4,\,n)$ $A(3,\,n)=8\cdot 2^{n}-3$

Ett av de praktiska sätten att beräkna värdena för Ackermann-funktionen är memoisering av mellanresultat. Kompilatorn kan tillämpa denna teknik på en funktion automatiskt med memofunktioner [8] [9] av Donald Michie .

Anteckningar

↑ Cristian Calude, Solomon Marcus och Ionel Tevy . Det första exemplet på en rekursiv funktion som inte är primitiv rekursiv // Historia Math . : journal. - 1979. - November ( vol. 6 , nr 4 ). - s. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Raphael M. Robinson . Rekursion och dubbelrekursion (neopr.) // Bulletin of the American mathematical society . - 1948. - T. 54 , nr 10 . - S. 987-993 . - doi : 10.1090/S0002-9904-1948-09121-2 . Arkiverad från originalet den 7 juni 2011.
↑ Diskret matematik: Algoritmer. Minsta spännträd (länk ej tillgänglig) . Hämtad 13 augusti 2011. Arkiverad från originalet 2 juni 2010. (obestämd)
↑ Y. Sundblad . Ackermann-funktionen. En teoretisk, beräknings- och formelmanipulativ studie (engelska) // BIT : journal. - 1971. - Vol. 11 . - S. 107-119 . - doi : 10.1007/BF01935330 . (inte tillgänglig länk)
↑ Ackermanns funktion: En studie i effektiviteten av anropsprocedurer (1975). Hämtad 13 augusti 2011. Arkiverad från originalet 23 februari 2012. (obestämd)
↑ Hur man anropar procedurer, eller andra tankar om Ackermanns funktion (1977). Hämtad 13 augusti 2011. Arkiverad från originalet 23 februari 2012. (obestämd)
↑ Senaste resultaten från proceduranropstestet. Ackermanns funktion (1982). Hämtad 13 augusti 2011. Arkiverad från originalet 23 februari 2012. (obestämd)
↑ Michie, Donald Memofunktioner och maskininlärning, Nature , nr. 218, sid. 19-22, 1968.
↑ Exempel: explicit memofunktionsversion av Ackermanns funktion Arkiverad 17 juli 2011 på Wayback Machine implementerad i PL/SQL.

Länkar

Weisstein, Eric W. Ackermann Function (engelska) på Wolfram MathWorlds webbplats .

Stora siffror
Tal	googol Shannon nummer Googolplex Skeves nummer Moser nummer Graham nummer TRÄD(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner för Buchholz tetration Pentation Hyperoperator Snabbväxande hierarki Långsamt växande hierarki Härlig hierarki
Noteringar	Steinhaus-Moser notation Knuth pilnotation Conway pil notation Massiv Bowers Notation