Karar Verilebilirlik (Decidability) nedir?
Bir dil Turing makinesi tarafından kabul ediliyorsa rekürsif/özyineli veya karar verilebilir (decidable) olarak adlandırılır. Bütün karar verilebilir diller Turing Acceptable’dır.
Diller:
-Karar Verilebilir (Decidable)
-Turing Kabul Eder (Turing Acceptable)
-Turing Kabul Etmez (Non-Turing Acceptable)
olarak sınıflandırılabilir.
Karar verilebilir bir dilde Turing makinesi ya kabul ya da ret sonucunu döndürür:
Bir dil karar verilebilir ise tümleyeni de karar verilebilirdir.
Karar verilebilir bir dil aynı zamanda sayılabilirdir.
Örnek: m sayısının asal olup olmadığı problemi karar verilebilir (decidable) mi karar verilemez (undecidable) mıdır?
Asal Sayılar={2,3,5,7,11,13,…}
m sayısını 2 ile √m arasındaki bütün sayılara böleriz, herhangi birisi 0 kalanını verirse ret, aksi halde kabul olur. Böylece bu problem karar verilebilir bir problemdir.
Decidability ve decidable languages ile undecidabilityve undecidable* languages fark nedir
Decidability: Karar verilebilirlik
Decidable: Karar verilebilir
Yani Decidability Language: Karar verilebilirlik Dili gibi ifade olmayacağından Decidable Language: Karar Verilebilir Dil denmektedir. Türkçedeki ebilmek-abilmek olayını bir inceleyiniz. Örneğin: http://www.hemeningilizce.com/ingilizce-ders/ebilmek-abilmek