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

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

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

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

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

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

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

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

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

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

ถึงแม้คอมพิวเตอร์ในยุคปัจจุบันจะเป็นเครื่องจักรที่มีหน่วยความจำจำกัดประเภทหนึ่ง ทำให้สามารถแก้ปัญหาการยุติการทำงานได้ในทางทฤษฎี จำนวนสถานะที่แตกต่างกันทั้งหมดของคอมพิวเตอร์นั้นมีมากกว่า 21,000,000 สถานะ ซึ่งมากมายมหาศาล เวลาในการแก้ไขปัญหานี้จึงมากมายมหาศาลด้วยเช่นกัน (สามารถเปรียบเทียบว่าเวลาในการแก้ไขปัญหานี้ ทำให้ช่วงเวลาอายุของเอกภพไร้ความหมายได้เลย)

## ร่างบทพิสูจน์
บทพิสูจน์ใช้การพิสูจน์แบบการสร้างข้อขัดแย้ง (หรือที่เรียกในภาษาละตินว่า 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

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

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

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

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

# สมมติว่า `trouble (⌜trouble⌝)` ยุติการทำงาน: หากพิจารณาการทำงานของโปรแกรม `trouble` จะพบว่า `halt (⌜trouble⌝,⌜trouble⌝)` ต้องคืนค่า**เท็จ** แต่ถ้า `halt` ทำงานถูกต้องก็หมายความว่า `trouble (⌜trouble⌝)` จะทำงานไม่รู้จบ ทำให้เกิดข้อขัดแย้งกับสมมุติฐานว่า `trouble (⌜trouble⌝)` ยุติการทำงาน
# สมมติว่า `trouble (⌜trouble⌝)` ทำงานไม่รู้จบ: เนื่องจาก `halt (⌜trouble⌝,⌜trouble⌝)` ทำงานจบเสมอ สาเหตุเดียวที่ทำให้ `trouble (⌜trouble⌝)` ทำงานไม่รู้จบก็คือ `halt (⌜trouble⌝,⌜trouble⌝)` ต้องคืนค่า**จริง** อย่างไรก็ตามนี่หมายความว่า `trouble (⌜trouble⌝)` จะต้องมีการยุติการทำงาน ทำให้เกิดข้อขัดแย้งกับสมมุติฐานว่า `trouble (⌜trouble⌝)` ทำงานไม่รู้จบ

เนื่องจากทั้งสองกรณีทำให้เกิดข้อขัดแย้งที่ล้วนเป็นไปไม่ได้ ดังนั้นสามารถสรุปได้ว่าข้อสมมติเริ่มต้นแรกสุด (*มี*ขั้นตอนวิธีที่อธิบายได้ด้วยโปรแกรม `halt (a, i) `) นั้นไม่ถูกต้อง กล่าวคือ*ไม่มี*โปรแกรม `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 ในงานวิจัยชิ้นนี้ ทัวริงนิยามเครื่องจักรทัวริง วางรูปแบบปัญหาการยุติการทำงาน และแสดงว่าปัญหานี้ (รวมทั้ง Entscheidungs problem) เป็นปัญหาที่ไม่สามารถแก้ได้

หมวดหมู่:ทฤษฎีการคำนวณ
หมวดหมู่:ปัญหาทางคณิตศาสตร์
หมวดหมู่:ทฤษฎีการคำนวณได้