ผลต่างระหว่างรุ่นของ "ปัญหาการยุติการทำงาน"

ใน[[ทฤษฎีการคำนวณได้]]นั้น '''ปัญหาการยุติการทำงาน''' ({{Lang-en|Halting problem}}) คือ[[ปัญหาการตัดสินใจ]]ที่ถามว่า

[[แอลัน ทัวริง]] (Alan Turing) พิสูจน์ในปี ค.ศ. 1936 ว่า ไม่มีขั้นตอนวิธีที่แก้ปัญหาการยุติการทำงานสำหรับข้อมูลป้อนเข้าใด ๆ ได้ทั้งหมดบน[[เครื่องจักรทัวริ่งทัวริง]] จึงกล่าวว่าปัญหาการยุติการทำงานนี้[[ปัญหาการตัดสินใจ#การตัดสินได้และการรับได้|ไม่สามารถตัดสินได้]]

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

การที่เรา[[การไม่สามารถตัดสินได้|ไม่สามารถตัดสิน]]ปัญหาการยุติการทำงานได้ มีผลสืบเนื่องทำให้เราไม่มีทางมีวิธีทั่วไปในการตัดสินได้ว่าถ้อยแถลง (statement) เกี่ยวกับ[[จำนวนธรรมชาติ]]ในเป็นจริงหรือไม่ ทั้งนี้เนื่องจาก[[ประพจน์]]ที่ระบุว่าขั้นตอนวิธีหนึ่ง ๆ จะยุติการทำงานเมื่อรับข้อมูลป้อนเข้าหนึ่ง ๆ นั้นสามารถเขียนให้อยู่ในรูปของถ้อยแถลงเกี่ยวกับจำนวนธรรมชาติที่เทียบเท่ากันได้ ดังนั้น ขั้นตอนวิธีที่ตัดสินความจริงของถ้อยแถลงเกี่ยวกับจำนวนธรรมชาติ จะสามารถนำมาใช้เพื่อตัดสินปัญหาการยุติการทำงานได้ ข้อสรุปก็คือ ขั้นตอนวิธีดังกล่าวจึงไม่สามารถมีอยู่จริง เพราะว่าเราทราบว่าไม่มีขั้นตอนวิธีใดที่ตัดสินปัญหาการยุติการทำงานได้ สังเกตว่าการแสดงการไม่สามารถตัดสินได้ดังกล่าวใช้วิธีการลดทอนปัญหาสู่ปัญหาการยุติการทำงาน

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

บทพิสูจน์ใช้[[การพิสูจน์แบบการสร้างข้อขัดแย้ง]] (หรือที่เรียกใน[[ภาษาละติน]]ว่า reductio ad absurdum) โดยสมมติว่า''มี''ขั้นตอนวิธีที่อธิบายได้ด้วยโปรแกรม <code>halt (a, i) </code> ที่ซึ่งตัดสินว่าขั้นตอนวิธีที่ระบุด้วยข้อความ ''a'' นั้นจะยุติการทำงานเมื่อได้รับข้อมูลป้อนเข้าเป็นข้อความ ''i'' เราจะแสดงว่าข้อสมมติดังกล่าวจะทำให้เกิดข้อขัดแย้ง, และนั่นหมายความว่าโปรแกรม <code>halt</code> นั้น''ไม่สามารถมีตัวตน''อยู่ได้

สมมติให้โปรแกรม <code>halt (a, i) </code> คืนค่า <code>'''จริง'''</code> ถ้าขั้นตอนวิธีที่ระบุด้วยข้อความ ''a'' ยุติการทำงานเมื่อรับ ''i'' เป็นข้อมูลป้อนเข้า และคืนค่า <code>'''เท็จ'''</code> ในกรณีอื่น ๆ ด้วยโปรแกรมดังกล่าว เราสามารถสร้างโปรแกรมอีกโปรแกรมหนึ่ง ชื่อว่า <code>trouble (s) </code> ดังนี้ดังต่อไปนี้:

โปรแกรมนี้ <code>trouble</code> รับข้อความ ''s'' และเรียกโปรแกรม <code>halt</code> โดยใช้ข้อมูลป้อนเข้าทั้งที่เป็นข้อความที่ระบุขั้นตอนวิธี ''a'' และข้อความที่จะใช้เป็นข้อมูลป้อนเข้า ''i'' ของขั้นตอนวิธีดังกล่าวเป็น ''s'' กล่าวอย่างไม่เป็นทางการก็คือ <code>trouble</code> ถาม <code>halt</code> ว่าขั้นตอนวิธี ''s'' เมื่อรับข้อความที่ระบุตัวขั้นตอนวิธีเองแล้ว จะยุติการทำงานหรือไม่ จากนั้น ถ้า <code>halt (s,s) </code> คืนค่า '''เท็จ''' โปรแกรม <code>trouble</code> จะจบการทำงาน แต่ถ้า <code>halt (s,s) </code> คืนค่า '''จริง''' โปรแกรม <code>trouble</code> จะวนรอบไม่รู้จบ

* [[กราฟแสดงการไหลของส่วนควบคุม]] (control flow graph) สามารถใช้เพื่อจำแนกโปรแกรมอย่างรวดเร็วออกเป็นโปรแกรมที่ (1) ไม่มีการวนซ้ำ, (2) มีการวนซ้ำแบบง่าย (จึงยุติการทำงาน) , (3) มีการวนซ้ำแบบไม่ง่าย (กรณีไม่สามารถระบุอะไรได้) , หรือ (4) ทำงานซ้ำอย่างไม่รู้จบ

* [[แอลัน ทัวริง]] (Alan Turing) , ''On computable numbers, with an application to the Entscheidungs problem'', Proceedings of the London Mathematical Society, Series 2, 42 (1936) , pp 230-265. [http://www.abelard.org/turpap2/tp2-ie.asp online version] ในงานวิจัยชิ้นนี้ ทัวริงนิยาม[[เครื่องจักรทัวริง]] วางรูปแบบปัญหาการยุติการทำงาน และแสดงว่าปัญหานี้ (รวมทั้ง [[Entscheidungs problem]]) เป็นปัญหาที่ไม่สามารถแก้ได้