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

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

• ปัญหาใดบ้างที่เครื่องทัวริงสามารถแก้ได้
• ระบบคณนาใดบ้างที่มีความสามารถทัดเทียมกับเครื่องทัวริง
• ปัญหาใดบ้างที่ต้องการเครื่องที่มีความสามารถเหนือกว่าเครื่องทัวริง
• ปัญหาใดบ้างที่สามารถแก้ได้โดยเครื่องที่มีความสามารถด้อยกว่าเครื่องจักรทัวริง

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