ปัญหาการยุติการทำงาน - วิกิพีเดีย

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

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

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

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

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

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

ปัญหานี้มีความสำคัญเพราะว่าเป็นปัญหาแรกที่พิสูจน์ได้ว่าเป็นปัญหาที่ไม่สามารถตัดสินได้ หลังจากนั้นปัญหาในกลุ่มนี้อีกหลายปัญหาก็ถูกระบุออกมา วิธีพิสูจน์ทั่วไปทำโดยใช้เทคนิคการลดทอนปัญหา (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` หรืออัลกอริทึมใดๆ ที่สามารถตัดสินปัญหาการยุติการทำงานได้

## [แก้] รูปแบบทางการของปัญหาการยุติการทำงาน

## [แก้] ความสัมพันธ์กับ Incompleteness Theorem ของ Gödel

## [แก้] มนุษย์สามารถแก้ปัญกาการยุติการทำงานได้หรือไม่?

## [แก้] ปัญหาที่มีคำตอบบางส่วน

## [แก้] เนื้อหาอื่นๆ

- กราฟแสดงการไหลของส่วนควบคุม (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) เป็นปัญหาที่ไม่สามารถแก้ได้
- Wiki:HaltingProblem

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%9B/%E0%B8%B1/%E0%B8%8D/%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%A2%E0%B8%B8%E0%B8%95%E0%B8%B4%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%97%E0%B8%B3%E0%B8%87%E0%B8%B2%E0%B8%99.html".

หมวดหมู่: การคำนวณได้ | ตรรกศาสตร์

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Català
- Česky
- Deutsch
- English
- Español
- فارسی
- Suomi
- Français
- עברית
- 日本語
- 한국어
- Nederlands
- Polski
- Русский
- Svenska
- 中文