Yazan : Şadi Evren ŞEKER
Ackermann Fonksiyonu, hesaplama teorisinde geçen ve bir özyineli fonskiyon (recursive function) örneğidir. İlk ilkel özyineli olmayan fonksiyon örneği olması açısından ilginçtir. Fonksiyonun tanımı aşağıdaki şekilde yapılabilir:
Yukarıdaki tanımı daha iyi anlayabilmek için örnek bir soru çözelim.
A(3,1) değeri için x=3 ve y=1 olarak verilmiştir. Bu durumda yukarıdaki koşullardan 3. duruma düşer ve
A(3,1) = A(2, A(3,0))olarak açılır. İşlemi devam ettirelim ve A(3,0) değerini açalım:
A(3,0) = A(2,1)
A(2,1) = A(1,A(2,0))
A(2,0) = 3
A(2,1) = A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,A(1,1))
A(1,1) = A(0,A(1,0))
A(1,0) = 1+1 = 2 , olarak bulunur. Şimdi fonksiyonlarımızı toplayarak yukarı doğru geri dönelim.
A(0,2) = 3
A(1,1) = 3
A(0,3) = 4
A(1,3) = A(0,4)
A(1,3) = 5
A(2,1) = 5
A(3,0) = 5
A(3,1) = A(2,5) olarak bulunmuş olur ve bu noktadan tekrar fonksiyonlarımızı açmamız gerekir.
A(2,5) = A(1,A(2,4))
A(2,4) = A(1,A(2,3))
A(2,3) = A(1,A(2,2))
A(2,2) = A(1, A(2,1))
A(2,1) = A(1,A(2,0))
A(2,0) =3 , bu değeri daha önce hesaplamıştık , d inamik programlama yapabiliriz (dynamic programming)
A(2,1) = A(1,3)
A(1,3) = 5 , daha önce hesaplanmıştı
A(2,1) = 5
A(2,2) = A(1,5)
A(1,5) = A(0,A(1,4))
A(1,4) = A(0,A(1,3))
A(1,4) = A(0,5) , daha önce A(1,3) hesaplamıştık
A(1,4) = 6
A(1,5) = A(0,6)
A(1,5) = 7, o halde
A(2,2) = 7
A(2,3) = A(1,7)
A(1,7) = A(0,A(1,6))
A(1,6) = A(0,A(1,5)) , A(1,5) de daha önce hesaplandı
A(1,6) = A(0, 7)
A(1,6) = 8
A(1,7) = A(0,8)
A(1,7) = 9
A(2,3) = 9 olarak bulunmuş olur.
A(2,4) = A(1,A(2,3))
A(2,4) = A(1,9)
A(1,9) = A(0,A(1,8))
A(1,8) = A(0,A(1,7))
A(1,8) = A(0,9)
A(1,8) = 10
A(1,9) = A(0,10)
A(1,9) = 11
A(2,4) = 11
A(2,5) = A(1,A(2,4))
A(2,5) = A(1,11)
A(1,11) = A(0,A(1,10))
A(1,10) = A(0,A(1,9))
A(1,9) = 11
A(1,10 ) = A(0,11)
A(1,10) = 12
A(1,11) = A(0,12)
A(1,11) = 13
A(2,5) = 13
A(3,1) = 13 olarak bulunmuş olur.
Yukarıdaki denklemlerin ortak bir özelliği bulunmaktadır. Ackermann fonksiyonu görüldüğü üzere özyineli bir fonksiyondur (Recursive) bu durumda denklemi aşağıdaki şekilde açmamız mümkündür:
| xy | 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 | 6 |
Yukarıdaki tabloda görüldüğü üzere, A(0,y) için formül zaten tanımdan y+1 olarak verilmişti, Bir satır daha ilerlettiğimiz zaman, A(1,y) için formülü y+2 olarak buluyoruz.
A(1,y) = y+2 olarak yazılabilir.
Sebebi ise
A(1,y) = A(0,A(1,y-1))
A(1,y-1) = A(0,A(1,y-2))
… , y adet adım sonra
A(1,y-y) = A(1,0) = A(0,1) = 1+1 = 2
yukarıdaki son adıma gelene kadar y adım geçilmiştir, ve her adımda A(0,k) şeklinde bir denklem bulunmaktadır. A(0,k) = k+1 olduğuna göre, ve denklemin son değeri 2 olduğuna göre her adımda 1 eklenerek yukarı çıkacak toplamda y adım için y+2 değeri olacaktır.
Diğer bir ifade ile,
A(1,y) = A(0,A(0,A(0,A(0, … , A(0,1) … ))))), işlemi y kadar iç içe girecektir.
A(1,y) = y+2 olarak bulunur.
Denklemi ilerletecek olursak
A(2,y) = A(1,A(2,y-1))
A(2,y-1) = A(1, A(2,y-2))
… , y adet adım sonra
A(2,y-y) = A(2,0)
A(2,0) = A(1,1)
Bir önceki ispatta görüldüğü üzere A(1,1) = 3 olacağına göre
A(2,y) = A(1,A(1,A(1,… A(1,1) … ))) olacaktır. Bu denklem açıldığında
A(2,1) = A(1,A(2,0)) = A(1,A(1,1)) = A(1,3) = 5
A(2,2) = A(1,A(2,1)) = A(1,5) = 7
A(2,3) = A(1,A(2,2)) = A(1,7) = 9
…
şeklinde devam edecektir. Nihayet y adet adım sonrası için
A(2,y) = A(1, 2y + 1) olacak ve bu değerde = 2y + 1 + 2 = 2y +3
olarak bulunacaktır. Buradaki 2y+1 kısmı tek sayıyı veren formüldür.
Denklemin çözümü yukarıdakine benzer olarak ispatlanarak devam edebilir. Ancak ilginç olan özellik x=3 ve sonrası için yaşanmaktadır. Bunun sebebi denklemin knuth üstü olarak (knuth power) yazılabilmeye başlamasıdır.
-
- A( x, y) =2↑ x-2(y+3)-3 olarak yazılabilir.
m↑ kn gösterimi, knuth üstü olmak üzere n. ackermann sayısı aşağıdaki şekilde yazılabilir:
n↑ nn
Bu gösterimi açacak olursak:
-
- 1↑1 = 1 1 = 1,
-
- 2↑↑2 = 2↑2 = 2 2 = 4,
-
- 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = 3 27