Funkcja Ackermanna

Funkcja Ackermanna – funkcja matematyczna odkryta przez Wilhelma Ackermanna w 1928 roku. Cechą charakterystyczną tej dwuargumentowej funkcji jest jej nadzwyczaj szybki wzrost. Funkcja Ackermanna jest prostym przykładem funkcji rekurencyjnej, niebędącej funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp.

Funkcja Ackermanna często jest używana do testowania jakości optymalizacji kompilatorów – stosunki czasu wykonania pomiędzy różnymi kompilatorami tego samego języka czasami sięgają tysiąca. Jakość kodu generowana dla tego typu funkcji jest szczególnie ważna w językach funkcyjnych, gdzie używa się rekursji.

Inną funkcją o własnościach podobnych do funkcji Ackermanna (tzn. będąca rekurencyjną i nie pierwotnie rekurencyjną) jest funkcja Sudana.

Definicja

Matematyczna definicja funkcji opisana jest wzorem ${\displaystyle (m,n\in \mathbb {N} ){:}}$

${\displaystyle A(m,n)={\begin{cases}n+1&{\text{gdy }}\;m=0\\A(m-1,1)&{\text{gdy }}\;m>0\ \ {\text{ i }}\;n=0\\A(m-1,A(m,n-1))&{\text{gdy }}\;m>0\ \ {\text{ i }}\;n>0\end{cases}}}$

Własności

Funkcja Ackermanna jest rekurencyjna.

Schemat dowodu twierdzenia funkcja Ackermanna nie jest pierwotnie rekurencyjna: definiuje się rodzinę funkcji Ackermanna ${\displaystyle A_{m}(n)=A(m,n)}$ (każda z tych funkcji jest pierwotnie rekurencyjna). Z tego wynika, że każda funkcja pierwotnie rekurencyjna jest majoryzowana przez pewną funkcję Ackermanna. Następnie dowodzi się, że wszystkie jednoargumentowe funkcje Ackermanna będą z kolei majoryzowane przez funkcję ${\displaystyle A(x)=A_{x}(x).}$ Wynika z tego, że ${\displaystyle A(x)}$ nie jest pierwotnie rekurencyjna.

• ${\displaystyle \forall m,n\in \mathbb {N} :A(m,n)>n}$

Dowód przez indukcję:

• Niech m = 0. Wtedy:

${\displaystyle \forall n\in \mathbb {N} :A(0,n)=n+1>0}$

zgodnie z definicją dla funkcji posiadającej 0 jako pierwszy argument. ${\displaystyle n+1}$ z kolei jest zawsze większe od 0, ponieważ już w przypadku n = 0, n + 1 = 0 + 1 = 1.

• (Hipoteza 1) Zakładając, że obowiązuje:

${\displaystyle \forall n\in \mathbb {N} :A(m,n)>n}$

pokazujemy poprzez indukcję na argumencie n, że

${\displaystyle \forall n\in \mathbb {N} :A(m+1,n)>n}$

• W tym celu niech n = 0. Zgodnie z hipotezą 1 obowiązuje

${\displaystyle A(m,1)>1}$

i poprzez to

${\displaystyle A(m+1,0)=A(m,1)>1>0}$

wedle definicji funkcji dla argumentu n = 0.

• (Hipoteza 2) Zakładając, że obowiązuje:

${\displaystyle \forall n\in \mathbb {N} :A(m+1,n)>n}$

pokazujemy, że

${\displaystyle \forall n\in \mathbb {N} :A(m+1,n+1)>n+1}$

• Ponieważ wedle hipotezy 2 zachodzi: ${\displaystyle n+1<A(m+1,n+1),}$ musi obowiązywać:

${\displaystyle n+1\leqslant A(m+1,n)}$

a następnie zgodnie z hipotezą 1:

${\displaystyle A(m+1,n)<A(m,A(m+1,n))}$

oraz wedle definicji funkcji dla argumentów różnych od 0:

${\displaystyle A(m,A(m+1,n))=A(m+1,n+1)}$

Łącząc te trzy relacje otrzymujemy dowód twierdzenia:

${\displaystyle n+1\leqslant A(m+1,n)<A(m,A(m+1,n))=A(m+1,n+1)}$

Tabela wartości

m\n	0	1	2	3	4	n
0	1	2	3	4	5	${\displaystyle n+1}$
1	2	3	4	5	6	${\displaystyle 2+(n+3)-3}$
2	3	5	7	9	11	${\displaystyle 2*(n+3)-3}$
3	5	13	29	61	125	${\displaystyle 2^{(n+3)}-3}$
4	13	65533	265536 – 3	${\displaystyle A}$(3, 265536 – 3)	${\displaystyle A}$(3, ${\displaystyle A}$(4, 3))	${\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n+3\ {\text{dwójek}}\end{matrix}}}$
5	65533	${\displaystyle A}$(4, 65533)	${\displaystyle A}$(4, ${\displaystyle A}$(5, 1))	${\displaystyle A}$(4, ${\displaystyle A}$(5, 2))	${\displaystyle A}$(4, ${\displaystyle A}$(5, 3))	${\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}$
6	${\displaystyle A}$(5, 1)	${\displaystyle A}$(5, ${\displaystyle A}$(5, 1))	${\displaystyle A}$(5, ${\displaystyle A}$(6, 1))	${\displaystyle A}$(5, ${\displaystyle A}$(6, 2))	${\displaystyle A}$(5, ${\displaystyle A}$(6, 3))	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow (n+3)-3}$

Wartość ${\displaystyle A}$(4,2) jest dużo większa niż liczba cząsteczek w obserwowalnym wszechświecie podniesiona do dwusetnej potęgi.

Przykłady

Pseudokod (oraz kod w języku Python) algorytmu obliczającego funkcję Ackermanna:

def Ack(m, n):
   if m==0: return n+1
   if m>0 and n==0: return Ack(m-1, 1)
   if m>0 and n>0: return Ack(m-1, Ack(m, n-1))

Kod metody obliczającej funkcję w przykładowym języku funkcyjnym, np. Erlangu:

ack(0,N) -> N+1;
  ack(M,0) -> ack(M-1, 1);
  ack(M,N) -> ack(M-1, ack(M, N-1)).

Trudność przy obliczeniach funkcji Ackermanna leży głównie w złożoności wywołań rekurencyjnych, które łatwo mogą doprowadzić do przepełnienia stosu (ang. stack overflow). Podczas wykonywania obliczenia dochodzi wielokrotnie do wywołań funkcji z identycznymi argumentami. W poniższym przykładzie między innymi A(1, 1), A(1, 0), A(0, 2) zostają wywołane dwukrotnie. Odpowiednia implementacja funkcji może wykorzystać powtarzające się instrukcje do znacznego skrócenia procesu obliczania. Przykładowo wartość A(2, 0) jest równa 3, co jest widoczne w wierszu 6. Podobnie wartość A(1, 2) wynosi 4, co daje się odczytać w przedostatnim wierszu. Oprócz tego wartość funkcji wywołanej z argumentami (2, 1) odpowiada wartości funkcji wywołanej z argumentami (1, 3) lub (0, 4). Różnica polega na tym, że ostatnia kombinacja argumentów może zostać obliczona w czasie krótszym (1 wywołanie funkcji) niż druga (8 wywołań funkcji) lub pierwsza (14 wywołań).

A(2, 1) = A(1, A(2, 0))
        = A(1, A(1, 1))
        = A(1, A(0, A(1, 0)))
        = A(1, A(0, A(0, 1)))
        = A(1, A(0, 2))
        = A(1, 3)
        = A(0, A(1, 2))
        = A(0, A(0, A(1, 1)))
        = A(0, A(0, A(0, A(1, 0))))
        = A(0, A(0, A(0, A(0, 1))))
        = A(0, A(0, A(0, 2)))
        = A(0, A(0, 3))
        = A(0, 4)
        = 5

Języki programowania i kompilatory często stosują tzw. optymalizację wywołań ogonowych, które ułatwiają, przyśpieszają obliczenia funkcji rekurencyjnych podobnych do funkcji Ackermana, i używają znacznie mniej pamięci na stosie.

Inną metodą stosowaną przez pewne kompilatory i języki programowania, jest tzw. spamiętywanie (tablicowanie, memoizacja, forma pamięci podręcznej) wartości funkcji – raz obliczona wartość funkcji A(m, n), jest zapamiętywana w specjalnej tablicy, którą można oznaczyć na przykład przez A[m, n]; przy następnych wywołaniach zamiast wykonywać całość obliczeń z nią związanych odczytuje się wcześniej obliczony wynik bezpośrednio z tablicy w jednym kroku. Przykład w języku Python:

Ack_tab = {}
def Ack(m, n):
   if (m, n) in Ack_tab:
      return Ack_tab[(m, n)]
   else:
     if m==0: r = n + 1
     if m>0 and n==0: r = Ack(m-1, 1)
     if m>0 and n>0: r = Ack(m-1, Ack(m, n-1))
     Ack_tab[(m, n)] = r
     return r

albo:

def ack(m, n, cache={}):
    if (m, n) in cache:
        return cache[(m, n)]
    elif m==0:
        cache[(m, n)] = n + 1
    elif m>0 and n==0:
        cache[(m,n)] = ack(m-1, 1, cache)
    elif m>0 and n>0:
        cache[(m, n)] = ack(m-1, ack(m, n-1, cache), cache)
    return cache[(m,n)]

W porównaniu do poprzedniego przykładu (14 wywołań), ta wersja wykona 10 wywołań rekurencyjnych, przy czym jedno z nich – A(1,1) zostanie spamiętane i wykorzystane w 11 wywołaniu funkcji do bezpośredniego zwrócenia wyniku. Przy większych n oraz m zysk jest również większy, dla przykładu A(3,3) wymaga 2432 wywołań, a wersja ze spamiętywaniem 186 wywołań, zapamiętując w tablicy 154 różne pary (m, n) wraz z odpowiadającymi im wartościami.

Odwrotna funkcja Ackermanna

Jeśli oznaczymy ${\displaystyle f(n)=A(n,n),}$ to możemy rozpatrywać również jej odwrotność ${\displaystyle f^{-1}.}$ Jest to funkcja niesłychanie wolno rosnąca (asymptotycznie wolniej niż logarytm, a nawet logarytm iterowany). We wszystkich wyobrażalnych praktycznych zastosowaniach można uznać tę funkcję za stałą, nie większą niż 5, ponieważ ${\displaystyle A(4,4)}$ wynosi około ${\displaystyle 2^{2^{10^{19729}}}.}$ Używając funkcji ${\displaystyle f(n)=A(n,n),}$ można wyznaczyć, że tempo wzrostu w szybko rosnącej hierarchii można zapisać jako: ${\displaystyle f(n)\approx f_{\omega }(n).}$

Definiuje się również dwuargumentową odwrotność funkcji Ackermanna:

${\displaystyle \alpha (m,n)=\min\{i\geqslant 1:A(i,\lfloor m/n\rfloor )\geqslant \log _{2}n\}.}$

Pojawia się ona czasami przy badaniu złożoności obliczeniowej (np. algorytm Union-Find).

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Ackermann Function, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
• Ackermann function (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].