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

 

 

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


× sekiz = 72