Funcția Ackermann

În matematică , funcția Ackermann este o funcție $f(x,y,z)$ ${\ displaystyle f (x, y, z)}$ $f (x, y, z)$ al cărui domeniu este setul de seturi de numere naturale și modul în care codominio numerele naturale . Este definit prin recurență după cum urmează:

f(0,0,z)=z

{\ displaystyle f (0,0, z) = z}

{\ displaystyle f (0,0, z) = z}

f(0,y+1,z)=f(0,y,z)+1

{\ displaystyle f (0, y + 1, z) = f (0, y, z) +1}

{\ displaystyle f (0, y + 1, z) = f (0, y, z) +1}

f(1,0,z)=0

{\ displaystyle f (1.0, z) = 0}

{\ displaystyle f (1.0, z) = 0}

f(x+2,0,z)=1

{\ displaystyle f (x + 2.0, z) = 1}

{\ displaystyle f (x + 2.0, z) = 1}

f(x+1,y+1,z)=f(x,[f(x+1,y,z)],z).

{\ displaystyle f (x + 1, y + 1, z) = f (x, [f (x + 1, y, z)], z).}

{\ displaystyle f (x + 1, y + 1, z) = f (x, [f (x + 1, y, z)], z).}

Un caz special este funcția Ackermann cu două argumente $A(m,n)$ ${\ displaystyle A (m, n)}$ ${\ displaystyle A (m, n)}$ , definit după cum urmează:

$A(m,n)={\begin{cases}n+1&{\mbox{se }}m=0\\A(m-1,1)&{\mbox{se }}m>0{\mbox{ e }}n=0\\A(m-1,A(m,n-1))&{\mbox{se }}m>0{\mbox{ e }}n>0.\end{cases}}$ ${\ displaystyle A (m, n) = {\ begin {cases} n + 1 & {\ mbox {se}} m = 0 \\ A (m-1,1) și {\ mbox {se}} m> 0 {\ mbox {e}} n = 0 \\ A (m-1, A (m, n-1)) și {\ mbox {se}} m> 0 {\ mbox {e}} n> 0. \ end {cases}}}$ ${\ displaystyle A (m, n) = {\ begin {cases} n + 1 & {\ mbox {se}} m = 0 \\ A (m-1,1) și {\ mbox {se}} m> 0 {\ mbox {e}} n = 0 \\ A (m-1, A (m, n-1)) și {\ mbox {se}} m> 0 {\ mbox {e}} n> 0. \ end {cases}}}$

Funcția Ackermann este un exemplu de funcție recursivă care nu este recursivă primitivă deoarece crește mai repede decât orice funcție recursivă primitivă.

Valoarea crește foarte rapid chiar și pentru valori foarte mici ale $m$ ${\ displaystyle m}$ $m$ Și $n$ ${\ displaystyle n}$ $n$ . De exemplu, $A(4,2)$ ${\ displaystyle A (4,2)}$ ${\ displaystyle A (4,2)}$ este un număr întreg de 19 729 cifre. ^[1] Pentru comparație, constanta Avogadro are doar 24 de cifre.

Mecanismul de calcul al funcției este extrem de simplu, precum și greu din punct de vedere al calculului. Definiția dată poate fi văzută ca cea a unei familii de funcții atunci când un parametru identificat de prima variabilă variază. Pentru fiecare valoare a parametrului există o funcție care se obține prin iterarea funcției anterioare de mai multe ori identificate de a doua variabilă. Din acest punct de vedere, primele funcții ale familiei sunt funcții familiare, cum ar fi adunarea , multiplicarea și puterea , urmate de tetracție și, ulterior, există funcții din ce în ce mai complexe:

f(0,y,z)=y+z

{\ displaystyle f (0, y, z) = y + z}

{\ displaystyle f (0, y, z) = y + z}

f(1,y,z)=y\times z

{\ displaystyle f (1, y, z) = y \ times z}

{\ displaystyle f (1, y, z) = y \ times z}

(prin iterație

z+z+z+\ldots

{\ displaystyle z + z + z + \ ldots}

{\ displaystyle z + z + z + \ ldots}

pentru

y

{\ displaystyle y}

y

ori)

f(2,y,z)=z^{y}

{\ displaystyle f (2, y, z) = z ^ {y}}

{\ displaystyle f (2, y, z) = z ^ {y}}

(prin iterație

z\times z\times z\times \ldots

{\ displaystyle z \ times z \ times z \ times \ ldots}

{\ displaystyle z \ times z \ times z \ times \ ldots}

pentru

y

{\ displaystyle y}

y

ori)

f(3,y,z)=z^{z^{z^{.^{.^{.}}}}}

{\ displaystyle f (3, y, z) = z ^ {z ^ {z ^ {. ^ {. ^ {.}}}}}}

{\ displaystyle f (3, y, z) = z ^ {z ^ {z ^ {. ^ {. ^ {.}}}}}}

(

y

{\ displaystyle y}

y

ori) (prin iterație

z^{z^{z^{.^{.^{.}}}}}

{\ displaystyle z ^ {z ^ {z ^ {. ^ {. ^ {.}}}}}}

{\ displaystyle z ^ {z ^ {z ^ {. ^ {. ^ {.}}}}}}

pentru

y

{\ displaystyle y}

y

ori și apoi prin iterație

y\times z

{\ displaystyle y \ times z}

{\ displaystyle y \ times z}

și apoi prin iterația de

y+z

{\ displaystyle y + z}

{\ displaystyle y + z}

)

Prin urmare, este o funcție cu o complexitate extrem de mare chiar și pentru valori de intrare simple.

Inversul funcției Ackermann, notat cu $\log ^{\ast }$ ${\ displaystyle \ log ^ {\ ast}}$ ${\ displaystyle \ log ^ {\ ast}}$ sau $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ , apare în unele demonstrații de informatică, cum ar fi algoritmul union-find .