hesaplanabilir

Hesaplanabilirlik veya hesaplanabilir kavramı, bir fonksiyonun ya da problemin bir algoritma ile sonlu adımlar içinde çözülebilir olması durumunu ifade eder. Böyle bir durumda için giriş üzerinde her zaman sonlu adımda doğru çıktı veren bir hesaplama prosedürü vardır. Bu prosedürler, Turing makinesi, lambda hesaplaması veya rekürsif fonksiyonlar gibi farklı modellerde tasarlanabilir ve bu modeller genelde birbirine denk hesaplanabilirlik sınıfını işaret eder.

Çeşitli hesaplama modelleri, hesaplanabilirliği tanımlayan temel araçlardır. En çok bilinenler arasında Turing makineleri, lambda hesaplaması ve rekürsif fonksiyonlar bulunur. Bu modeller, hesaplanabilirlik kavramını bağımsız olarak da olsa tanımlamış ve çoğu durumda aynı sınıfı kapsadıkları kabul edilmiştir; bu görüş, Church-Turing tezi ile özetlenir.

Tarihsel olarak hesaplanabilirlik kuramı, 1930’larda Alonzo Church ve Alan Turing’in çalışmalarıyla ortaya çıktı. Kleene ve diğerleri, rekürsif fonksiyonlar ve hesaplama kuramını geliştirdi. Günümüzde hesaplanabilirlik, bilgisayar biliminin temel bir konusu olarak, algoritma tasarımı, karar problemleri ve karmaşıklık kuramı ile ilişkilendirilir.

Örnekler arası farklar da vardır. Doğal sayılar üzerinde toplama, çarpma ve temel karşılıklı işlemler hesaplanabilir. Ancak bir programın kendi durumunu sonlandırıp sonlandırmayacağını her durumda belirlemek istenen halting problemi hesaplanamazdır. Hesaplanabilirlik, bu tür sınırları ve olası hesaplama modellerinin güçlerini anlamada kilit rol oynar.