ผลต่างระหว่างรุ่นของ "ทฤษฎีการคำนวณได้"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Jittat (คุย | ส่วนร่วม)
intro, interwiki
(ไม่แตกต่าง)

รุ่นแก้ไขเมื่อ 15:01, 12 มีนาคม 2548

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

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

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