Ackermann funktion

Ackermann-funktionen er et simpelt eksempel på en overalt defineret beregnelig funktion , der ikke er primitiv rekursiv . Det tager to ikke-negative heltal som parametre og returnerer et naturligt tal , angivet med . Denne funktion vokser meget hurtigt, for eksempel er tallet så stort, at antallet af cifre i rækkefølgen af dette tal er mange gange større end antallet af atomer i den observerbare del af universet . $A(m,\;n)$ $A(4,\;4)$

Historie

I slutningen af 1920'erne studerede David Hilberts matematikere , Gabriel Sudan og Wilhelm Ackermann , det grundlæggende i databehandling. Sudan og Ackerman er berømte [1] for at opdage en overalt defineret beregnelig funktion (nogle gange blot kaldet "rekursiv"), som ikke er primitiv rekursiv . Sudan opdagede den mindre kendte funktion Sudan , hvorefter Ackerman uafhængigt af ham offentliggjorde sin funktion i 1928 . Ackermann-funktionen af tre argumenter blev defineret på en sådan måde, at den for den udførte operationen addition, multiplikation eller eksponentiering: $\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},

og for det er udvidet ved hjælp af Knuths pilnotation , udgivet i 1976: $p>2$

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

(Ud over sin historiske rolle som den første overalt definerede ikke-primitive rekursive beregnelige funktion, udvidede Ackermanns oprindelige funktion grundlæggende aritmetiske operationer ud over eksponentiering, dog ikke så godt som dedikerede funktioner som Goodsteins hyperoperatorsekvens .)

I On the Infinite formodede Hilbert, at Ackermanns funktion ikke er primitivt rekursiv, og Ackerman (Hilberts personlige sekretær og tidligere studerende) beviste denne formodning i On Hilberts Construction of the Real Numbers. Rosa Peter og Raphael Robinson præsenterede senere en to-argument version af Ackermann-funktionen, som mange forfattere nu foretrækker frem for originalen [2] .

Definition

Ackermann-funktionen er defineret rekursivt for ikke-negative heltal og som følger: $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}

Det virker måske ikke indlysende, at rekursion altid slutter. Dette følger af, at i et rekursivt kald enten reduceres værdien af , eller værdien bevares, men værdien reduceres . Dette betyder, at hver gang parret reduceres med hensyn til leksikografisk rækkefølge , hvilket betyder, at værdien til sidst vil nå nul: for én værdi er der et begrænset antal mulige værdier (siden det første opkald med dataene var lavet med en bestemt værdi , og yderligere, hvis værdien bevares, kan værdien kun falde), og antallet af mulige værdier er til gengæld også begrænset. Men når den falder , er den værdi, der stiger med, ubegrænset og normalt meget stor. $m$ $m$ $n$ $(m,\;n)$ $m$ $m$ $n$ $m$ $n$ $m$ $n$ $m$ $m$ $n$

Tabel over værdier

Se hyperoperatøren for detaljer om hyper .

$n$ $\|m$	$0$	$en$	$2$	$3$	$fire$	$5$	$m$
$0$	$en$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hyper}}(2,\;m,\;3)-3$
$en$	$2$	$3$	$5$	$13$	$65533$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536}}-3$	${\mathrm {hyper}}(2,\;m,\;4)-3$
$2$	$3$	$fire$	$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$	$fire$	$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$
$fire$	$5$	$6$	$elleve$	$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$ (total blokke ) $n$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))}$	${\mathrm {hyper}}(2,\;m,\;n+3)-3$

Invers funktion

Da funktionen vokser meget hurtigt, vokser den omvendte funktion , betegnet med , meget langsomt. Denne funktion støder man på i studiet af kompleksiteten af nogle algoritmer , for eksempel et system af usammenhængende sæt eller Chazell-algoritmen til at konstruere et minimumspændende træ [3] . Når vi analyserer asymptotikken , kan vi antage, at for alle praktisk talt forekommende tal er værdien af denne funktion mindre end fem, da den ikke er mindre end . $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))))$

Brug i præstationstests

Ackerman-funktionen har i kraft af sin definition et meget dybt niveau af rekursion, som kan bruges til at teste compilerens evne til at optimere rekursion. Yngwie Sundblad [4] var den første til at bruge Ackerman-funktionen til dette .

Brian Wichman (medforfatter af Whetstone benchmark ) tog denne artikel i betragtning, da han skrev en række artikler om opkaldsoptimeringstest [5] [6] [7] .

For eksempel kan en compiler, der ved analyse af en beregning er i stand til at gemme mellemværdier, for eksempel og , fremskynde beregningen med hundreder og tusinder af gange. Også at evaluere direkte i stedet for rekursivt at udvide ind vil fremskynde beregningen en del. Beregningen tager lineær tid . Beregningen kræver kvadratisk tid, da den udvides til O ( ) indlejrede kald for forskellige . Beregningstiden er proportional med . $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)$ $jeg$ $A(3,\,n)$ $4^{n+1}$

Værdien kan ikke beregnes med en simpel rekursiv applikation inden for rimelig tid. I stedet bruges stenografiformler til at optimere rekursive opkald, som f.eks . $A(4,\,n)$ $A(3,\,n)=8\cdot 2^{n}-3$

En af de praktiske måder at beregne værdierne af Ackermann-funktionen på er memoisering af mellemresultater. Compileren kan anvende denne teknik til en funktion automatisk ved hjælp af memofunktioner [8] [9] af Donald Michie .

Noter

↑ Cristian Calude, Solomon Marcus og Ionel Tevy . Det første eksempel på en rekursiv funktion, som ikke er primitiv rekursiv // Historia Math . : journal. - 1979. - November ( bind 6 , nr. 4 ). - S. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Raphael M. Robinson . Rekursion og dobbelt rekursion (neopr.) // Bulletin of the American mathematical Society . - 1948. - T. 54 , nr. 10 . - S. 987-993 . - doi : 10.1090/S0002-9904-1948-09121-2 . Arkiveret fra originalen den 7. juni 2011.
↑ Diskret matematik: Algoritmer. Minimumsspændende træer (linket er ikke tilgængeligt) . Hentet 13. august 2011. Arkiveret fra originalen 2. juni 2010. (ubestemt)
↑ Y. Sundblad . Ackermann-funktionen. En teoretisk, beregningsmæssig og formel manipulativ undersøgelse (engelsk) // BIT : journal. - 1971. - Bd. 11 . - S. 107-119 . - doi : 10.1007/BF01935330 . (utilgængeligt link)
↑ Ackermanns funktion: En undersøgelse af effektiviteten af opkaldsprocedurer (1975). Hentet 13. august 2011. Arkiveret fra originalen 23. februar 2012. (ubestemt)
↑ Sådan kalder du procedurer eller overvejelser om Ackermanns funktion (1977). Hentet 13. august 2011. Arkiveret fra originalen 23. februar 2012. (ubestemt)
↑ Seneste resultater fra procedurekaldstesten. Ackermanns funktion (1982). Hentet 13. august 2011. Arkiveret fra originalen 23. februar 2012. (ubestemt)
↑ Michie, Donald Memofunktioner og maskinlæring, Nature , nr. 218, s. 19-22, 1968.
↑ Eksempel: eksplicit memo funktion version af Ackermanns funktion Arkiveret 17. juli 2011 på Wayback Machine implementeret i PL/SQL.

Links

Weisstein, Eric W. Ackermann Function (engelsk) på Wolfram MathWorld- webstedet .

Store tal
Tal	google Shannon nummer Googolplex Skæv nummer Moser nummer Graham nummer TRÆ(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner af Buchholz tetration Pentation Hyperoperator Hurtigt voksende hierarki Langsomt voksende hierarki Hardy hierarki
Notationer	Steinhaus-Moser notation Knuth pil notation Conway pil notation Massive Bowers-notation