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

จากวิกิพีเดีย สารานุกรมเสรี
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
JAnDbot (คุย | ส่วนร่วม)
โรบอต แก้ไข: en:Computability
JAnDbot (คุย | ส่วนร่วม)
โรบอต ลบ: tr:Hesaplanabilirlik kuramı
บรรทัด 30: บรรทัด 30:
[[sh:Teorija izračunljivosti (računarstvo)]]
[[sh:Teorija izračunljivosti (računarstvo)]]
[[simple:Computability theory]]
[[simple:Computability theory]]
[[tr:Hesaplanabilirlik kuramı]]
[[zh:可计算性理论]]
[[zh:可计算性理论]]

รุ่นแก้ไขเมื่อ 15:25, 15 กรกฎาคม 2553

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

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

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