Özyineli sayılabilir küme (Recursively Enumerable Sets)

Yazan : Şadi Evren ŞEKER

Hesaplanabilirlik teorisine (Computability Theory) bir sayı kümesi elemanlarının tamamının bir algoritma için çalışıp son bulma şartını sağlıyorsa özyineli sayılabilir küme olarak sınıflandırılır.

Daha basit bir anlatımla kümede bulunan bütün elemanlar bir algoritma için, o algoritmanın bitmesini sağlayacak elemanlar olmalıdır.

Daha akademik bir tanımla bir özyineli hesaplanabilir fonksiyon (Recursively Computable Function) için etki alanı olarak S: s₁, s₂, s₃, … kümesi tanımlanıyorsa bu kümedeki bütün elemanlar s₁, s₂, s₃, …için fonksiyona girdi (argument, parameter) olma imkanı bulunmalıdır.

Tanım itibariyle özyineli kümenin (recursive set) alt kümesi kabul edilen bu kümenin farkı kümenin elemanı olmayan durumlarda sonucun kestirilememesidir.

Yani özyineli kümenin tanımının hatırlayacak olursak:

f(s_i) = 1 s_i ∈ S

f(s_i) = 0 s_i ∉ S

şeklinde gösterilen ve S kümesinin her elemanı olan s_i için 1 veya 0 şeklinde bir sonuç çıkaran kümeydi. Özyineli sayılabilir küme ise

f(s_i) = 0 s_i ∈ S

f(s_i) = belirsiz / hesaplanamaz s_i ∉ S

şeklinde gösterilen bir fonksiyon olmalıdır.

« Hesaplanabilir Fonksiyon (Computable Function) | Mana Ağları (Sematic Webs, Anlamsal Ağ) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Özyineli sayılabilir küme (Recursively Enumerable Sets)' isimli yazı 25 Jun 2009 tarihinde, saat: 12:13 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 343 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