Funkcja Ackermanna
Z Wikipedii
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.
Spis treści |
[edytuj] Definicja
Matematyczna definicja funkcji opisana jest wzorem 
:
[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 |  |
| 3 | 5 | 13 | 29 | 61 | 125 | 2(n + 3) − 3 |
| 4 | 13 | 65533 | 265536 − 3 | ψ(3, 265536 − 3) | ψ(3, ψ(4, 3)) |  |
| 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
