ทฤษฎีการคำนวณได้

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

ตารางแสดงความสัมพันธ์ระหว่างกลุ่มของปัญหา สามารถดูได้ในบทความเกี่ยวกับทฤษฎีการคำนวณ

หมวดหมู่:คณิตตรรกศาสตร์
หมวดหมู่:ทฤษฎีการคำนวณ
หมวดหมู่:ทฤษฎีการคำนวณได้