Halting problem เป็นชื่อปัญหาที่ classic มากทางด้าน algorithm

Halt หมายถึง การหยุด ดังนั้น Halting problem คือ ปัญหาเกี่ยวกับการหยุด ปัญหาข้อนี้มีที่มาจาก มีผู้ตั้งปัญหาว่า เราสามารถสร้างเครื่องที่สามารถบอกได้ว่า algorithm ใดๆ จะสามารถให้คำตอบได้หรือไม่ ตัวอย่างของการไม่ได้คำตอบ เช่น ติด loop, หาไปเรื่อยๆไม่มีที่สิ้นสุด เป็นต้น การให้คำตอบแปลว่า algorithm จบการทำงาน (halt) นั่นเอง

Alan Turing เป็นผู้ prove ว่า ไม่สามารถทำเครื่องนี้ขึ้นมาได้ โดยใช้วิธี contradiction

นิยามเบื้องต้น
halt คือ algorithm ให้คำตอบได้ ว่า จริง หรือ เท็จ
loop คือ algorithm ให้คำตอบไม่ได้

1. สมมติ ให้เครื่องนี้มีอยู่จริง โดยรับ input เป็น "algorithm" กับ "input ของ algorithm" แล้วให้ผลลัพธ์เป็น จริง หรือ เท็จ หรือเขียนเป็น function ได้ว่า f(a,b) เมื่อ f แทนเครื่อง, a แทน algorithm, b แทน input สำหรับ algorithm
   ตัวอย่าง ให้ input เป็น algorithm A และ input สำหรับ algorithm เป็น B
   เครื่องจะตอบว่า "จริง" เมื่อ ใส่ input B ให้ algorithm A แล้ว ได้คำตอบ (halt)
   เครื่องจะตอบว่า "เท็จ" เมื่อ ใส่ input B ให้ algorithm A แล้ว ไม่ได้คำตอบ (loop)
   
2. สมมติเพิ่มใหม่ ให้มี เครื่อง g ที่รับ input เป็น algorithm x ให้ output เป็น จริง เมื่อ f(x,x) ให้ output เป็น เท็จ นอกจากนั้น เครื่องจะวน loop
   ตัวอย่าง ให้ input เป็น algorithm A
   เครื่องจะตอบว่า "จริง" เมื่อ ใส่ A ให้ algorithm A แล้ว ไม่ได้คำตอบ (f(A,A) = false)
   เครื่องจะตอบว่า "loop" เมื่อ ใส่ A ให้ algorithm A แล้ว ได้คำตอบ (f(A,A) = true)
   
   จะเห็นได้ว่า เครื่อง g นี้ ทำงานคล้ายๆกับเครื่อง f แต่จำกัดตัว "input ของ algorithm x" ให้เป็นตัว algorithm x เองเท่านั้น และให้ผลตรงข้ามกับ เครื่อง f
   
3. การทำงานของทั้งเครื่อง f และ g เขียนแทนได้ด้วย algorithm f และ g ตามลำดับ
   เราจะทดลองให้ input ของเครื่อง g เป็น algorithm g เอง
   ถ้า f(g,g) เป็น เท็จ เครื่อง g จะตอบว่า จริง แต่ จากนิยามของเครื่อง f บอกว่า เครื่อง f จะตอบผลออกมาเป็นเท็จ เมื่อ algorithm ซึ่งในที่นี้ คือ g เป็น loop ในขณะที่ g ตอบเราออกมาได้ว่า จริง แสดงว่า g นั้น halt ดังนั้น เกิดการขัดแย้งขึ้นที่ g
   ถ้า f(g,g) ให้ผลเป็น จริง เครื่อง g จะ loop แต่ จากนิยามของเครื่อง f บอกว่า เครื่อง f จะตอบผลออกมาเป็นจริง เมื่อ algorithm ซึ่งในที่นี้คือ g นั้น halt แต่ g กลับวน loop จึงเกิดการขัดแย้งขึ้นที่ g
   
   เนื่องจากเกิดการขัดแย้งขึ้นทั้ง f(g,g) เป็นเท็จ และ f(g,g) เป็นจริง แสดงว่าที่สมมติข้างต้นว่ามี เครื่อง f นั้น ไม่เป็นจริง จึงสรุปได้ว่า "ไม่สามารถสร้าง algorithm ที่แก้ปัญหานี้ (halting problem ได้"

ปัญหาใดๆ ที่เข้าในลักษณะของ halting problem จะเป็นปัญหาที่ไม่สามารถหา algorithm มาแก้ได้ ซึ่งหมายถึงว่า เราไม่สามารถเขียนโปรแกรมให้แก้ปัญหาเหล่านี้ได้นั่นเอง

ข้อมูลเพิ่มเติม http://en.wikipedia.org/wiki/Halting_problem