Ackermann-függvény

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 ${\displaystyle 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 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:

${\displaystyle 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

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×10¹⁹⁷²⁸, é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 e^x, 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	${\displaystyle n+1}$
1	2	3	4	5	6	${\displaystyle n+2}$
2	3	5	7	9	11	${\displaystyle 2n+3}$
3	5	13	29	61	125	${\displaystyle 8\times {2}^{n}-3}$
4	13	65533	265536 ‒ 3	A(3, 265536 ‒ 3)	A(3, A(4, 3))	${\displaystyle {\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 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) 2⁶⁵⁵³⁶ ‒ 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 mⁿ, ahol m-met önmagával szorozzák meg n-szer. Ha p = 2, az eredmény egy kitevősorozat, ${\displaystyle {{m^{m}}^{{\cdot }^{{\cdot }^{{\cdot }^{m}}}}}}$ n emelettel, vagy m n-szer az m-edik hatványon, másképp írva ⁿm, 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

1. The Ackermann Function A(4, 2). web.archive.org, 2008. február 13. [2008. február 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. november 16.)

További információk

• Weisstein, Eric W.: Ackermann function (angol nyelven). Wolfram MathWorld
• An animated Ackermann function calculator
• Scott Aaronson, Who can name the biggest number? (1999)
• Ackermann function's. Includes a table of some values.
• Hyper-operations: Ackermann's Function and New Arithmetical Operation
• Robert Munafo's Large Numbers describes several variations on the definition of A.
• Gabriel Nivasch, Inverse Ackermann without pain on the inverse Ackermann function.
• Raimund Seidel, Understanding the inverse Ackermann function (PDF presentation).
• The Ackermann function written in different programming languages, (on Rosetta Code)
• Ackermann's Function( 2009-10-24) – Some study and programming by Harry J. Smith.

• Informatikai portál • összefoglaló, színes tartalomajánló lap