Funkcja Ackermanna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Funkcja Ackermanna jest funkcją matematyczną odkrytą 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łaściwościach podobnych do funkcji Ackermanna (tzn. będąca rekurencyjną i nie pierwotnie rekurencyjną) jest funkcja Sudana.

Definicja[edytuj | edytuj kod]

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


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

Właściwości[edytuj | edytuj kod]

Funkcja Ackermanna jest rekurencyjna.

Schemat dowodu twierdzenia funkcja Ackermanna nie jest pierwotnie rekurencyjna: definiuje się rodzinę funkcji Ackermanna 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ę A (x) = A _x (x). Wynika z tego, że A(x) nie jest pierwotnie rekurencyjna.

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

Dowód przez indukcję:

  • Niech m = 0. Wtedy:
\forall n \in \mathbb{N}: A (0, n) = n + 1 > 0

zgodnie z definicją dla funkcji posiadającej 0 jako pierwszy argument. 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:
\forall n \in \mathbb{N}: A (m, n) > n

pokazujemy poprzez indukcję na argumencie n, że

\forall n \in \mathbb{N}: A(m + 1, n) > n
  • W tym celu niech n = 0. Zgodnie z hipotezą 1 obowiązuje
A(m, 1) > 1\,

i poprzez to

A(m + 1, 0) = A (m, 1) > 1 > 0\,

wedle definicji funkcji dla argumentu n = 0.

  • (Hipoteza 2) Zakładając, że obowiązuje:
\forall n \in \mathbb{N}: A(m + 1, n) > n

pokazujemy, że

\forall n \in \mathbb{N}: A(m + 1, n + 1) > n + 1
  • Ponieważ wedle hipotezy 2 zachodzi: n + 1 < A(m + 1, n + 1), musi obowiązywać:
n + 1 \leq A(m + 1, n)

a następnie zgodnie z hipotezą 1:

A (m + 1, n)  < A(m, A(m + 1, n))\,

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

A(m, A(m + 1, n)) = A(m + 1, n + 1)\,

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

n + 1 \leq A(m + 1, n) < A(m, A(m + 1, n)) = A(m + 1, n + 1)

Tabela wartości[edytuj | edytuj kod]

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

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

Przykłady[edytuj | edytuj kod]

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, na przykład 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, przyczym jedno z nich A(1,1) zostanie spamiętane i wykorzystane w 11 wywołaniu funkcji do bezpośrednigo zwrócenia wyniku. Przy większych n oraz m, zysk jest nawet większy, dla przykładu A(3,3) wymaga 2432 wywołań, a wersja ze spamiętywanie 186 wywołań, zapamiętując w tablicy 154 różne pary (m,n) wraz z wartościami.

Odwrotna funkcja Ackermanna[edytuj | edytuj kod]

Jeśli oznaczymy f(n) = A(n,n). To możemy rozpatrywać również jej odwrotność f^{-1}. Jest to funkcja niesłychanie wolno rosnąca (asymptotycznie wolniej niż logarytm, a nawet logarytm iterowany). W wszystkich wyobrażalnych praktycznych zastosowaniach można uznać tę funkcję za stałą, nie większą, niż 5, ponieważ A(4,4), wynosi około 2^{2^{10^{19729}}}.

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

\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.

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

Linki zewnętrzne[edytuj | edytuj kod]