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 $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:

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	$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	2⁶⁵⁵³⁶ ‒ 3	A(3, 2⁶⁵⁵³⁶ ‒ 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 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, ${{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

↑ 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

[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.)

[1]