Ackermann fonksiyonu normalde A(m, n) olarak tanımlanıyor. Pekala Bu fonksiyonu A(x, x, x…) veya daha fazla eleman ekleyerek ifade edebilir miyiz?

Öncelikle şu sıradan iki değişkenli Ackermann fonksiyonunu (yani ) gözünüzün önüne getirin. Temel seviyede, bu fonksiyonun ne kadar hızlı büyüdüğünden hep bahsedilir. Hani çığ etkisi derler ya, küçük bir kar topu tepeden yuvarlanıp aşağıda kocaman bir çığıa dönüşür. İşte Ackermann fonksiyonunun büyümesi de tam olarak öyle – hatta bundan çok daha deli dolu, adeta füze gibi fırlıyor.

Derken şöyle bir soru akla gelebilir: "Bu canavar fonksiyonu, diyelim ki sadece iki parametreyle değil de, üç, dört, hatta beş parametreli hale getirsek neler olur?" İşte bu noktada işler iyice şenleniyor. Wilhelm Ackermann'ın ilk tanımladığı üç değişkenli sürümden tutun da, daha sonra farklı matematikçilerin önerdiği çok parametreli sürümlere kadar her çeşit tarif mevcut. Alt başlık ekleyeceğim daha rahat okunabilmesi ve algılanabilmesi için.

Ackermann'ın İlk Üç-Değişkenli Tanımı

Bunu bir hikâye gibi düşünelim. Aslında Ackermann'ın 1928'de tanıttığı ilk fonksiyon, üç argümanlıydı: . Bu üçlü tanım, sonradan mütevazı bir "iki değişkenli versiyona" indirgendi. O meşhur, ders kitaplarında gördüğümüz (ama genelde karşımıza iki argümanlı olarak çıkan) sürüm, aslında bu ilk üç değişkenli tarifin biraz sadeleştirilmiş bir türevi yani.

Ackermann'ın üç değişkenli fonksiyonu şöyle bir şeye benziyor:

Tabii buradaki tanımlar, "Ne oluyor ya?" dedirtecek kadar karmaşık gelebilir, ama özetle şu: Üçüncü parametre , fonksiyonun ne kadar agresif bir şekilde (bir bakıma) üst üste işlemleri tekrarlayacağını belirliyor. Bu da sanki bir roketin yakıt katmanına benziyor: halinde roket basit bir işlem yapıyor; büyüdükçe roket katman katman ateşlenip daha da yükseğe (veya daha çılgın hızlara) çıkıyor.

Daha Çok Değişken, Daha Büyük Patlama

Peki, "Buna bir parametre daha katsak?" ya da "Hadi her parametreyi aynı değere eşitleyip yapsak?" soruları akla gelebilir. Evet, katabiliriz. Aslında hem tarihsel hem de çağdaş literatürde, Ackermann gibi hızlı büyüyen fonksiyonların "çok değişkenli" (multi-ary) hâllerini inceleyen çalışmalar var.

Neden yapsınlar peki?

Birincisi, computability (hesaplanabilirlik) teorisi ve karmaşıklık (complexity) analizi açısından, bu fonksiyonların sınırlarını daha iyi görmek istiyoruz.

İkincisi, bu fonksiyonlar hiperoperasyon dizisi gibi yapılarla çok yakın ilişkili. Hiperoperasyon deyince akla sırasıyla toplama, çarpma, üs alma, tetration ve ötesi geliyor. İşte Ackermann fonksiyonu da bu dizinin en üst katmanlarına doğru bir köprü kuruyor.

Sundblad (1971) bu mevzuyu şöyle bir düzenlemiş. Onun tarifinde:

gibi bir ifade kullanıyor. Burada , "-inci hiperoperasyonla 2 ve üzerine çalış" demek. Detayına girdiğinizde bu tarif, Ackermann fonksiyonunun hızlı büyümesini hiperoperasyonlarla ilişkilendiriyor.

Bir de, "Her değişkeni aynı alırsak ne olur?" diye soracaksınız çok yüksek ihtimalle: "Zevkli olur, ama pek bir anlamı var mı?" Aslında anlamı var, çünkü böylece fonksiyonun davranışını simetrik bir şekilde inceleyebiliyorsunuz. Ancak hesapsal karmaşıklık bakımından, "farklı" veya "aynı" değer olsun, yine pek bir fark yok: Her halükârda hızlı, deli dolu bir büyüme söz konusu.

Tek Değişken Görünümüne Çekmek: İterasyon Yaklaşımı

Bir de şöyle bir yaklaşım var: Bazen Ackermann fonksiyonunu, sabit bir alıp, sadece (veya tersi) odaklanmak isteriz. Bu durumda karşımıza iterasyon (tekrarlı uygulama) kavramı çıkıyor. Mesela:

diyor bazı kaynaklar. Yani fonksiyonunu defa iç içe uyguluyoruz ve 1 değerinden başlıyoruz. "Bu kadarı basit görünüyor, hile nerede?" diye sorduğunuzu duyar gibiyim 😂. Hile şu: Bu tanım, "tek-argümanlı" gibi gözükmesine rağmen, aslında "çok-argümanlı" büyümenin özünü iterasyonla gizlice içeri almış oluyor. Zaten Ackermann fonksiyonunu "iterasyonun iterasyonu" (hatta belki de "iterasyonun iterasyonunun iterasyonu") gibi düşünmek mantıklı; meşhur büyüme hiyerarşilerinin veya Grzegorczyk hiyerarşisinin üst katlarına kadar tırmanan bir merdiven gibi.

Uygulamalar, Kıyaslamalar ve "Olmuş da bitmiş" Benzetmeleri

Bilgisayar Bilimleri: Algoritma karmaşıklığını ölçerken bazen "Bu kadar hızlı büyüyen fonksiyonları bile hesaplayabiliyor muyuz?" diye sorgularız. Tabi Ackermann fonksiyonu "tam hesaplanabilir" ama ilkel özyinelemeli (primitive recursive) sınırları aşıyor.^[1] Bu demek değil ki hesaplanamaz; tam tersi, hesaplanır ama primitive recursive fonksiyonların oluşturduğu "konfor alanı"ndan bayağı dışarı taşıyor.

Matematiksel Modelleme: Yüksek derecedeki tekrarlamalı işlemleri modellemek istediğimizde, tıpkı patlayan bir yıldız gibi, bu fonksiyon bize "evrensel, herkesin korktuğu gökdelenler" misali bir büyüme profili verir. Örneğin "Bu fonksiyon 5 parametre de alsa, 10 parametre de alsa, aynı hızla mı büyüyecek?" derseniz, "Daha da hızlı büyüyecek" cevabıyla karşılaşırsınız. Yani elli parametre koyunca ipi iyice koparmış oluyoruz.

Kısacası formunda bir Ackermann yazmak tam anlamıyla "çok katlı roketin" her katını eşdeğer yakıtla doldurmak gibi. Daha fazla parametre ekledikçe, roketin daha da derin uzaylara gitmesi kaçınılmaz.

Ackermann fonksiyonunu daha fazla parametreyle tanımlamak, hem tarihsel olarak zaten var olan (Ackermann'ın ilk üçlü tarifi) hem de matematiksel araştırmalarda çeşitli yollarla önerilen bir yöntem. Ortaya çıkan fonksiyonun büyüme hızı, "uçsuz bucaksız" diyebileceğimiz türden. Her ilave parametre, fonksiyonun kendi kendisini tekrarlama biçiminde yeni bir katman ekliyor.

Matematiksel formüllerle bakıldığında, üç veya daha fazla değişkenli sürümler, genellikle şu tipte özyinelemeli (rekürsif) kural setlerine dayanıyor:

Bu "daha karmaşık biçimde çağrısı", genelde bir alt seviye parametrede veya bir önceki değer üzerinde yine bu fonksiyonun çalıştırılmasıyla gerçekleşir. Her bir ek parametre, sanki yeni bir özyinelemeli döngü ekliyor. Yanbi bir satranç tahtasının boyutlarını arttırdıkça hamle sayısı ve strateji olasılığı nasıl artıyorsa, burada da fonksiyonun karmaşıklığı o ölçüde katlanıyor.

Yani "Daha çok parametre ekleyelim mi?" sorusuna benim cevabım: Tabii ki ekleyebiliriz, ama sonuç tıpkı çığ'ın önüne set çekmeye çalışmak gibi, neredeyse durdurulamaz bir hızda artacaktır.