ผลต่างระหว่างรุ่นของ "ทฤษฎีการคำนวณได้"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เหตุไรเจ้าจึงกลายเป็นโครงคณิตศาสตร์ |
|||
บรรทัด 9: | บรรทัด 9: | ||
[[หมวดหมู่:ทฤษฎีการคำนวณ]] |
[[หมวดหมู่:ทฤษฎีการคำนวณ]] |
||
{{โครง |
{{โครงคอมพิวเตอร์}} |
||
[[ar:نظرية الحاسوبية]] |
[[ar:نظرية الحاسوبية]] |
รุ่นแก้ไขเมื่อ 04:05, 17 ธันวาคม 2551
ทฤษฎีการคำนวณได้ คือส่วนหนึ่งของการศึกษาในทฤษฎีการคำนวณที่สนใจกับปัญหาที่ว่า ปัญหาใดที่สามารถหาคำตอบได้ด้วยอัลกอริทึม (หรือ—ในความหมายที่เหมือนกัน—โดยเครื่องจักรทัวริง) ภายใต้ข้อจำกัดและข้อเพิ่มเติมหลายๆ แบบ ทฤษฎีการคำนวณได้ศึกษาปัญหาหลักๆ สี่ปัญหาดังต่อไปนี้
- ปัญหาใดที่เครื่องจักรทัวริงสามารถแก้ได้?
- ระบบในการคำนวณใดที่มีความสามารถเท่าเทียมกับเครื่องจักรทัวริง?
- ปัญหาใดที่ต้องการเครื่องจักรที่มีความสามารถมากกว่าเครื่องจักรทัวริง?
- ปัญหาใดที่สามารถแก้ได้โดยเครื่องจักรที่มีความสามารถน้อยกว่าเครื่องจักรทัวริง?
ตารางแสดงความสัมพันธ์ระหว่างกลุ่มของปัญหา สามารถดูได้ในบทความเกี่ยวกับทฤษฎีการคำนวณ