Az Ackermann-függvény egy, a matematikai logikában definiált, de újabban a számítógéptudomány és a kombinatorika által is használt függvény. Egyszerű példa olyan rekurzív függvényre, ami nem primitív rekurzív. A függvény kétváltozós, mindkét változó természetes szám, az értéke pedig egy természetes szám. Azaz .
A függvény nagyon gyorsan növekszik, így már kis helyeken is hatalmas értékeket vesz fel. A (4,3) argumentum esetén a függvény értéke akkora, hogy tízes számrendszerben 19729 számjegyre van szükség a felírásához.[1]
Definíció
A függvényt rekurzívan definiáljuk az m és n természetes számokra az alábbi módon:
Tulajdonságok
Az alábbi rekurzív hívást tartalmazó kód segítségével könnyen írhatunk programot a függvény kiszámítására:
function ack(m, n)
if m = 0
return n+1
else if n = 0
return ack(m-1, 1)
else
return ack(m-1, ack(m, n-1))
Egy másik lehetséges kiszámítás:
function ack(m, n)
while m ≠ 0
if n = 0
n := 1
else
n := ack(m, n-1)
m := m – 1
return n+1
Haskell nyelven tömörebb definíciót kapunk:
ack 0 n = n + 1
ack m 0 = ack (m – 1) 1
ack m n = ack (m – 1) (ack m (n – 1))
Meglepő lehet, hogy ezek a függvények mindig adnak vissza értéket. Ez azért van, mert minden lépésben vagy n csökken, vagy n nő és m csökken. Mindig amikor n eléri a 0-t, m-nek is csökkennie kell, ezért ez is eléri a nullát. Fontos azonban megjegyezni, hogy nincs felső határa annak, hogy n mennyire nőhet – sokszor nagyon nagyra.
Az Ackermann-függvényt nemrekurzívan is kifejezhetjük a Conway-féle nyílláncolat segítségével:
- A(m, n) = (2 → (n+3) → (m ‒ 2)) ‒ 3 ahol m > 2
ebből
- 2 → n → m = A(m+2,n-3) + 3 ahol n>2
(n=1 és n=2 megfelelne A(m,‒2) = ‒1 -nek és A(m,‒1) = 1, -nek, amit logikusan hozzávehetünk).
Vagy hiper operátorral:
- A(m, n) = hyper(2, m, n + 3) ‒ 3.
Ha m-nek kis értékeket adunk, például 1-et, 2-t vagy 3-at, az Ackermann-függvény viszonylag lassan növekszik n-hez képest (legfeljebb exponenciálisan). Azonban m ≥ 4-re már sokkal gyorsabban nő, még A(4, 2) is körülbelül 2×1019728, és A(4, 3) tízes számrendszerbeli kifejtéséhez nem lenne elég a fizikai univerzum.
Ha definiáljuk az f (n) = A(n, n) függvényt, ami egyszerre növeli m-et és n-t, akkor kapunk egy egyváltozós függvényt, ami messze maga mögött hagyja a többi primitív rekurzív függvényt, köztük a nagyon gyorsan növekvőket is, például az ex, függvény vagy a faktoriálist, multi- és szuperfaktoriális függvényeket és még a Knuth-nyilakat használó függvényeket (kivéve amik indexelt felfelé nyilat használnak).
Ezt az extrém növekedést kihasználhatjuk annak megmutatására, hogy f, amit szemmel láthatóan egy olyan végtelen memóriájú gép tud kiszámolni, mint a Turing-gép, tehát rekurzív, gyorsabban nő, mint bármilyen primitív rekurzív függvény, tehát éppen ezért nem az. Az Ackermann-függvény algoritmusanalízisbeli alkalmazásaival – amiket később tárgyalunk – kombinálva ez megcáfolja azt az elméletet, hogy minden hasznos vagy egyszerű függvény primitív rekurzív (de ez nem a gondolatsor vége: a Beaver-függvények bármilyen rekurzív függvénynél gyorsabban nőnek).
Abból a szempontból érdekes még az Ackermann-függvény, hogy az egyetlen aritmetikai operátor, amit használ, az 1 hozzáadása és kivonása. A tulajdonságai csupán a határok nélküli rekurzió erejéből származnak. Ez magában foglalja azt is, hogy futásideje legalább arányos (de lehet jobban növő is) a kimenetével, éppen ezért irdatlanul nagy. Valójában a legtöbb esetben a futásidő jóval nagyobb a kimenetnél, lásd lentebb.
A függvényértékek táblázata
Az Ackermann-függvény kiszámítását egy végtelen táblázattal is be lehet mutatni. A természetes számokat elhelyezzük a felső sorban. Hogy egy cella értékét meghatározzuk, vegyük a közvetlenül balra esőt, utána az előző sorban a megfelelőt, aminek hollétét az elsőként vett szám adja meg. Ha balra nincs szám, egyszerűen nézzük meg az előző sor 1-es oszlopát. Itt látható a táblázat kis bal felső részlete:
A'(m, n)
m\n
|
0
|
1
|
2
|
3
|
4
|
n
|
0
|
1 |
2 |
3 |
4 |
5 |
|
1
|
2 |
3 |
4 |
5 |
6 |
|
2
|
3 |
5 |
7 |
9 |
11 |
|
3
|
5 |
13 |
29 |
61 |
125 |
|
4
|
13 |
65533
|
265536 ‒ 3
|
A(3, 265536 ‒ 3)
|
A(3, A(4, 3))
|
|
5
|
65533 |
A(4, 65533) |
A(4, A(5, 1))
|
A(4, A(5, 2)) |
A(4, A(5, 3)) |
A(4, A(5, n-1))
|
6
|
A(5, 1) |
A(5, A(5, 1))
|
A(5, A(6, 1))
|
A(5, A(6, 2)) |
A(5, A(6, 3)) |
A(5, A(6, n-1))
|
A(4, 2) nagyobb, mint az Ismert Univerzum részecskéinek száma a 200. hatványon. A 4. sor és az 1. oszlop után az értékeket kivihetetlen bármilyen szabályos jelöléssel leírni magán az Ackermann-függvényen kívül – tízes számrendszerben vagy akár kisebb m számú oszlopokra hivatkozva is lehetetlen leírni. Könnyen belátható, hogy nagyobb számpárok esetében nincsenek "kisszám-szigetek", vagyis olyan kitüntetett számpárok, melyek kezelhetően kicsi eredményt adnak.
Magyarázat
Hogy láthassuk, hogyan nő ilyen gyorsan az Ackermann-függvény, segít, ha felbontunk néhány egyszerű kifejezést az eredeti definíció szabályai szerint. Például kiértékelhetjük A(1, 2)-t a következő módon:
A(1, 2) = A(0, A(1,1))
= A(0, A(0, A(1,0)))
= A(0, A(0, A(0,1)))
= A(0, A(0, 2))
= A(0, 3)
= 4
Most próbáljuk meg ezt a bonyolultabb A(4, 3)-mal, az első olyannal, ami viszonylag kis n-nel sem írható le a Világegyetemben tízes számrendszerben:
A(4, 3) = A(3, A(4, 2))
= A(3, A(3, A(4, 1)))
= A(3, A(3, A(3, A(4, 0))))
= A(3, A(3, A(3, A(3, 1))))
= A(3, A(3, A(3, A(2, A(3, 0)))))
= A(3, A(3, A(3, A(2, A(2, 1)))))
= A(3, A(3, A(3, A(2, A(1, A(2, 0))))))
= A(3, A(3, A(3, A(2, A(1, A(1, 1))))))
= A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))
= A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))
= A(3, A(3, A(3, A(2, A(1, A(0, 2))))))
= A(3, A(3, A(3, A(2, A(1, 3)))))
= A(3, A(3, A(3, A(2, A(0, A(1, 2))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))
= A(3, A(3, A(3, A(2, A(0, A(0, 3)))))
= A(3, A(3, A(3, A(2, A(0, 4)))))
= A(3, A(3, A(3, A(2, 5))))
= …
= A(3, A(3, A(3, 13)))
= …
= A(3, A(3, 65533))
= …
Itt megállhatunk, mert A(3, 65533) 265536 ‒ 3-t ad vissza, egy olyan számot, ami jóval nagyobb, mint az Univerzum atomjainak száma. Ezután ez a szám 2 hatványaként emelkedik a végső eredmény eléréséig.
Inverz
Mivel a fentebb tárgyalt f (n) = A(n, n) függvény nagyon gyorsan tart végtelenhez, inverze nagyon lassan. Mivel a rekurzióelméletben csak természetes szám értékű függvényeket engedünk meg, szokás az inverzet a következőképpen definiálni: α(n) a legkisebb olyan k érték, amire A(k,k)≥n. Mivel A(n,n) minden primitív rekurzív függvénynél gyorsabban tart végtelenhez, α(n) minden (végtelenhez tartó) primitív rekurzív függvénynél lassabban tart végtelenhez. Valójában α(n) kevesebb 5-nél minden elképzelhető nagyságú bemeneti n-re, mivel A(4, 4) kettes számrendszerben nem jegyezhető le az Univerzumban.
Az Ackermann-függvény inverze váratlanul megjelent a matematika más ágaiban is. Elsőként Robert Endre Tarjan mutatta meg 1975-ben, hogy a feszítő fák konstruálásához használt úttömörítés algoritmus lépésszáma konstans szorzó erejéig α(n)-nel becsülhető. Ennél is meglepőbb a Davenport–Schinzel-probléma megoldása volt (Sergiu Hart és Micha Sharir, 1986). Ez újabban sok alkalmazást kapott a geometriai algoritmusok elméletében. Persze, a gyakorlati alkalmazásokban α(n)-t konstansnak tekinthetjük.
Története
Az 1920-as években David Hilbert felvetései hatására többen érdemesnek tartották, hogy a számelméleti függvények kiszámíthatóságával foglalkozzanak. Hilbert matematikáról alkotott képében lényeges szerepet játszottak azok az eljárások, melyek minden körülmények között véges lépésben és csak az aritmetika legegyszerűbb tényeinek felhasználásával igazolják a formális matematikai kijelentések bizonyítható voltát. Egy idő után azonban kétségessé vált, hogy minden valamilyen értelemben kiszámítható aritmetikai függvény a Hilbert által megkövetelt végességi kritériumok alapján tényleg kiszámítható-e. Ezek a kutatások vezettek a rekurzív és primitív rekurzív függvény fogalmának megalkotásához és az ezen fogalmak különbözőségét igazoló nevezetes függvényekhez, mint például az Ackermann-függvény felfedezéséhez.
Az első ilyen példát Hilbert egyik tanítványa Gabriel Sudan román matematikus adta 1927-ben. Eredménye nem vált közismertté, feltehetőleg azért, mert egy kevéssé olvasott román matematikai folyóiratban közölte publikációját. Tőle függetlenül állt elő Wilhelm Ackermann (aki szintén Hilbert tanítványa, sőt később munkatársa volt) 1928-ban a maga rekurzív, de nem primitív rekurzív függvényével. Később Raphael Robinson és Péter Rózsa is egyszerűsítette a függvény konstrukcióját. Péter Rózsa egyszerűsített verzióját Ackermann-Péter függvénynek nevezik.
Ackermann eredetileg az A(m, n, p) háromváltozós függvénnyel foglalkozott, mely az m-nek n alapú, p szeres iterált hatványozása lenne ill. a Conway-féle nyílláncolat alkalmazásával egyszerűbben írva m → n → p. Ha p = 1, akkor az eredménye mn, ahol m-met önmagával szorozzák meg n-szer. Ha p = 2, az eredmény egy kitevősorozat, n emelettel, vagy m n-szer az m-edik hatványon, másképp írva nm, m-nek n-nel való tetrációja. Ezt a végtelenségig általánosíthatjuk, ahogy p egyre nő.
Ackermann bebizonyította, hogy A rekurzív függvény, egy függvény, amit egy végtelen memóriával rendelkező számítógép ki tud számítani, de nem primitív rekurzív függvény, melyek esetén a gép csak egyszerű iteratív műveleteket végez és biztosan véges lépésben leáll, mint például az összeadásnál vagy a faktoriális képzésnél.
Hilbert A végtelenről című cikkében felhasználta azt a tényt, hogy az Ackermann-függvény a mondott tulajdonságú, de nem bizonyította azt. Az igazolás Ackermann A valós számok hilberti konstrukciójáról című munkájában jelent meg. Az A végtelenről Hilbertnek a matematika alapjaival foglalkozó egyik legnagyobb jelentőségű munkája, melyben a transzfinit számok elméletét a Hilbert-féle finit (véges) módszerek segítségével alapozta meg. Később ez a finit elv alkotta a Hilbert-program ideológiai alapját, vagyis, hogy a formális matematikai elméletek konzisztencia és függetlenségi vizsgálatait a legmegbízhatóbb módon, bizonyos fajta véges aritmetikai eszközökkel végezhetjük el. Ez a tanulmány irányította rá Kurt Gödel figyelmét a nemteljességgel, a kiválasztási axiómával és a kontinuumhipotézissel kapcsolatos vizsgálatokra.
Jegyzetek