Etiket Arşivleri: Hesaplanabilirlik (Computability)

Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız?

Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız? Hesaplanabilirlik (Computability), bir problemin hesaplanıp hesaplanamayacağını yani bir çözümünün olup olmadığını belirtir. Bir problem belli prensiplerle bir hesaplama cihazı ile çözülebiliyorsa hesaplanabilirdir. Bu tip problemler hesaplanabilir(computable), çözülebilir(solvable), karar verilebilir(decidable) ve özyineli(recursive) olarak ta adlandırılmaktadır. 1930’lu yıllarda Gödel, Turing ve Church bazı problemlerin çözülemeyeceğini göstermiştir. Halting (Durma) problemi, Post>>>