การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่แก้ได้หรือไม่เป็นประเด็นที่สำคัญในทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณได้ จึงได้นิยามศัพท์คำว่า การตัดสินได้ และ การรับรองได้ โดยนิยามไว้ดังนี้

• ปัญหาที่ ตัดสินได้ (decidable) แก้ได้ (solvable) หรือ รู้จำได้ (recognizable) หมายถึงปัญหาที่มีเครื่องจักรทัวริงที่สามารถตอบปัญหานี้ได้ว่า "ใช่" หรือ "ไม่ใช่" เสมอสำหรับทุกๆ อินพุต ปัญหานี้จะมีความสัมพันธ์กับ recursive set
• ปัญหาที่ รับรองได้ (acceptable) หมายถึงปัญหาที่มีเครื่องจักรทัวริงที่สามารถตอบปัญหานี้ได้ว่า "ใช่" เสมอสำหรับอินพุตที่ "ใช่" แต่สำหรับอินพุตที่ "ไม่ใช่" เครื่องจักรทัวริง อาจตอบว่า "ไม่ใช่" หรือทำงานไปเรื่อยๆ โดยไม่สิ้นสุดก็ได้ ปัญหานี้จะมีความสัมพันธ์กับ recursively enumerable set
• ปัญหาที่ ตัดสินไม่ได้ (undecidable) หมายถึงปัญหาการตัดสินใจอื่นๆ ที่ไม่ใช่ ปัญหาที่ตัดสินได้

จะสังเกตเห็นว่า ปัญหาที่ตัดสินได้ย่อมเป็นปัญหาที่รับรองได้ไปด้วยและปัญหาที่ตัดสินไม่ได้อาจเป็นปัญหาที่รับรองได้ก็ได้ ยกตัวอย่างปัญหาที่ตัดสินไม่ได้แต่รับรองได้เช่น ปัญหาการยุติการทำงาน เป็นต้น