Funkcja Ackermanna

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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 rekurencyjna i nie pierwotnie rekurencyjna) jest funkcja Sudana.

[edytuj] Definicja

Matematyczna definicja funkcji opisana jest wzorem:

$\psi(m,n) = \begin{cases}n+1 & \mbox{gdy } m=0 \\ \psi(m-1,1) & \mbox{gdy } n=0 \\ \psi(m-1, \psi(m,n-1)) & \mbox{w innych przypadkach} \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.(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\mbox{ + 3 razy}\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

Poniżej znajduje się przykład kodu programu wykorzystującego funkcję Ackermanna, napisanego w języku Ada.

with Ada.Command_Line; use Ada.Command_Line;
with Gnat.Io; use Gnat.Io;

procedure Ackermann is
   function ack (x : in integer; y: in integer) return integer is
       begin
           if (x = 0) then
               return y + 1;
           elsif (y = 0) then
               return ack(x-1,1);
           else
               return ack(x-1,ack(x,y-1));
           end if;
       end ack;
   x,y,a : integer;
begin
   if (Argument_Count = 2) then
       x := Integer'Value (Argument(1));
       y := Integer'Value (Argument(2));
   elsif (Argument_Count = 1) then
       x := 3;
       y := Integer'Value (Argument(1));
   else
       x := 3;
       y := 3;
   end if;
   a := ack (x,y);
   Put ("Ack (");
   Put (x);
   Put (",");
   Put (y);
   Put (") = ");
   Put (a);
   New_Line;
end Ackermann;