Hesaplanabilir fonksiyon
Hesaplanabilir fonksiyonlar, hesaplanabilirlik teorisinde kullanılan temel nesnelerdir. Hesaplanabilir fonksiyonlar, algoritmaların sezgisel kavramının resmîleş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
değiştirKaynakça
değiştir- 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 19 Haziran 2023 tarihinde Wayback Machine sitesinde arşivlendi. . 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.