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

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมถึงข้อโต้แย้งแบบทแยง (diagonalization argument) ที่สร้างภาวะที่ไม่สามารถตัดสินใจได้ของปัญหาการหยุดทำงาน ความแตกต่างระหว่างปัญหาที่ตัดสินใจได้ (decidable), ปัญหาที่รับรู้ได้ (recognizable) และปัญหาที่รับรู้ร่วมได้ (co-recognizable) ทฤษฎีของไรซ์ (Rice's theorem) ที่แสดงให้เห็นว่าคุณสมบัติเชิงความหมายที่ไม่ใช่เรื่องเล็กน้อยทั้งหมดของโปรแกรมไม่สามารถตัดสินใจได้ และรายการของปัญหาที่ไม่สามารถตัดสินใจได้ตามธรรมชาติในสาขาตรรกศาสตร์ คณิตศาสตร์ และวิทยาการคอมพิวเตอร์

Core questions

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

Key theories

ภาวะที่ไม่สามารถตัดสินใจได้ของปัญหาการหยุดทำงาน

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

ทฤษฎีของไรซ์

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

Clinical relevance

เนื่องจากการหยุดทำงานและคุณสมบัติเชิงพฤติกรรมที่ไม่ใช่เรื่องเล็กน้อยทั้งหมดของโปรแกรม (ตามทฤษฎีของไรซ์) ไม่สามารถตัดสินใจได้ จึงไม่มีเครื่องมือใดที่สามารถตรวจจับการวนซ้ำไม่สิ้นสุด (infinite loops) ตรวจสอบความถูกต้องตามอำเภอใจ หรือวิเคราะห์โปรแกรมทุกโปรแกรมได้อย่างสมบูรณ์ ดังนั้น เครื่องมือวิเคราะห์และตรวจสอบแบบสถิต (static analyzers and verifiers) จึงต้องประมาณค่า ยอมรับการแจ้งเตือนที่ผิดพลาด หรือจำกัดขอบเขตการทำงานของตน

History

ทัวริงได้สร้างภาวะที่ไม่สามารถตัดสินใจได้ของปัญหาการหยุดทำงานและปัญหาการตัดสินใจสำหรับตรรกศาสตร์ในปี 1936 โดยใช้ข้อโต้แย้งแบบทแยงที่ได้รับแรงบันดาลใจจากคันเตอร์ (Cantor) และเกอเดล (Gödel) ไรซ์ได้พิสูจน์การสรุปผลที่ครอบคลุมของเขาในปี 1953 และในช่วงหลายทศวรรษต่อมา ปัญหาตามธรรมชาติหลายอย่าง รวมถึงปัญหาที่สิบของฮิลเบิร์ต (Hilbert's tenth problem) เกี่ยวกับสมการไดโอแฟนไทน์ (Diophantine equations) ได้รับการแสดงให้เห็นว่าไม่สามารถตัดสินใจได้

Key figures

• Alan Turing
• Henry Gordon Rice
• Emil Post
• Alonzo Church

Seminal works

• turing1937
• sipser2013

Frequently asked questions

เหตุใดเราจึงไม่สามารถเพียงแค่รันโปรแกรมเพื่อดูว่ามันหยุดทำงานหรือไม่?

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

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

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