Hesaplanabilir fonksiyon

Hesaplanabilir fonksiyonlar, hesaplanabilirlik teorisinde kullanılan temel nesnelerdir. Hesaplanabilir fonksiyonlar, algoritmaların sezgisel kavramının resmileştirilmiş analoğudur. Bir fonksiyonun, fonksiyonun işini yapabilen bir algoritma varsa hesaplanabilir olması, yani fonksiyon alanının bir girdisi verildiğinde karşılık gelen çıktıyı vermesidir. Hesaplanabilir fonksiyonlar, Turing makineleri veya kayıt makineleri gibi herhangi bir somut hesaplama modeline atıfta bulunmadan hesaplanabilirliği tartışmak için kullanılır. Hesaplanabilir işlevler kümesine yol açan belirli hesaplanabilirlik modelleri, Turing-hesaplanabilir işlevler ve genel özyinelemeli işlevlerdir.

Ayrıca bakınız 

 Hesaplanabilir sayı
 Etkili yöntem
 Hesaplama teorisi
 Özyineleme teorisi
 Turing derecesi
 Aritmetik hiyerarşi
 Hiper hesaplama
 Süper özyinelemeli algoritma
 Yarı hesaplanabilir fonksiyon

Kaynakça 

 Cutland, Nigel. hesaplanabilirlik Cambridge University Press, 1980.
 Enderton, HB Özyineleme kuramının öğeleri. Handbook of Mathematical Logic (Kuzey-Hollanda 1977) s. 527–566.
 Rogers, H. Özyinelemeli fonksiyonlar teorisi ve etkin hesaplama (McGraw–Hill 1967).
 Turing, A. (1937), Entscheidungsproblem'e Bir Uygulama İle Hesaplanabilir Sayılar Üzerine  . Londra Matematik Derneği Bildirileri, Seri 2, Cilt 42 (1937), s.230–265. M. Davis'te yeniden basılmıştır (ed. ), Karar Verilemez, Raven Press, Hewlett, NY, 1965.

Algoritmalar teorisi
Hesaplanabilirlik teorisi