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

:''กำหนด[[ขั้นตอนวิธี]]และ[[ข้อมูลป้อนเข้า]]ให้ จงหาว่าขั้นตอนวิธีเมื่อทำงานกับข้อมูลป้อนเข้าดังกล่าวแล้ว จะยุติการทำงาน (ทำงานเสร็จสิ้น) หรือจะทำงานไปเรื่อยๆเรื่อย ๆ ไม่มีที่สิ้นสุด''

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

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

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

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

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

เนื่องจากโปรแกรมใดๆใด ๆ สามารถเขียนระบุเป็นข้อความได้ ดังนั้นสำหรับโปรแกรม <code>trouble</code> เอง เราจะมีข้อความ ''t⌜trouble⌝'' ที่ระบุโปรแกรมดังกล่าว พิจารณาคำถามต่อไปนี้:

: <code>trouble (t⌜trouble⌝) </code> จะยุติการทำงานหรือไม่?

# สมมติว่า <code>trouble (t⌜trouble⌝) </code> ยุติการทำงาน กรณีเดียวที่เป็นไปได้ก็คือ <code>halt (t⌜trouble⌝,t⌜trouble⌝) </code> คืนค่า '''เท็จ''' แต่นี่หมายความว่า <code>trouble (t⌜trouble⌝) </code> จะทำงานไม่รู้จบ ดังนั้นเราได้ข้อขัดแย้ง

# สมมติว่า <code>trouble (t⌜trouble⌝) </code> ทำงานไม่รู้จบ เนื่องจาก <code>halt (t⌜trouble⌝,t⌜trouble⌝) </code> ทำงานจบเสมอ ดังนั้นสาเหตุเดียวที่ทำให้ <code>trouble (t⌜trouble⌝) </code> ทำงานไม่รู้จบก็คือ <code>halt (t⌜trouble⌝,t⌜trouble⌝) </code> คืนค่า '''จริง''' อย่างไรก็ตามนี่หมายความว่า <code>trouble (t⌜trouble⌝) </code> จะต้องมีการยุติการทำงาน เราจึงได้ข้อขัดแย้งอีกเช่นกัน

เนื่องจากทั้งสองกรณีทำให้เกิดข้อขัดแย้งที่ล้วนเป็นไปไม่ได้ ดังนั้นสามารถสรุปได้ว่าข้อสมมติเริ่มต้นที่ใช้นั้นไม่ถูกต้อง กล่าวคือไม่มีโปรแกรม <code>halt</code> หรือขั้นตอนวิธีใดๆใด ๆ ที่สามารถตัดสินปัญหาการยุติการทำงานได้

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

ปัญหาการยุติการทำงานเป็นปัญหาที่สามารถตัดสินใจได้ (นั่นคือสามารถแก้ได้) บนเครื่องจักรที่มีหน่วยความจำจำกัด (linear bounded automata; LBAs) เนื่องจากจำนวนสถานะในเครื่องจักรเหล่านี้มีจำกัด เมื่อทำงานไปเรื่อยๆเรื่อย ๆ โดย[[หลักรังนกพิราบ]] จะมีจุดหนึ่งที่สถานะในหน่วยความจำเหมือนกัน นั่นคือถ้าหากเราปล่อยให้โปรแกรมทำงานต่อไปอีก สถานะก็จะมาซ้ำที่จุดเดิมอีกไปเรื่อยๆเรื่อย ๆ ดังนั้นเมื่อมาถึงจุดๆจุด ๆ นั้น เราก็สามารถบอกได้ทันทีว่าโปรแกรมนี้ ไม่ยุติการทำงาน