ปัญหาการยุติการทำงาน
From Wikipedia, the free encyclopedia
ในทฤษฎีการคำนวณได้ ปัญหาการยุติการทำงาน (อังกฤษ: Halting problem) คือปัญหาการตัดสินใจที่ถามว่า
- กำหนดขั้นตอนวิธีและข้อมูลป้อนเข้าให้ จงหาว่าขั้นตอนวิธีเมื่อทำงานกับข้อมูลป้อนเข้าดังกล่าวแล้ว จะยุติการทำงาน (ทำงานเสร็จสิ้น) หรือจะทำงานไปเรื่อย ๆ ไม่มีที่สิ้นสุด
แอลัน ทัวริง (Alan Turing) พิสูจน์ในปี ค.ศ. 1936 ว่า ไม่มีขั้นตอนวิธีที่แก้ปัญหาการยุติการทำงานสำหรับข้อมูลป้อนเข้าใด ๆ ได้ทั้งหมดบนเครื่องจักรทัวริง จึงกล่าวว่าปัญหาการยุติการทำงานนี้ไม่สามารถตัดสินได้