Hesaplanabilirlik ve Karar Verilebilirlik
Hesaplanabilirlik kuramı, algoritmik problem çözmenin temel sınırlarını incelemekte olup, etkili bir prosedürle çözülebilecek problemler ile hiçbir algoritmanın karar veremeyeceği problemler arasındaki sınırı belirlemektedir.
Tanım
Hesaplanabilirlik kuramı, hangi fonksiyonların ve karar problemlerinin etkili bir prosedürle hesaplanabilir olduğunu inceleyen bir alandır; bir problem, eğer bir algoritma her zaman doğru evet-hayır cevabıyla duruyorsa karar verilebilir, böyle bir algoritma mevcut değilse karar verilemez olarak tanımlanmaktadır.
Kapsam
Bu alan, Turing makineleri gibi etkili hesaplamanın biçimsel modellerini, bu modelleri sezgisel algoritma kavramıyla özdeşleştiren Church–Turing tezini, durdurma problemi de dahil olmak üzere karar verilemez problemlerin varlığını, problemler arasında çözülemezliği aktarmak için kullanılan indirgemeleri ve hesaplanabilirliğin ötesindeki problemleri sınıflandıran çözülemezlik derecelerinin yapısını kapsamaktadır.
Alt konular
Temel sorular
- Bir problemin bir algoritma tarafından çözülebilir olması ne anlama gelmektedir?
- Hiçbir algoritmanın çözemeyeceği iyi tanımlanmış problemler var mıdır?
- Bir problemin çözülemezliği, başka bir problemin çözülemezliğini kanıtlamak için nasıl kullanılabilir?
- Çözülemez problemler, göreceli zorluklarına göre nasıl sınıflandırılmaktadır?
Temel kuramlar
- Turing'in hesaplama modeli
- Turing'in soyut makinesi, etkili bir prosedür kavramını biçimselleştirmiş ve durdurma ile birinci dereceden mantık için karar problemlerinin çözülemez olduğunu kanıtlamak için kullanılmıştır, böylece hesaplamanın doğal sınırlarını belirlemiştir.
- Karar verilemez problemlerin varlığı
- Köşegen argümanıyla, hiçbir algoritmanın karar veremeyeceği problemler (en ünlüsü durdurma problemi) bulunmaktadır; bu nedenle karar verilemezlik, bir merak olmaktan ziyade yaygın bir yapısal özelliktir.
- Hesaplama modellerinin eşdeğerliği
- Turing makineleri, lambda kalkülüsü ve özyinelemeli fonksiyonlar, tam olarak aynı hesaplanabilir fonksiyonlar sınıfını tanımlamaktadır; bu yakınsama, Church–Turing tezini desteklemektedir.
Klinik önem
Karar verilemezlik sonuçları, yazılım araçlarının garanti edebileceği şeyler üzerinde kesin sınırlar koymaktadır: hiçbir genel algoritma, rastgele bir programın durup durmadığına, doğru olup olmadığına veya belirli hatalardan arınmış olup olmadığına karar veremez; bu nedenle doğrulama araçları, tam otomatik analiz yerine yaklaşıma, kısıtlı dillere ve insan rehberliğine dayanmaktadır.
Tarihçe
Hilbert'in Entscheidungsproblem'i tarafından tetiklenen Church ve Turing, 1936'da bağımsız olarak hiçbir algoritmanın birinci dereceden mantığın tamamına karar veremeyeceğini göstermiştir; Turing'in makine modeli ve Church'ün lambda kalkülüsü eşdeğer olduğunu kanıtlamıştır. Post ve Kleene, sonraki on yıllarda kuramı çözülemezlik derecelerinin incelenmesine doğru genişletmiştir.
Öne çıkan isimler
- Alan Turing
- Alonzo Church
- Kurt Gödel
- Emil Post
İlgili konular
Temel eserler
- turing1937
- church1936
- sipser2013
Sıkça sorulan sorular
- Karar verilebilir ile karar verilemez arasındaki fark nedir?
- Bir problem, her girdi için her zaman duran ve doğru evet-hayır cevabını veren bir algoritma varsa karar verilebilirdir. Durdurma problemi için kanıtlandığı gibi, böyle bir algoritma mevcut olamazsa karar verilemezdir; karar verilemez bir problem yine de tanınabilir olabilir, yani bir algoritma evet-örneklerini doğrulayabilir ancak hayır-örneklerinde sonsuza kadar çalışabilir.
- Karar verilemezlik, bu problemlerin asla ele alınamayacağı anlamına mı gelmektedir?
- Bu, hiçbir tek algoritmanın her örneği doğru bir şekilde çözemeyeceği anlamına gelmektedir. Pratikte araçlar kısıtlı durumları ele almakta, yaklaşık veya muhafazakar cevaplar vermekte veya birçok örneği çözerken ara sıra başarısız olmakta veya yardım istemektedir; bu nedenle karar verilemezlik, tüm ilerlemeyi yasaklamak yerine problemlerin nasıl ele alındığını şekillendirmektedir.