ปัญหาการยุติการทำงาน

จากวิกิพีเดีย สารานุกรมเสรี

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

ในทฤษฎีการคำนวณได้นั้น ปัญหาการยุติการทำงาน (Halting problem) คือปัญหาการตัดสินใจ (decision problem) ที่สามารถอย่างไม่เป็นทางการได้ดังนี้

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

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

เนื้อหา 1 ความสำคัญและผลสืบเนื่อง 2 ร่างบทพิสูจน์ 3 ดูเพิ่ม 4 อ้างอิง

[แก้] ความสำคัญและผลสืบเนื่อง

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

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

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

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

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

[แก้] ร่างบทพิสูจน์

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

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

 function trouble (string s)
     if halt (s, s) = false
         stop
     else
         loop forever

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

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

trouble (t) จะยุติการทำงานหรือไม่?

ลองดูความเป็นไปได้ทั้งสองกรณี:

1. สมมติว่า trouble (t) ยุติการทำงาน กรณีเดียวที่เป็นไปได้ก็คือ halt (t,t) คืนค่า เท็จ แต่นี่หมายความว่า trouble (t) จะทำงานไม่รู้จบ ดังนั้นเราได้ข้อขัดแย้ง
2. สมมติว่า trouble (t) ทำงานไม่รู้จบ เนื่องจาก halt (t,t) ทำงานจบเสมอ ดังนั้นสาเหตุเดียวที่ทำให้ trouble (t) ทำงานไม่รู้จบก็คือ halt (t,t) คืนค่า จริง อย่างไรก็ตามนี่หมายความว่า trouble (t) จะต้องมีการยุติการทำงาน เราจึงได้ข้อขัดแย้งอีกเช่นกัน

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

[แก้] ดูเพิ่ม

• กราฟแสดงการไหลของส่วนควบคุม (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. online version ในงานวิจัยชิ้นนี้ ทัวริงนิยามเครื่องจักรทัวริง วางรูปแบบปัญหาการยุติการทำงาน และแสดงว่าปัญหานี้ (รวมทั้งEntscheidungsproblem) เป็นปัญหาที่ไม่สามารถแก้ได้