Hesaplanabilir Fonksiyon (Computable Function)

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 : A₁ x A₂ x … x A_n → B şeklinde tanımlı bir fonksiyon alalım. Bu durumda f(a₁, a₂, …, a_n) = b olarak gösterilebilir ve a_i ∈ A_i, 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(a₁, a₂, …, a_n)↓ = b ile gösterilen fonksiyonun a₁, a₂, …, a_nargü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.

« Özyineli Küme (Recursive Set) | Özyineli sayılabilir küme (Recursively Enumerable Sets) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Hesaplanabilir Fonksiyon (Computable Function)' isimli yazı 25 Jun 2009 tarihinde, saat: 12:06 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 395 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