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: s1, s2, s3, … kümesi tanımlanıyorsa bu kümedeki bütün elemanlar s1, s2, s3, …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(si) = 1 si ∈ S
f(si) = 0 si ∉ S
şeklinde gösterilen ve S kümesinin her elemanı olan si için 1 veya 0 şeklinde bir sonuç çıkaran kümeydi. Özyineli sayılabilir küme ise
f(si) = 0 si ∈ S
f(si) = belirsiz / hesaplanamaz si ∉ S
şeklinde gösterilen bir fonksiyon olmalıdır.