Funkcja Ackermanna.html

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 nadaje się do testowania zdolności kompilatorów do optymalizacji kodu wynikowego. W jej przypadku dobra optymalizacja może oznaczać skrócenie czasu wykonywania programu o trzy lub cztery rzędy wielkości.

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

edytuj Definicja

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

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

edytuj Właściwości

Bardzo łatwo jest pokazać, że funkcja Ackermanna jest rekurencyjna. Dużo ciekawszy jest jednak dowód, że nie jest ona pierwotnie rekurencyjna.

Można go zarysować następująco: Definiujemy najpierw rodzinę funkcji Ackermanna $ψ m (n) = ψ(m, n)$ (zauważmy, że każda z tych funkcji jest pierwotnie rekurencyjna). Pokazujemy, że każda funkcja pierwotnie rekurencyjna jest majoryzowana przez pewną funkcję Ackermanna. Następnie dowodzimy, że wszystkie (jednoargumentowe) funkcje Ackermanna będą z kolei majoryzowane przez funkcję $ψ(x) = ψ x (x)$ . Wynika z tego jasno, że $ψ(x)$ nie może być pierwotnie rekurencyjna.

edytuj Tabela wartości

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\cdot(n + 3)-3$
3	5	13	29	61	125	$2 (n + 3) - 3$
4	13	65533	2⁶⁵⁵³⁶ − 3	$ψ$ (3, 2⁶⁵⁵³⁶ − 3)	$ψ$ (3, $ψ$ (4, 3))	$\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n+3 \ dw \acute o jek\end{matrix}$
5	65533	$ψ$ (4, 65533)	$ψ$ (4, $ψ$ (5, 1))	$ψ$ (4, $ψ$ (5, 2))	$ψ$ (4, $ψ$ (5, 3))
6	$ψ$ (5, 1)	$ψ$ (5, $ψ$ (5, 1))	$ψ$ (5, $ψ$ (6, 1))	$ψ$ (5, $ψ$ (6, 2))	$ψ$ (5, $ψ$ (6, 3))

Wartość $ψ$ (4,2) jest większe niż liczba cząsteczek we wszechświecie podniesiona do dwusetnej potęgi.

edytuj Przykład

Pseudokod algorytmu obliczającego funkcję Ackermanna:

Ackermann(m,n):
    if m==0 then return n + 1
    if m>0 and n==0 then return Ackermann(m - 1,1)
    if m>0 and n>0 then return Ackermann(m - 1,Ackermann(m,n - 1))

edytuj Linki zewnętrzne

http://mathworld.wolfram.com/AckermannFunction.html