ผลต่างระหว่างรุ่นของ "204512/บรรยาย 13"
| แถว 8: | แถว 8: | ||
=== ปัญหา Halting Problem === | === ปัญหา Halting Problem === | ||
| − | '''Description''' | + | '''Description :''' ให้โปรแกรม P และ input X ถามว่า P(x) ทำงานจบหรือไม่ |
จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้ | จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้ | ||
| − | '''Proof''' | + | '''Proof :''' สมมติให้มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ |
โดยมี Q(program P, input X) จะ return True ถ้า P(x) halt และ return False เมื่อ P(x) ติด loop | โดยมี Q(program P, input X) จะ return True ถ้า P(x) halt และ return False เมื่อ P(x) ติด loop | ||
เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้ | เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้ | ||
| แถว 23: | แถว 23: | ||
จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่ | จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่ | ||
Case1 : Q'(Q') halt | Case1 : Q'(Q') halt | ||
| − | + | นั่นคือ Q(Q',Q') = False --> Q'(Q') = False คือ Q'(Q') ติด loop *Contradict* | |
Case2 : Q'(Q') loop | Case2 : Q'(Q') loop | ||
| − | + | นั่นคือ Q(Q',Q') = Ture --> Q'(Q') = True คือ Q'(Q') halt *Contradict* | |
พบว่าเกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้ | พบว่าเกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้ | ||
เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง | เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง | ||
รุ่นแก้ไขเมื่อ 14:40, 22 กันยายน 2550
จดบันทึกคำบรรยายโดย:
- นายเกรียงไกร ลิ่มทอง รหัส : 50653732
- นายธีรวัฒน์ ตออำนวย รหัส : 50653815
เนื้อหา
NP Completeness
ปัญหา Halting Problem
Description : ให้โปรแกรม P และ input X ถามว่า P(x) ทำงานจบหรือไม่ จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้
Proof : สมมติให้มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ โดยมี Q(program P, input X) จะ return True ถ้า P(x) halt และ return False เมื่อ P(x) ติด loop เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้
Procedure Q'(program P)
If Q(P, P) then
loop forever
Else
halt
จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่ Case1 : Q'(Q') halt นั่นคือ Q(Q',Q') = False --> Q'(Q') = False คือ Q'(Q') ติด loop *Contradict* Case2 : Q'(Q') loop นั่นคือ Q(Q',Q') = Ture --> Q'(Q') = True คือ Q'(Q') halt *Contradict* พบว่าเกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้ เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง
Note: ปัญหา Halting Problem ถูกพิสูจน์โดย Alan Turing
