Ackermann-függvény

A Wikipédiából, a szabad enciklopédiából

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 : \mathbb{N}\times \mathbb{N} \to \mathbb{N}.

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 több jegy kell a felírásához, mint ahány részecske az univerzumban van.

Definíció[szerkesztés | forrásszöveg szerkesztése]

A függvényt rekurzívan definiáljuk az m és n természetes számokra az alábbi módon:

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

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

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 → nm = 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'(nn) 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[szerkesztés | forrásszöveg szerkesztése]

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'(mn)
m\n 0 1 2 3 4 n
0 1 2 3 4 5 n + 1
1 2 3 4 5 6 n + 2
2 3 5 7 9 11 2n + 3
3 5 13 29 61 125 8 \times {2}^{n} - 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\mbox{ + 3 kettes}\end{matrix}
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 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Mivel a fentebb tárgyalt  f (n) = A'(nn) 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[szerkesztés | forrásszöveg szerkesztése]

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'(mnp) 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, {{m^m}^{{\cdot}^{{\cdot}^{{\cdot}^m}}}} 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.

További információk[szerkesztés | forrásszöveg szerkesztése]