Halting Problem

ปัญหา Halting Problem เนี่ย เป็นปัญหาสุดคลาสสิกอันนึงสำหรับคนที่เรียนคอมพิวเตอร์ โจทย์มีอยู่ว่า

เราจะสร้างโปรแกรม (หรือคำสั่ง) ชื่อว่า H ที่รับ input 2 ตัว คือ

1. X = โปรแกรม (คือ source code หรือ object code หรือ อะไรก็ได้)
2. Y = input (ทั้งหมด) ของโปรแกรม X

และมี output เป็น

1. "หยุด" ถ้า X(Y) หยุดการทำงานในเวลาจำกัด
2. "ไม่หยุด" ถ้า X(Y) ไม่หยุดการทำงาน (ก็คือ ติด loop หนะ)

โดยที่ H(X, Y) ทำงานเสร็จในเวลาจำกัด (นับเป็นจำนวนคำสั่งก็ได้) ได้รึเปล่า?

H(X, Y) ทำงานเสร็จในเวลาจำกัด แปลว่า H(H, (X, Y)) ให้คำตอบเป็น "หยุด" เสมอน่ะนะ

คำตอบของปัญหานี้ ก็มีคนตอบได้มานานแล้วหละ แต่วิธีการหาคำตอบเนี่ย น่าสนใจ ... เค้าใช้วิธีพิสูจน์แบบขัดแย้ง แบบนี้...

สมมติว่า H(X, Y) มีอยู่จริง เราจะสร้างโปรแกรม L(X) แบบนี้ได้

L(X)

• If H(X, X) = "หยุด", then loop forever.
• Else (if H(X, X) = "ไม่หยุด"), do nothing.

แปลว่า ถ้า H(X, X) ให้คำตอบเป็น "หยุด" H(L, X) จะเป็น "ไม่หยุด" แต่ถ้า H(X, X) ให้คำตอบเป็น "ไม่หยุด" H(L, X) จะเป็น "หยุด"

คราวนี้ เราก็ลองคิดดูว่า H(L, L) มันจะเป็นอะไร ...

ถ้า H(L, L) = "หยุด"

1. ตามนิยามของ H: L(L) ต้องหยุด
2. ตามนิยามของ L: แปลว่ามันไปตกที่ "Else, ..." ดังนั้น H(L, L) = "ไม่หยุด"

ถ้า H(L, L) = "ไม่หยุด"

1. ตามนิยามของ H: L(L) ต้องไม่หยุด
2. ตามนิยามของ L: แปลว่ามันไปตกที่ "If ..., then ..." ดังนั้น H(L, L) = "หยุด"

จะเห็นว่า ไม่ว่าจะสมมติให้ H(L, L) เป็นอะไร มันก็จะเกิดความขัดแย้งเสมอ แสดงว่า จริง ๆ แล้วเราไม่สามารถสร้าง H ได้นั่นเอง

ความพยายามสร้าง H(X, Y) ที่ใกล้เคียงที่สุด ก็คือ

1. H(X, Y) ตอบว่า "หยุด" ในเวลาจำกัด ถ้า X(Y) หยุดการทำงานในเวลาจำกัด
2. H(X, Y) ไม่สามารถตอบอะไรได้ และไม่หยุดการทำงาน ถ้า X(Y) ไม่หยุดการทำงาน

ซึ่ง H(X, Y) แบบนี้ ก็ไม่ต่างจากการปล่อยให้ X(Y) ทำงานเฉย ๆ

โยงกลับไปที่ภาษาอันดับหนึ่งนิดนึง เคยพูดไว้ในตอนท้ายเรื่อง ตรรกศาสตร์: Unification แล้วว่า

"จะว่าไป มันก็เทียบได้กับ halting problem น่ะแหละ (เทียบได้จริง ๆ นะ เหมือนกัันเด๊ะเลย)"

ก็เลยเอามาเทียบกันให้ดูอีกที ว่าทำไมมันเหมือนกัน ... อันนี้คือ ความเป็นจริงเกี่ยวกับการพิสูจน์ว่า ประพจน์เป็นจริงรึเปล่า เมื่อมีกฎต่าง ๆ ให้

"ถ้าประพจน์ที่ต้องการพิสูจน์เป็นจริง เมื่อได้ประพจน์ว่าง (จาก resolution) เราก็จะรู้ แต่ถ้ามันไม่จริง เราก็อาจจะต้องทำไปเรื่อย ๆ เรื่อย ๆ ... เหมือนกับ ไม่มีทางรู้เลย ว่ามันเป็นจริงรึเปล่า"

ส่วนในกรณีของ H(X, Y) ที่สามารถสร้างได้ ...

"ถ้า X(Y) หยุดการทำงาน เราก็จะได้คำตอบจาก H(X, Y) แต่ถ้า X(Y) ไม่หยุดการทำงาน H(X, Y) ก็จะทำงานไปเรื่อย ๆ ... ไม่มีทางรู้ว่ามันจะหยุดรึเปล่า"

จบละ