ผลต่างระหว่างรุ่นของ "พูดคุย:ปัญหาการยุติการทำงาน"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
→{{ARTICLEPAGENAME}}#ร่างบทพิสูจน์: clarify |
ล re |
||
บรรทัด 46:
:: เดี๋ยวว่าง ๆ จะมาตอบนะครับ แต่ผมดูบทสนทนาของคุณ Ans กับ Jittat ไม่ได้อะครับ คิดว่าเนื่องมาจากบทสนนทนาดังกล่าวไม่ได้ตั้งค่าให้บุคคลจากสาธารณะสามารถเข้าได้ --[[ผู้ใช้:Nullzero|Nullzero]] ([[คุยกับผู้ใช้:Nullzero|คุย]]) 17:43, 30 ธันวาคม 2562 (+07)
::: {{ping|Nullzero}} ทุก account ใน fb, ถ้า login จะเปิดอ่านบทสนทนานั้นได้ครับ, ถ้าไม่มี account เดี๋ยวเอามาแปะให้ครับ --[[ผู้ใช้:Ans|Ans]] ([[คุยกับผู้ใช้:Ans|คุย]]) 17:51, 30 ธันวาคม 2562 (+07)
::::* ผมมี account ครับ แต่เจอหน้า "Sorry, this content isn't available right now"
::::* ตอบกลับเรื่อง "ตย. ของผมไม่เหมือน ตย. 2 ที่คณยกมาครับ": โอเคครับ ไม่เหมือนกันอย่างที่คุณว่าจริง ๆ แหละครับ ต้องขอโทษด้วยครับถ้าทำให้สับสน แต่ประเด็นที่ผมต้องการจะสื่อคือ การเอาข้อมูลนำเข้าอันหนึ่ง (<math>I</math>) มาทำงานบน Turing machine อันหนึ่ง (<math>M</math>) จะได้ผลลัพธ์ที่เหมือนกันเสมอ (นั่นคือ การทำงานเป็น[[ฟังก์ชัน (คณิตศาสตร์)|ฟังก์ชันทางคณิตศาสตร์]]) สาเหตุเพราะว่าในสถานะหนึ่ง ๆ ของ Turing machine (<math>q</math>) บนเทปข้อมูลหนึ่ง ๆ (<math>s</math>) และตำแหน่งหัวอ่านเทปหนึ่ง ๆ (<math>i</math>) ถ้า <math>q</math> ไม่ใช่สถานะจบ จะมีเพียงแค่วิธีเดียวในการเปลี่ยนสถานะไปเป็นสถานะถัดไป (ตามนิยามของ Turing machine) จึงสรุปแบบชุ่ย ๆ ได้ว่า <math>M</math> และ <math>I</math> จะนำไปสู่ผลลัพธ์ที่เหมือนกันเสมอ (ถ้าอยากให้รัดกุมก็อาจจะใช้[[การพิสูจน์เชิงคณิตศาสตร์#การพิสูจน์โดยการอุปนัยเชิงคณิตศาสตร์|การอุปนัย]]ในการพิสูจน์อะไรทำนอง "หลังจาก <math>M</math> ทำงานด้วยข้อมูล <math>I</math> ไปได้แล้ว <math>z</math> ขั้น แล้วอยู่ในสถานะรวม <math>(q_1, s_1, i_1)</math> และ <math>(q_2, s_2, i_2)</math> จะได้ว่า <math>q_1 = q_2, s_1 = s_2, i_1 = i_2</math> สำหรับทุก ๆ จำนวนเต็ม <math>z \ge 0</math>") เพราะฉะนั้นแล้ว ในบทความ <code>halt(t, t)</code> จึงมีค่าที่เป็นไปได้เพียงค่าเดียวครับ
::::* ตอบกลับเรื่อง "ลองดู สมการ x^2 = 1 สิครับ, มันก็ทำให้ x มี 2 ค่าได้ เช่นกัน": คือถ้าคุณ Ans พยายาม "แก้สมการ" ก็จะได้ว่าทั้ง true และ false เป็น feasible solution ของ <code>halt(t, t)</code> แหละครับ แต่
::::*# นี่ก็ไม่ได้ทำให้ความจริงที่ว่า <code>halt(t, t)</code> เป็นไปได้เพียงแค่ค่าเดียวเท่านั้นเปลี่ยนไป
::::*# อีกประการคือ การแก้สมการอาจไม่ได้ characterize ผลลัพธ์อย่างเที่ยงตรงเสมอไป ขอยกตัวอย่างอีกอันคือ ถามว่า[[เศษส่วนต่อเนื่อง]] <math>1 + \frac{1}{1 + \frac{1}{1 + \dots}}</math> มีค่าเป็นเท่าไหร่ เรารู้แน่ ๆ ว่าการหาค่านิพจน์หนึ่ง ๆ ในคณิตศาสตร์ (ไม่ใช่การแก้สมการ ซึ่งอาจมีหลายคำตอบ อันนี้แค่หาค่าตรง ๆ เลย) จะมีเพียงแค่ค่าเดียวเท่านั้น แต่เวลาเราพยายาม formulate ปัญหาเป็นสมการแล้วพยายามแก้ อาจจะได้หลายค่าออกมาก็ได้:
::::*#: <math>\begin{align}
x & = 1 + \frac{1}{1 + \frac{1}{1 + \dots}} \\
x - 1 & = \frac{1}{1 + \frac{1}{1 + \dots}} \\
\frac{1}{x - 1} & = 1 + \frac{1}{1 + \dots} \\
& = x \\
1 & = x (x - 1) \\
0 & = x^2 - x - 1 \\
\end{align}</math>
::::*#: และได้ว่าเซตคำตอบคือ <math>\{\phi, -1/\phi\}</math> จาก <math>\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}</math> โดยที่ φ คือ[[อัตราส่วนทอง]] แต่นี่ไม่ได้แปลว่าค่าของ <math>1 + \frac{1}{1 + \frac{1}{1 + \dots}}</math> เป็นทั้ง <math>-1/\phi</math> และ <math>\phi</math> ในเวลาเดียวกัน
::::* ตอบกลับเรื่อง "check_result": มันมี[[:en:Rice's theorem|ทฤษฎีบทของไรซ์]] ที่บอกว่า "investigate the code of program P with input I (without running the code) if it would return false" เป็นปัญหาที่ไม่สามารถตัดสินได้เช่นกันครับ ในกรณีนี้ สามารถพิสูจน์ได้ง่าย ๆ เลยคือ ''สมมุติถ้าเราสามารถสร้างโปรแกรม'' <code>is_false (P, I)</code> ที่สามารถ "investigate the code of program P with input I (without running the code) if it would return false" ได้ ผมสามารถสร้างโปรแกรม <code>halt</code> ดังต่อไปนี้
'''function''' halt (P, I)
'''function''' Q (P, I)
execute P on I
'''return''' '''false'''
if is_false(Q, I) = '''true'''
'''return''' '''true'''
'''else'''
'''return''' '''false'''
* สำหรับ ''P'' และ ''I'' ใด ๆ ถ้าเอา ''P'' มาทำงานบน ''I'' แล้วการทำงานยุติ โปรแกรม ''Q'' ก็ต้องคืนค่า '''false''' แปลว่า <code>is_false(Q, I)</code> ก็ต้องตอบ '''true''' ทำให้ <code>halt (P, I)</code> ตอบ '''true''' ซึ่งถูกต้อง
* สำหรับ ''P'' และ ''I'' ใด ๆ ถ้าเอา ''P'' มาทำงานบน ''I'' แล้วการทำงานไม่ยุติ โปรแกรม ''Q'' ก็ต้องไม่ยุติการทำงาน แปลว่า <code>is_false(Q, I)</code> ก็ต้องตอบ '''false''' ทำให้ <code>halt (P, I)</code> ตอบ '''false''' ซึ่งถูกต้องอีกเช่นกัน
แปลว่าเราสามารถสร้าง <code>halt</code> ได้ ภายใต้สมมุติฐานว่าเราสามารถสร้าง <code>is_false</code> ได้ แต่เรารู้จากทฤษฎีบทของปัญหาการยุติการทำงานว่า ''เราไม่มีทางที่จะสร้าง <code>halt</code> ได้'' นั่นหมายความว่าสมมุติฐานที่ว่า ''เราสามารถสร้าง <code>is_false</code> ได้'' ไม่ถูกต้อง นั่นคือ ''เราไม่สามารถสร้าง <code>is_false</code> ได้''
กล่าวคือ คำถามที่คุณถามเกี่ยวกับ <code>check_result</code> จริง ๆ แล้วแทบจะเป็นคำถามเดียวกันกับ คำถามก่อนหน้าเกี่ยวกับ <code>trouble</code> ไม่ได้เป็นคำถามที่ง่ายกว่า และคำตอบก็เหมือนกัน คือ ในเมื่อ <code>check_result</code> (หรือ <code>trouble</code>) เรียกใช้โปรแกรมที่ไม่สามารถเขียนได้ จึงทำให้โปรแกรม <code>check_result</code> (หรือ <code>trouble</code>) ไม่มีอยู่จริง จึงป่วยการที่จะวิเคราะห์ว่ามันทำงานอย่างไรครับ --[[ผู้ใช้:Nullzero|Nullzero]] ([[คุยกับผู้ใช้:Nullzero|คุย]]) 11:11, 31 ธันวาคม 2562 (+07)
| |||