Sayılabilirlik Teorisi

[Life Hunter]

Programlamada birçok alışkanlık vardır. Bu alışkanlıklardan biri de bütün sayı serilerini sayma sayılara çevirme alışkanlığıdır.
Sayma sayıların ne olduğunu hatırlamak ile başlayalım. {1,2,3,4,5,...} şeklinde 1'den başlayarak sonsuza kadar giden sayı serisine sayma sayıları deriz. Yani bizim günlük hayatımızda yaptığımız, sayıları sayma şekli. Sayılabilirlik teorisine göre amacımız, sayma sayılar serisi hariç, bütün sayı serilerini sayma sayılarına çevirmektir.

Örneğin 10'dan 20'ye kadar olan ve üçe tam bölünebilen sayıları ekranda yazdırmak isteyelim. Bu durum için 10'dan 20'ye kadar olan sayıları tek tek test edip, üçe tam bölünenleri bulup,onları ekrana yazdıran bir kod yazabiliriz.

for (int i = 10; i < 20; i++)
    if (i % 3 == 0)
        printf("%d\n",i);

Ve ya bu sayı serisinin {12,15,18,...} şeklinde olduğunu düşünür isek, sayaç değişkenini 12'den 20'ye kadar ayarlayıp,her seferinde üçer üçer arttıran bir kodda yazabiliriz.

for (int i = 12; i < 20; i += 3)
     printf("%d\n",i);

Peki size:
1 verildiğinde 12
2 verildiğinde 15
3 verildiğinde 18
Değerlerini çıkartan bir formül ve ya bir fonksiyon oluşturun desem? İşte herhangi bir sayı serisini, bu şekilde sayma sayıları şeklinde yazmak sayılabilirlik teorisidir.

Bu örnek için oluşturacağımız matematiksel fonksiyon şu şekilde olabilir:
f(x) = 9 + (3*x)

f(1) = 9 + (3*1) = 12
f(2) = 9 + (3*2) = 15
f(3) = 9 + (3*3) = 18

Görüldüğü gibi seri sürekli 3 arttığı için,sayma sayılarını 3 ile çarptık ve sonucu 9'a ekledik.Şimdi bu yaptığımız formülü koda dökelim:

for (int i = 1; i <= 3; i++)
    printf("%d\n",9 + (3*i));

Bu kod ile elde etmek istediğimiz sayı serisi olan {12,15,18} serisini sayma sayıları şeklinde yazmış olduk. Burada yapılan tek şey,döngünün {1,2,3,4,5,...} şeklinde yani sayma sayıları şeklinde gitmesini sağlayıp, sayac değişkenin değerlerini az önce oluşturduğumuz formüle soktuk ve istediğimiz sayı değerlerini sayma sayılarını kullanarak elde ettik.

Aynı formülün fonksiyonlar ile kullanılmış hali:

int f(int x){
    return 9 + (3 * x);
}

int main()
{
   for (int i = 1; i <= 3; i++)
         printf("%d\n",f(i));
}

Burada oluşturduğumuz formülü bir fonksiyonun içine attık ve for döngüsü ile her seferinde fonksiyonun parametre olarak sayma sayılar almasını sağladık.

Başka bir örnek, {10,30,60,100...} serisini sayılabilirlik teorisi ile ekrana yazdırmak isteyelim.
Sayılar arasındaki ilişkiye bakar isek,10'dan 30'a yirmi lik bir artış söz konusu. 30'dan 60'a otuz luk bir artış söz konusu. 60'dan 100'e ise 40 lık bir artış söz konusu.


Yani artış miktarı en başta 20 den başlayarak,her adımda 10 artmış. Fark önce 20 iken,sırası ile 30 ve 40 olmuş.

Bu durum için şöyle bir algoritma kurulabilir:
10*1 + 0 = 10
10*2 + 10 = 30
10*3 + 30 = 60
10*4 + 60 = 100
Bu formülde öncelik ile verilen sayma sayısı ile 10 sayını çarptık ve bir önceki formülün sonucunu ekledik. Tersten bakalım ve 4 verildiğini farz edelim,10 ile 4 çarpılacak ve bir önceki formülün sonucu yani formüle 3 verildiği zamanki sonuç eklenecek.
Formüle 3 verildiği zaman 60 olduğuna göre,4 verildiği zamanki sonuç (10*4) + 60 = 100 olur. 3 verildiği zamanda 10*3 + iki verildiği zamanki sonuç yani 10*3 + 30 dan 60.
Tabi bir sınır noktası koymazsak sonsuza kadar giden bir işlem olur bu yüzden 0 verildiği zamanki değeri 0 olarak varsayacağız.
Şimdi kodunu yazalım:

int x = 0;
for (int i = 1; i <= 4; i++) {
     x = 10 * i + x;
   printf("%d\n", x);
}

Burada x adında bir değişken oluşturduk ve ilk değer olarak 0 atadık. Bu değişkenin yaptığı iş bir önceki işlemden kalan sonucu tutup bu sonucu yeni işleme eklemesidir.

Bu formülü fonksiyon halinde yazacak olursak:
f(0) = 0 koşulu ile
f(x) = 10*x + f(x-1) şeklinde olabilir.
Görüldüğü üzere bu özyinelemeli(Recursive) bir fonksiyondur. Bu durumda bunu Recursive fonksiyon olarak programlayabiliriz.

int f(int x){
   if (x == 0)
       return 0;
  return 10 * x + f(x - 1);
}
int main()
{
   for (int i = 4; i >= 1; i--)
         printf("%d\n",f(i));
}

Görüldüğü gibi, birçok sayı serisini sayma sayılara indirgeyerek yazabiliriz. birçok diyorum çünkü bazı seriler sayma sayılara indirgenemiyor. Örneğin asal sayılar. Matematikte asal sayıların birbirleri ile olan ilişkisi halen bulunamadığından, asal sayıları veren bir fonksiyon yoktur. Dolayısı ile bunu sayılabilirlik teorisi ile yapamayız. Asal sayıları ekrana yazdırmanın tek yolu, sayıları tek tek test edip asal olanları ekrana yazdıran bir kod yazmaktır. Ama sayıları hiç test etmeden direk verilen sayma sayılarından hesaplayan bir kod yazılamıyor. Tabi ilerde asal sayılar arasındaki ilişki bulunur ise böyle bir kodda yazabilir