Yazan : Şadi Evren ŞEKER
Hesaplanabilirlik teorisinin (Computability Theory) temel taşlarından birisi olan özel bir fonksiyon (function) tipidir. Bu fonksiyonların özelliği herhangi bir formal dilbilgisi (formal grammer) yardımıyla açıklanmayan fonksiyonlar olmalarıdır.
Genellikle karıştırıldıkları için karmaşıklık teorisi (complexity theory) ile hesaplanabilirlik teorisi (computability theory) arasındaki farkı bu fonksiyonlar üzerinde de vurguluamakta yarar vardır. Basitçe bir fonksiyonun hesaplanabilir olması o fonksiyonun bir sonucunun çıkması anlamına gelir.
Örneğin Church-Turing testine göre bir fonksiyonun hesaplanabilir olması bu fonksiyonun bir makine ile (veya elektronik devre ile veya bilgisayar programı ile) modellenebiliyor olmasını ve sınırsız zaman ve depolama imkanı (storage) verildiğinde bir şekilde biteceği anlamına gelir.
Bu bağlamda bir fonksiyonun hesaplanabilir olması en verimli şekilde hesaplanması (efficiency) veya en kısa zamanda veya en kısa depolama ihtiyacıyla çalışıp bitmesi anlamından farklıdır. Bu tip kaygılar daha çok karmaşıklık teorisi (complexity theory) konusunun çalışma alanına girmektedir.
Hesaplanabilir fonksiyonları basitçe bir parametre havuzundaki elemanlar için sonuç döndüren fonksiyonlar olarak düşünebiliriz. Örneğin f : A1 x A2 x … x An → B şeklinde tanımlı bir fonksiyon alalım. Bu durumda f(a1, a2, …, an) = b olarak gösterilebilir ve ai ∈ Ai, i = 1, …, n ve b ∈ B’dir denilebilir. Klasik bir fonksiyonu bu şekilde tanımladıktan sonra hesaplanabilir fonksiyonu bu fonksiyonda sonuç bulan anlamında ↓ sembolü ile gösterek
f(a1, a2, …, an)↓ = b ile gösterilen fonksiyonun a1, a2, …, an argümanları için b sonucunu veren fonksiyon olduğunu söyleyebiliriz.
Örneğin bir dilin hesaplanabilir olması bu dildeki bütün kelimeler için doğru ve bu dilden olmayan bütün kelimeler için de yanlış sonucunu veren bir fonksiyon bulunabilmesine bağlıdır. Bu fonksiyona da hesaplanabilir fonksiyon ismi verilir.
Örneğin bir düzenli ifade (regular expression) ile gösterilen dildeki bütün üretilebilen kelimeler için doğru sonucu veren fonksiyon ve üretilemeyen bütün kelimeler için yanlış sonucu veren fonksiyon bu tip bir fonksiyondur.
Bu tanımı biraz daha genişleterek bir A kümesi ve bir bu küme üzerindeki bir f fonksiyonu için Turing makinesi (turing machine) üretilebiliyorsa (ya da bir kahin makinesi (oracle) ) hesaplanabilir bir kümemiz ve hesaplanabilir bir fonksiyonumuz bulunuyor demektir. Bu duruma A-hesaplanabilir (A-computable) veya f-hesaplanabilir (f-computable) isimleri de verilir.