Funcția Ackermann

Funcția Ackermann este un exemplu simplu de funcție computabilă definită peste tot, care nu este recursivă primitivă . Ia două numere întregi nenegative ca parametri și returnează un număr natural , notat cu . Această funcție crește foarte repede, de exemplu, numărul este atât de mare încât numărul de cifre din ordinea acestui număr este de multe ori mai mare decât numărul de atomi din partea observabilă a Universului . $A(m,\;n)$ $A(4,\;4)$

Istorie

La sfârșitul anilor 1920, matematicienii lui David Hilbert , Gabriel Sudan și Wilhelm Ackermann , au studiat bazele calculului. Sudan și Ackerman sunt faimoși [1] pentru că au descoperit o funcție computabilă definită peste tot (uneori numită pur și simplu „recursivă”) care nu este recursivă primitivă . Sudan a descoperit funcția mai puțin cunoscută Sudan , după care, independent de el, Ackerman și-a publicat funcția în 1928 . Funcția Ackermann a trei argumente a fost definită în așa fel încât pentru aceasta a efectuat operația de adunare, înmulțire sau exponențiere: $\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},

și pentru aceasta este extinsă folosind notația săgeată a lui Knuth , publicată în 1976: $p>2$

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

(Pe lângă rolul său istoric de prima funcție computabilă recursivă neprimitivă definită peste tot, funcția originală a lui Ackermann a extins operațiile aritmetice de bază dincolo de exponențiere, deși nu la fel de bine ca funcții dedicate precum secvența hiperoperatorului lui Goodstein .)

În Despre infinit, Hilbert a presupus că funcția lui Ackermann nu este recursivă primitiv, iar Ackerman (secretarul personal și fostul student al lui Hilbert) a demonstrat această presupunere în Construcția numerelor reale a lui Hilbert. Rosa Peter și Raphael Robinson au prezentat ulterior o versiune cu două argumente a funcției Ackermann, pe care mulți autori o preferă acum față de originalul [2] .

Definiție

Funcția Ackermann este definită recursiv pentru numere întregi nenegative și după cum urmează: $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}

Poate să nu pară evident că recursiunea se termină întotdeauna. Acest lucru rezultă din faptul că, într-un apel recursiv, fie valoarea lui este redusă , fie valoarea este păstrată, dar valoarea este redusă . Aceasta înseamnă că de fiecare dată perechea este redusă din punct de vedere al ordinii lexicografice , ceea ce înseamnă că valoarea va ajunge în cele din urmă la zero: pentru o valoare , există un număr finit de valori posibile (de vreme ce primul apel cu datele a fost realizat cu o anumită valoare și, în plus, dacă valoarea este păstrată, valoarea poate doar să scadă), iar numărul de valori posibile , la rândul său, este de asemenea finit. Cu toate acestea, atunci când scade , valoarea care crește cu este nelimitată și de obicei foarte mare. $m$ $m$ $n$ $(m,\;n)$ $m$ $m$ $n$ $m$ $n$ $m$ $n$ $m$ $m$ $n$

Tabel de valori

Consultați operatorul hyper pentru detalii despre hyper .

$n$ $\|m$	$0$	$unu$	$2$	$3$	$patru$	$5$	$m$
$0$	$unu$	$2$	$3$	$5$	$13$	$65533$	${\mathrm {hiper}}(2,\;m,\;3)-3$
$unu$	$2$	$3$	$5$	$13$	$65533$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))_{{65536}}-3$	${\mathrm {hiper}}(2,\;m,\;4)-3$
$2$	$3$	$patru$	$7$	$29$	$2^{{65536}}-3$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{{\underbrace {2^{{2^ {{ \cdot ^{{\cdot ^{{\cdot ^{2)))))))))))))_{{65536))))-3$	${\mathrm {hiper}}(2,\;m,\;5)-3$
$3$	$patru$	$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 {hiper}}(2,\;m,\;6)-3$
$patru$	$5$	$6$	$unsprezece$	$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$	$\underbrace {2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2))))))))))))_{({\underset {\underbrace {2^ {{ 2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))_{{65536}}}{\vdots }}}}-3$ (total de blocuri ) $n$ $2^{{2^{{\cdot ^{{\cdot ^({\cdot ^{2)))))))))))))}$	${\mathrm {hiper}}(2,\;m,\;n+3)-3$

Funcția inversă

Deoarece funcția crește foarte repede, funcția inversă , notată cu , crește foarte lent. Această funcție este întâlnită în studiul complexității unor algoritmi , de exemplu, un sistem de mulțimi disjunctive sau algoritmul Chazell pentru construirea unui arbore de întindere minim [3] . Când analizăm asimptoticele , putem presupune că pentru toate numerele care apar practic, valoarea acestei funcții este mai mică de cinci, deoarece nu este mai mică de . $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))))$

Utilizare în testele de performanță

Funcția Ackerman, în virtutea definiției sale, are un nivel foarte profund de recursivitate, care poate fi folosit pentru a testa capacitatea compilatorului de a optimiza recursiunea. Yngwie Sundblad [4] a fost primul care a folosit funcția Ackerman pentru aceasta .

Brian Wichman (coautor al benchmark-ului Whetstone ) a luat în considerare acest articol atunci când a scris o serie de articole despre testarea optimizării apelurilor [5] [6] [7] .

De exemplu, un compilator care, atunci când analizează un calcul, este capabil să stocheze valori intermediare, de exemplu, și , poate accelera calculul de sute și mii de ori. De asemenea, evaluarea directă, în loc să se extindă recursiv, va accelera destul de mult calculul. Calculul durează timp liniar . Calculul necesită timp pătratic, deoarece se extinde în O ( ) apeluri imbricate pentru diverse . Timpul de calcul este proporțional cu . $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}$

Valoarea nu poate fi calculată cu o simplă aplicație recursivă într-o perioadă rezonabilă de timp. În schimb, formulele scurte sunt folosite pentru a optimiza apelurile recursive, cum ar fi . $A(4,\,n)$ $A(3,\,n)=8\cdot 2^{n}-3$

Una dintre modalitățile practice de a calcula valorile funcției Ackermann este memorarea rezultatelor intermediare. Compilatorul poate aplica automat această tehnică unei funcții folosind funcții memo [8] [9] de Donald Michie .

Note

↑ Cristian Calude, Solomon Marcus și Ionel Tevy . Primul exemplu de funcție recursivă care nu este recursivă primitivă // Historia Math . : jurnal. - 1979. - Noiembrie ( vol. 6 , nr. 4 ). - P. 380-384 . - doi : 10.1016/0315-0860(79)90024-7 .
↑ Raphael M. Robinson . Recursiune și recursivitate dublă (neopr.) // Buletinul societății matematice americane . - 1948. - T. 54 , nr 10 . - S. 987-993 . - doi : 10.1090/S0002-9904-1948-09121-2 . Arhivat din original pe 7 iunie 2011.
↑ Matematică discretă: algoritmi. Arbori de întindere minim (link nu este disponibil) . Preluat la 13 august 2011. Arhivat din original la 2 iunie 2010. (nedefinit)
↑ Y. Sundblad . Funcția Ackermann. Un studiu teoretic, computațional și manipulativ de formule (engleză) // BIT : jurnal. - 1971. - Vol. 11 . - P. 107-119 . - doi : 10.1007/BF01935330 . (link indisponibil)
↑ Funcția lui Ackermann: Un studiu asupra eficienței procedurilor de apelare (1975). Preluat la 13 august 2011. Arhivat din original la 23 februarie 2012. (nedefinit)
↑ Cum să apelezi la proceduri sau gânduri secundare asupra funcției lui Ackermann (1977). Preluat la 13 august 2011. Arhivat din original la 23 februarie 2012. (nedefinit)
↑ Cele mai recente rezultate de la testul de apelare a procedurii. funcţia lui Ackermann (1982). Preluat la 13 august 2011. Arhivat din original la 23 februarie 2012. (nedefinit)
↑ Michie, Donald Memo functions and machine learning, Nature , nr. 218, pp. 19-22, 1968.
↑ Exemplu: versiunea explicită a funcției memo a funcției lui Ackermann Arhivată 17 iulie 2011 la Wayback Machine implementată în PL/SQL.

Link -uri

Weisstein, Eric W. Ackermann Function (engleză) pe site-ul Wolfram MathWorld .

Cifre mari
Numerele	googol Numărul Shannon Googlelplex Număr înclinat numărul Moser Numărul Graham TREE(3) Numărul Rayo
Funcții	Funcția Ackermann Funcția Veblen Funcțiile Psi ale lui Buchholz tetrare Pentație Hiperoperator Ierarhie în creștere rapidă Ierarhie în creștere lent Ierarhie Hardy
Notații	Notația Steinhaus-Moser Notație cu săgeată Knuth Notație săgeată Conway Notație masivă Bowers