ปัญหาการหยุดทำงานและการตัดสินใจไม่ได้

ปัญหาการหยุดทำงาน (halting problem) ซึ่งเป็นการตัดสินใจว่าโปรแกรมที่กำหนดจะหยุดทำงานบนอินพุตที่กำหนดหรือไม่ เป็นตัวอย่างหลักของปัญหาที่ตัดสินใจไม่ได้ด้วยอัลกอริทึม และการลดรูปจากปัญหานี้พิสูจน์ว่าปัญหาอื่นๆ อีกมากมายก็ตัดสินใจไม่ได้เช่นกัน

Definition

ปัญหาการตัดสินใจ (decision problem) จะตัดสินใจไม่ได้หากไม่มีเครื่องจักรทัวริง (Turing machine) ใดที่สามารถตัดสินใจได้อย่างถูกต้องสำหรับอินพุตทั้งหมด ปัญหาการหยุดทำงานถามว่าเครื่องจักรใดๆ จะหยุดทำงานบนอินพุตใดๆ หรือไม่ และเป็นปัญหาต้นแบบที่ตัดสินใจไม่ได้ ซึ่งใช้ในการแสดงให้เห็นว่าปัญหาอื่นๆ ตัดสินใจไม่ได้โดยการลดรูป

Scope

หัวข้อนี้ครอบคลุมถึงการระบุปัญหาการหยุดทำงานอย่างแม่นยำ การพิสูจน์ว่าตัดสินใจไม่ได้ด้วยวิธี diagonalization เทคนิคการลดรูปแบบหลายต่อหนึ่ง (many-one reduction) เพื่อถ่ายทอดคุณสมบัติการตัดสินใจไม่ได้ ทฤษฎีบทของ Rice เกี่ยวกับคุณสมบัติที่ไม่ใช่เรื่องเล็กน้อยของโปรแกรม และปัญหาคลาสสิกที่ตัดสินใจไม่ได้ เช่น Entscheidungsproblem และปัญหาคำสำหรับกลุ่ม (word problem for groups)

Core questions

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

Key theories

การแก้ไขไม่ได้ของปัญหาการหยุดทำงาน

ข้อโต้แย้งแบบทแยงมุม (diagonal argument) แสดงให้เห็นว่าการสมมติว่ามีตัวตัดสินการหยุดทำงานจะนำไปสู่ความขัดแย้ง ดังนั้นจึงไม่มีอัลกอริทึมใดที่สามารถตัดสินการหยุดทำงานสำหรับโปรแกรมและอินพุตทั้งหมดได้

การลดรูปและการถ่ายทอดคุณสมบัติการตัดสินใจไม่ได้

หากปัญหาที่ตัดสินใจไม่ได้ที่ทราบแล้วสามารถลดรูปไปสู่ปัญหาเป้าหมายได้ ปัญหาเป้าหมายนั้นก็ตัดสินใจไม่ได้เช่นกัน ทำให้การลดรูปเป็นเครื่องมือมาตรฐานสำหรับการสร้างคุณสมบัติการตัดสินใจไม่ได้

ทฤษฎีบทของ Rice

คุณสมบัติที่ไม่ใช่เรื่องเล็กน้อยทุกประการของฟังก์ชันที่คำนวณโดยโปรแกรมนั้นตัดสินใจไม่ได้ ดังนั้นโดยพื้นฐานแล้วคุณสมบัติเชิงพฤติกรรมที่น่าสนใจของโปรแกรมจึงไม่สามารถตัดสินใจได้ด้วยอัลกอริทึม

Clinical relevance

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

History

Turing และ Church ได้แสดงให้เห็นในปี 1936 ว่า Entscheidungsproblem ซึ่งเป็นคำถามเกี่ยวกับอัลกอริทึมที่ตัดสินความถูกต้องของตรรกะอันดับหนึ่ง (first-order validity) นั้นไม่สามารถแก้ไขได้ โดยมีปัญหาการหยุดทำงานเป็นหัวใจสำคัญของข้อโต้แย้งของ Turing Rice ได้สรุปปรากฏการณ์นี้ในปี 1953 และต่อมาได้มีการพิสูจน์ว่าปัญหาเฉพาะ เช่น ปัญหาคำสำหรับกลุ่มโดย Novikov และปัญหาที่สิบของ Hilbert โดย Matiyasevich นั้นตัดสินใจไม่ได้

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

เหตุใดคอมพิวเตอร์ที่เร็วกว่าจึงไม่สามารถแก้ปัญหาการหยุดทำงานได้?

การตัดสินใจไม่ได้ไม่ขึ้นอยู่กับความเร็วหรือหน่วยความจำ: ข้อโต้แย้งแบบทแยงมุมได้ตัดความเป็นไปได้ของอัลกอริทึมใดๆ ออกไป ไม่ว่าจะได้รับเวลาเท่าใดก็ตาม ปัญหาการหยุดทำงานไม่สามารถแก้ไขได้ในทางหลักการ ไม่ใช่แค่ในทางปฏิบัติเท่านั้น

เราสามารถบอกได้หรือไม่ว่าโปรแกรมจะหยุดทำงานหรือไม่?

บ่อยครั้งที่สามารถทำได้สำหรับโปรแกรมบางโปรแกรม โดยการวิเคราะห์หรือการรันโปรแกรม สิ่งที่เป็นไปไม่ได้คืออัลกอริทึมเดียวที่ตอบคำถามได้อย่างถูกต้องสำหรับทุกโปรแกรมและทุกอินพุต ดังนั้นตัวตรวจสอบการสิ้นสุดในทางปฏิบัติจึงประสบความสำเร็จเฉพาะในคลาสที่จำกัด หรืออาจไม่สามารถให้คำตอบได้