Ackermann-függvény

A Wikipédiából, a szabad lexikonbó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.

[szerkesztés] 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}$

[szerkesztés] 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.

[szerkesztés] 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	$2 n + 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 Univerzum részecskéinek száma a 200. hatványon. A(5, 2) az A(5, 1) oszlop m = 4 sorában található, és tízes számrendszerben írva nem férne el a fizikai Univerzumban. 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.

Ha megtehetnénk, hogy a mostani Univerzum minden részecskéjét egy csettintéssel egy univerzummá tágítsuk, utána ugyanezt a megjelent univerzumok részecskéivel, és ezt sokszor megtennénk, meghalnánk végelgyengülésben mielőtt a részecskék száma elérné a A(4, 3)-t. Viszont A(5, 1) még ennél a számnál is nagyobb.

[szerkesztés] 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.

[szerkesztés] 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 inverzt 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.

[szerkesztés] 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.

(…a szócikk további része lefordítandó…)

A lap eredeti címe "http://hu.wikipedia.org../../../a/c/k/Ackermann-f%C3%BCggv%C3%A9ny.html"

Kategóriák: Lefordítandó lapok | Számítógéptudomány