Karar Verilebilirlik (Decidability) nedir?

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.

dil-siniflandirmasi

Karar verilebilir bir dilde Turing makinesi ya kabul ya da ret sonucunu döndürür:

turing-makinesi-kabul-ret

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.

Etiketler: , ,

2 Yorum

  1. Decidability ve decidable languages ile undecidabilityve undecidable* languages fark nedir

Yorum Yapın