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

จากวิกิพีเดีย สารานุกรมเสรี

บทความนี้ต้องการแหล่งอ้างอิงเพิ่มเติม เพื่อให้บทความน่าเชื่อถือและสมบูรณ์ยิ่งขึ้น คุณสามารถช่วยพัฒนาวิกิพีเดีย โดยเพิ่มแหล่งอ้างอิงที่เหมาะสม อย่าปล่อยให้งานเขียนของคุณปราศจากแหล่งอ้างอิงที่สามารถยืนยันได้ รายละเอียดเพิ่มเติม การอ้างอิงแหล่งที่มา - การพิสูจน์ยืนยันได้ - วิธีการเขียน - ป้ายนี้มีไว้เพื่ออะไร

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

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

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

ทฤษฎีการคำนวณได้ เป็นบทความเกี่ยวกับ คอมพิวเตอร์ อุปกรณ์คอมพิวเตอร์ หรือ เครือข่าย ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหาหรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ ทฤษฎีการคำนวณได้ ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ หรือ ดูเพิ่มที่ สถานีย่อย:เทคโนโลยีสารสนเทศ