ความสามารถในการตัดสินใจภาษา

ภาษาเรียกว่า Decidable หรือ Recursive หากมีเครื่องทัวริงที่ยอมรับและหยุดทุกสายอักขระอินพุต w. ทุกภาษาที่สามารถตัดสินใจได้คือ Turing-Acceptable

ปัญหาในการตัดสินใจ P จะตัดสินใจได้ถ้าภาษา L จากทุกกรณีที่ใช่ P ตัดสินใจได้

สำหรับภาษาที่ถอดรหัสได้สำหรับแต่ละสตริงอินพุต TM จะหยุดที่สถานะยอมรับหรือปฏิเสธตามที่แสดงในแผนภาพต่อไปนี้ -

ตัวอย่าง 1

ค้นหาว่าปัญหาต่อไปนี้สามารถตัดสินใจได้หรือไม่ -

จำนวนไพรม์ 'm' หรือไม่?

วิธีการแก้

เลขเฉพาะ = {2, 3, 5, 7, 11, 13, ………… .. }

หารจำนวน ‘m’ โดยตัวเลขทั้งหมดระหว่าง '2' ถึง '√m' เริ่มจาก '2'

หากตัวเลขใด ๆ เหล่านี้ทำให้เกิดส่วนที่เหลือเป็นศูนย์ก็จะเข้าสู่“ สถานะถูกปฏิเสธ” มิฉะนั้นจะเข้าสู่“ สถานะที่ยอมรับ” ดังนั้นคำตอบสามารถทำได้โดย "ใช่" หรือ "ไม่ใช่"

Hence, it is a decidable problem.