Hesaplanabilirlik Kuramı
Hesaplanabilirlik kuramı, prensipte hangi problemlerin bir algoritma tarafından çözülebileceğini incelemekte ve çözülemeyen problemleri zorluk derecelerine göre sınıflandırmaktadır.
Tanım
Hesaplanabilirlik kuramı, aynı zamanda özyineleme kuramı (recursion theory) olarak da adlandırılmakta olup, etkin bir şekilde hesaplanabilir fonksiyon kavramını kesinleştiren, algoritmaların hesaplayabileceği ve hesaplayamayacağı kümeleri ve fonksiyonları inceleyen, ayrıca çözülemeyen problemlerin göreceli zorluğunu ölçen matematiksel mantığın bir dalıdır.
Kapsam
Bu alan, hesaplamanın biçimsel modellerini ve Church-Turing tezini, hesaplanabilir ve hesaplanabilir sayılabilir kümeleri, durma problemi gibi karar verilemez problemleri, göreceli çözülemezliği ölçen indirgenebilirlikleri ve Turing derecelerini, ayrıca niceleyici karmaşıklığına göre tanımlanabilirliği katmanlandıran aritmetik hiyerarşiyi kapsamaktadır.
Alt konular
Temel sorular
- Bir fonksiyonun veya kümenin hesaplanabilir olması ne anlama gelmektedir?
- Hangi doğal problemler algoritmik olarak karar verilemezdir?
- Çözülemeyen problemlerin zorluğu nasıl karşılaştırılabilir ve sıralanabilir?
- Mantıksal karmaşıklık, hesaplanabilirlik seviyeleriyle nasıl bir ilişki içindedir?
Temel kuramlar
- Church-Turing tezi
- Etkin hesaplanabilirlik sezgisel kavramı, Turing makinesi hesaplanabilirliği ile eşleşmekte olup, eşdeğer olarak özyinelemeli fonksiyonlar ve lambda ile tanımlanabilir fonksiyonlarla da örtüşmekte ve algoritmanın sağlam bir matematiksel tanımını sabitlemektedir.
- Durma probleminin çözülemezliği
- Hiçbir algoritma, her program ve girdi için programın durup durmayacağına karar verememekte, bu da karar verilemez bir problemin ilk ve prototipik örneğini sunmaktadır.
- Turing dereceleri
- Turing indirgenebilirliği, kümeleri göreceli hesaplanabilirliklerine göre sıralamakta ve ortaya çıkan dereceler, ara derecelerin varlığı da dahil olmak üzere yapısı merkezi bir çalışma nesnesi olan zengin bir kısmi sıralama oluşturmaktadır.
Klinik önem
Hesaplanabilirlik kuramı, algoritmik çözülebilirliğin mutlak sınırını belirlemekte, teorik bilgisayar biliminin temelini oluşturmakta ve matematiğin genelinde tekrar eden, durma ve kelime problemleri gibi çözülemezlik sonuçlarını sağlayarak hesaplama karmaşıklığı kuramına bilgi vermektedir.
Tarihçe
Hesaplanabilirlik kuramı, 1930'larda Church, Turing, Kleene ve Post'un lambda kalkülüsü, Turing makineleri, özyinelemeli fonksiyonlar ve kombinatoryal sistemler aracılığıyla etkin bir prosedür kavramını birbirinden bağımsız olarak biçimselleştirmesiyle ortaya çıkmıştır; bu yaklaşımların hepsi birbirine eşdeğer olduğu kanıtlanmıştır. Post ve Kleene, dereceler kuramını ve aritmetik hiyerarşiyi geliştirmiş, 1950'lerde tanıtılan öncelik yöntemi ise hesaplanabilir sayılabilir derecelerin derin yapısal incelemesini yönlendirmiştir.
Öne çıkan isimler
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
İlgili konular
Temel eserler
- soare1987
- rogers1987
- cutland1980
Sıkça sorulan sorular
- Hesaplanabilirlik kuramı, karmaşıklık kuramı ile aynı mıdır?
- Hayır. Hesaplanabilirlik kuramı, bir problemin herhangi bir algoritma tarafından çözülüp çözülemeyeceğini kaynakları göz ardı ederek sormakta; karmaşıklık kuramı ise çözülebilir bir problemin ne kadar zaman veya bellek gerektirdiğini araştırmaktadır. Hesaplanabilirlik, çözülebilir ve çözülemez arasındaki sınırı çizerken; karmaşıklık, çözülebilir tarafı derecelendirmektedir.
- Church-Turing tezi neden bir teorem değildir?
- Gayri resmi bir kavram olan etkin hesaplanabilirliği, kesin bir matematiksel kavramla eşitlediği için biçimsel olarak kanıtlanamaz. Kabulü, birçok bağımsız biçimselleştirmenin aynı fonksiyon sınıfında birleşmesine dayanmakta olup, bu bir kanıttan ziyade güçlü bir kanıttır.