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 Correspondence problemi çözülemeyen/karar verilemeyen(undecidable) problemlerdendir.
Karmaşıklık (Complexity), bir probleminin çözümünün ne kadar zaman (adım) veya alan (bellek) ile gerçekleştirildiğini belirlemek için kullanılır. Bu aşamaya geçilebilmesi için problemin hesaplanabilir olması gerekmektedir. En iyi algoritma en hızlı ve en az hafıza ihtiyacı ile çalışan algoritmadır.
Hesaplanabilirlikte; bir hesaplama modeli algotiması ile problemlerin ne kadar yeterli olarak çözülebileceğini de söylebiliriz. Önemli soru budur, “Bilgisayarın temel yetenekleri ve sınırlamaları nedir?” .
Teşekkürler