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

## [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×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.

## [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 | 2n + 3
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 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) 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.

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

(…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

##### Views

- Szócikk
- Vitalap
- Aktuális változat

##### Keresés

##### Más nyelveken

- English
- Česky
- Deutsch
- Español
- Français
- עברית
- 日本語
- Nederlands
- Polski
- Português
- Српски / Srpski
- Türkçe
- Tiếng Việt
- 中文