Özyineli Küme (Recursive Set)

Yazan : Şadi Evren ŞEKER

Hesaplanabilirlik teorisine (Computability Theory) göre bir doğal sayılardan oluşan bir kümedeki bütün elemanlar bir algoritmanın belirli bir zaman sonra sona ermesini sağlıyorsa bu kümeye özyineli küme ismi verilir. Şayet kümenin elemanlarından bir veya daha fazlası algoritmanın belirli bir zamanda bitmesini sağlamıyorsa bu kümeye hesaplanamaz (noncomputable) veya karar verilemez (undecidable) ismi verilir.

Özyineli küme terimi yerine hesaplanabilir küme (computable set) veya karar verilebilir küme (decidable set) terimleri de kullanılır.

Daha akademik bir tanımla şayet hesaplanabilir bir fonksiyonun aldığı parametereleri tutan bir S kümesi varsa ve bu fonksiyon kümedeki elemanlar için doğru ve kümede olmayan elemanlar için yanlış sonuç üretiyorsa (C dilinde 0 ve 1 olarak kabul edilebilir) bu kümeye özyineli küme (recursive set) ismi verilir.

f(s_i) = 1 s_i ∈ S

f(s_i) = 0 s_i ∉ S

şartlarını sağlıyorsa özyineli küme ismi verilir.

Yukarıdaki tanma göre boş küme, bütün doğal sayılar kümesi veya asal sayılar kümesi gibi kümeler özyineli küme olarak kabul edilebilirler.

Örnek Soru:

S isminde bir küme aşağıdaki şekilde tanımlanıyor olsun:

3 ∈ S

x ∈ S ve y ∈ S ise x + y ∈ S

Yukarıdaki S kümesinin 3′e tam bölünebilen pozitif tam sayılar kümesi olduğunu gösteriniz.

Çözüm:

Yukarıda tanımı yapılan kümenin 3′e tam bölünebilen pozitif tam sayı kümesi olduğunu göstermek için bu tanıma A kümesi diyelim. Yani S yukarıda tanımlanan küme ve A da olduğunu göstermemiz istenen küme olsun.

Bu durumda A = S olduğunu göstermemiz gerekiyor. Bunu göstermenin bir yolu daaynı anda

hem A ⊆ S hem de S ⊆ A olduğunu göstermemizdir. Yani şayet A, S’in alt kümesi ve aynı anda S de A’nın alt kümesiyse bu iki küme eşittir denilebilir.

Önce A’nın S’in alt kümesi olduğunu ispatlayalım. Bunun için matematiksel tümevarım teoreminden (mathematical induction principle) istifade edeceğiz.

başlangıç adımımız (basis step) : 3 olarak kabul edersek

istikra adımı olarak P(n) gibi bir fonksiyon tanımlayalım. P(n) sayının 3′e bölünebilme özelliğini kullanan fonksiyon olsun dolayısıyla

P(n) = 3n olsun. Görüldüğü üzere P(n) fonksiyonu her zaman 3′e tam bölünebilen sayılar üretir.

S kümesindeki herhangi bir k sayısını alalım. Bilindiği üzere k sayısı 3′e bölünebilen sayıdır (iddia gereği)

Dolayısıyla k = 3n şeklinde yazılabilir.

İstikra gereği (induction) bu serideki bir sonraki sayıyı bulmak için S kümesindeki en küçük eleman olan 3 ile sayımızı topluyoruz.

Öyleyse k+3 yada 3n+3 sayısı serideki k’dan sonra gelen sayı olur.

Bu gösterimi A kümesi için yazacak olsaydık

P(n) = 3n olacaktı ve bir sonraki sayı P(n+1) = 3n +3 olacaktı.

Dolayısıyla görülebileceği üzere

P(n) = k

P(n+1) = k+3

eşitlilklerinin ikisi de , yani isitkra (tümevarım, induction) adımlarımızın ikisi de sağlanmış oluyor.

Şimdi ispatın ikinci kısmına geçelim ve S’in A’nın alt kümesi olduğunu gösterelim. Bunun için S’in özyineli (recursive) tanımından faydalanabiliriz.

Öncelikle başlangıç adımı olan 3, S kümesinin elemanıdır. Ayrıca 3 = 3×1 şeklinde yazılabilir. Buradan S kümesindeki bütün elemanların 3xn şeklinde yazılabileceğini söyleyebiliriz. Bunu göstermek için S kümesinin tanımındaki ikinci parçayı yani x+y’nin A’nın bir üyesi olduğunu göstermeliyiz.

Şayet 3|x ve 3|y ise (yani x ve y ayrı ayrı 3′e tam olarak bölünebiliyorsa) o zaman 3|x+y’dir denilebilir (x+y, 3′e tam bölünebilir)

Yukarıdaki bu bölünebilirlik iddiasını ispatlamak için

3| x ve 3|y durumunda

x = 3s ve y = 3t olarak yazılabilir. Buradaki s ve t değerleri 3 sayısının herhangi bir çarpanıdır.

Dolayısıyla x + y = 3s + 3t olarak yazılabilir ve buradan 3(s+t) sonucuna ulaşılır ki s+t değeri her ne olursa olsun 3(s+t) değeri 3′e tam bölünebilir.

Yukarıdaki iki ispat sonucunda A=S olduğu söylenebilir ve özyineli kümenin bu özelliğinden faydalanarak ispat yapılmıştır.

« Hesaplanabilirlik Teorisi (Computability Theory) | Hesaplanabilir Fonksiyon (Computable Function) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Özyineli Küme (Recursive Set)' isimli yazı 25 Jun 2009 tarihinde, saat: 11:38 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 334 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, algoritma analizi (teory of algorithms), bilgisayar felsefesi kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar