Ackermann Fonksiyonu: Bilgisayar Biliminin "Hızlı Büyüyen" Canavarı

"Bu fonksiyon ne yapıyor?"

Bir öğrenci tahtaya şu tanımı bakar:

$A(m, n) = \begin{cases} n + 1 & \text{eğer } m = 0 \\ A(m-1, 1) & \text{eğer } m > 0 \text{ ve } n = 0 \\ A(m-1, A(m, n-1)) & \text{eğer } m > 0 \text{ ve } n > 0 \end{cases}$

Sade bir rekürsiyon. Üç kural. Ama küçük değerleri hesaplamaya başlayın:

• $A(0, n) = n + 1$. Basit.
• $A(1, n) = n + 2$. Yine basit.
• $A(2, n) = 2n + 3$. Hâlâ basit.
• $A(3, n) = 2^{n+3} - 3$. Şimdi üstel.
• $A(4, n) = 2^{2^{2^{...^{2}}}} - 3$ ($n+3$ kat 2). Süper-üstel.

Şöyle bir somut sayı: $A(4, 2) = 2^{65536} - 3$. Bu, ondalık olarak 19729 basamaklı bir sayı. Evrendeki atom sayısı sadece 80 basamaklı.

$A(5, 5)$? Yazılamayacak kadar büyük. Evrenin tüm bilgisayarlarında saklanamaz.

Bu, Ackermann fonksiyonu. 1928 yılında Wilhelm Ackermann tarafından (Hilbert'in doktora öğrencisi) tanımlandı. Hesaplanabilir ama primitif olmayan rekürsif ilk ünlü örnek.

Tarihsel bağlam — "primitif rekürsiyon" tartışması

1900-1928 arası, Hilbert programı matematiği aksiyomatize etmeye uğraşıyordu. Hilbert ve çevresi (von Neumann, Bernays, Ackermann) rekürsiyon ile tanımlanan fonksiyonların matematiğin tamamını yakaladığını düşünüyordu.

Primitif rekürsiyon: $f(0, n)$ baz, sonra $f(m+1, n)$ önceki değerlerden tanımla. Tüm aritmetik (toplama, çarpma, üst, ...) primitif rekürsiftir.

Hilbert iddiası: "Tüm tam-sayı fonksiyonları primitif rekürsiftir."

Ackermann 1928'de bu iddiayı çürüttü. Yukarıdaki fonksiyon, $f(m+1, n)$ tanımlanırken $f(m+1, n-1)$ ve $f(m, ?)$ kullanılıyor — bu, iç içe rekürsiyondur. Primitif rekürsiyon değildir.

Ackermann, fonksiyonu açıkça inşa etti ve primitif rekürsiyonun büyüme hızından daha hızlı olduğunu ispatladı. Sonuç: hesaplanabilir ama primitif rekürsif olmayan fonksiyonlar vardır.

Bu çürütüş Church-Turing tezine giden yolun açılışıdır. 1936'da Gödel, Church, Turing, Kleene "genel rekürsif fonksiyonlar" çerçevesini geliştirdiler — bunlar Ackermann fonksiyonunu da içerir.

Niçin bu kadar hızlı büyür?

İçeride iç içe rekürsiyon var: $A(m, n)$, $A(m, n-1)$ değerini kendi içine alıyor; sonra bu değer $A(m-1, ...)$'nin argümanı oluyor. Yani her satır rekürsiyon bir önceki satırın çıktısı kadar derinleşiyor.

İç içe rekürsiyon = hyperoperator hiyerarşisi:

• $A(0, n)$: toplam (0-ıncı hyperoperator).
• $A(1, n)$: çarpım benzeri.
• $A(2, n)$: üs benzeri.
• $A(3, n)$: tetration (üst-üs).
• $A(4, n)$: pentation. Vs.

Knuth ok notasyonu: $A(m+2, n)$ kabaca $2 \uparrow^m n$. Yani $A(3, n) \approx 2 \uparrow n = 2^n$, $A(4, n) \approx 2 \uparrow\uparrow n$, ...

Ters Ackermann ve Union-Find

İlginç şekilde, inanılmaz yavaş büyüyen bir fonksiyon var: ters Ackermann fonksiyonu $\alpha(n)$. Tanım: $\alpha(n)$ = en küçük $k$ ki $A(k, k) \geq n$.

$\alpha(n)$ pratik olarak sabittir:

• $\alpha(2) = 2$
• $\alpha(4) = 3$
• $\alpha(2^{2^{2^{...^{2^{65536}}}}}) = 4$

Yani evrendeki herhangi bir mantıklı sayı için $\alpha(n) \leq 4$. Resmi olarak $\alpha(n) \to \infty$ ama "hiç fark etmez".

Bu fonksiyon Union-Find veri yapısının (MST için kullanılan) karmaşıklık analizinde karşımıza çıkar. Tarjan ve van Leeuwen (1984) ispatladı: yol sıkıştırma + rank-by-union Union-Find, $n$ işlemi $O(n \alpha(n))$ zamanda işler. Bu, pratik olarak $O(n)$ demektir.

Yani Ackermann fonksiyonu hızlı büyüyen canavarı dolaylı yoldan bilgisayar bilimine girer: ters versiyonu "pratik sabit" olarak.

Wilhelm Ackermann kim?

Wilhelm Friedrich Ackermann (1896-1962), Alman matematikçi, mantıkçı.

• Doktora: Göttingen, 1924. Danışman: David Hilbert.
• İlk başarısı: Birinci dereceden mantıkta Ackermann seti, kümeler-teorisinin alternatif aksiyomatizasyonu.
• Akademik kariyer: Hayatının çoğunu lise hocası olarak geçirdi. Bunu seçim olarak yapıyordu — üniversite bürokrasisinden uzak durmak istiyordu. Hilbert mahzun olmuştu: "En parlak öğrencim, gymnasium hocası!"
• 1953-61: Münster Üniversitesi'nde fahri profesör.

Ackermann sade, mütevazı bir adamdı. Asla evlenmedi. Hayatın çoğunu mantık üzerine sessizce çalışarak geçirdi. 1962'de Lüdenscheid'da öldü.

İlginç biyografik nokta: Ackermann fonksiyonu onun kariyerinin başında (28 yaşında) buldu. Sonra hayatının kalan 35 yılı birinci dereceden mantık ve küme teorisi üzerine geçti. Tek bir 8-satırlık tanım, onun adını tüm sonraki kuşakların ders kitaplarına yazdırdı.

Diğer "hızlı büyüyen" fonksiyonlar

Ackermann'dan sonra daha hızlı büyüyen fonksiyon aileleri gelişti:

Busy Beaver

Tibor Radó (1962): $n$-durumlu Turing makinelerinin durabilenlerin yazdığı en uzun string. $\Sigma(n)$ fonksiyonu Ackermann'dan çok daha hızlı büyür ve hesaplanamazdır (halting problem).

Goodstein dizileri

Önceki yazımızda gördük. Ackermann hesaplanabilir ama hızlı; Goodstein "hesaplanabilirdir ama Peano aritmetiğinde kanıtlanmaz".

TREE(n)

Friedman'ın TREE fonksiyonu: $\mathrm{TREE}(3)$ Graham sayısından kıyaslanamayacak kadar büyük. $\mathrm{TREE}(n)$ Goodstein'dan daha hızlı.

Rayo sayısı

Mantıksal tanımlanabilir en büyük sayı. Hızlı büyüme yarışının en uç noktası.

Bu yarış matematik mantığının ortaya koyduğu derin bir mesajdır: rekürsiyon türleri arasında bir hiyerarşi var, ve her seviyede daha güçlü bir yöntemle aşılabilir.

Pratik anlamı

Ackermann fonksiyonu doğrudan kullanılmaz. Ama:

1. Hesaplanabilirlik teorisi: primitif olmayan rekürsiyonun ilk örneği.
2. Karmaşıklık analizi: ters Ackermann, Union-Find'da "pratik sabit".
3. Mantık derslerinde: rekürsiyonun farklı türlerini örnekleyen klasik.
4. Compiler testleri: derleyicilerin tail call optimization ve stack depth sınırlarını test etmek için.

Sonuç

Ackermann fonksiyonu, matematik mantığının çarpıcı bir mesajıdır:

• Hesaplanabilir ama primitif rekürsif değil.
• Çok hızlı büyür — küçük argümanlar evren-üstü değerler verir.
• Ters versiyonu çok yavaş büyür — pratik olarak sabit.
• 1928'de tanımlandı, hâlâ ders kitabı zorunluluğu.

Bir sade tanım — 8 satır. Sonra evrenin atom sayısından milyar kez büyük sayılar. Sonra modern bilgisayar bilimi karmaşıklık analizinin kalbi. Matematiğin minimum-aksiyom maksimum-etki ilkesinin uç örneği.

Ackermann mütevazı bir lise hocasıydı. Hayatı boyunca "fonksiyonun arkasındaki adam" değildi — hatta bunu vurgulamaktan kaçındı. Ama bugün her bilgisayar bilimi öğrencisi onun adını ezbere bilir. Sessiz büyüklük.