พูดคุย:ปัญหาการยุติการทำงาน

ปัญหาการยุติการทำงาน#ร่างบทพิสูจน์

ต่อให้เปลี่ยน function trouble เป็นแบบไม่สร้างเงื่อนไขที่ขัดแย้ง,

 function trouble (string s)
     if halt (s, s) = false
         loop forever
     else
         stop

เราก็บอกไม่ได้อยู่ดีว่า trouble(t) นั้นหยุดหรือไม่. คือ halt(t, t) จะคืนค่า true ก็ได้, คืนค่า false ก็ได้, เป็นค่าที่ถูกต้องได้ทั้งคู่. ซึ่งมันก็เป็นผลที่ประหลาดอยู่ดี, เพราะ halt(t, t) ควรจะคืนค่าที่ถูกต้องได้เพียงค่าเดียวไม่ใช่เหรอ, ไม่น่าจะมีค่าที่ถูกต้องทั้งสองค่าพร้อมกันได้. --Ans (คุย) 13:01, 12 ธันวาคม 2562 (+07)

@Ans: ยังสงสัยอยู่หรือเปล่าครับ? เห็น User:Jittat บอกว่าคุณพยายามติดต่อหาเขาไปแล้วทางเฟซบุ๊ก คำอธิบายของผมเองมีอยู่สองส่วน

1. คำถามนี้น่าสนใจ แต่ไม่มีประโยชน์ที่จะหาคำตอบ ประเด็นของบทความนี้คือ มันเป็นไปไม่ได้ที่จะสร้าง Turing machine ที่แก้ halting problem นั่นคือ เราพิสูจน์ได้แล้วว่าวัตถุนี้ไม่มีอยู่จริง เพราะฉะนั้น การจะถามว่า Turing machine นี้มีคุณลักษณะเป็นอย่างไรจึงไร้ประโยชน์ เหมือนคำถามว่า "ให้ X เป็นจำนวนนับที่อยู่ระหว่าง 1 กับ 2 (1 < X < 2) แล้ว X เป็นจำนวนคู่หรือจำนวนคี่" ประเด็นคือ X มันไม่มีอยู่จริง การถามว่าเป็นจำนวนคู่หรือจำนวนคี่จึงไร้ประโยชน์
2. ลองเปรียบเทียบกับกรณีอื่นเผื่อจะทำให้หายงงนะครับ ลองนึกถึงข้อความคาดการณ์ของก็อลท์บัคดูเล่น ๆ สมมุติว่าถ้าข้อความคาดการณ์เป็นจริง ให้ตัวแปร x เท่ากับ 0 ไม่อย่างนั้นให้ตัวแปร x เท่ากับ 1 สิ่งที่เป็นจริงแน่ ๆ คือตัวแปร x มีค่าไม่ 0 ก็ 1 แต่เราไม่รู้ว่ามันคืออะไร (ณ ปัจจุบันนี้) ทีนี้ ลองพิจารณาโปรแกรม if (x == 0) { return 2; } else { return 2; } โดยโปรแกรมนี้เป็นโปรแกรมที่คืนค่า 2 ทีนี้จะสังเกตได้ว่า เป็นความจริงว่าไม่ว่า x จะมีค่าเป็นอะไร โปรแกรมข้างบนก็คืนค่า 2 ที่ถูกต้อง แต่ก็เป็นความจริงด้วยว่า x เป็นไปได้เพียงแค่ค่าเดียว คือไม่ 0 ก็ 1 การที่โปรแกรมข้างบนคืนค่า 2 ที่ถูกต้องไม่ว่า x จะมีค่าเป็นอะไรก็ตามไม่ได้แปลว่า x มีหลายค่าได้ --Nullzero (คุย) 18:04, 18 ธันวาคม 2562 (+07)

@Nullzero: เราไม่มีทางรู้หรอกครับว่า การหาคำตอบของปัญหาบางอย่าง ต่อไปจะมีประโยชน์หรือไม่. กรณีนี้เป็นการลองทำอีกแบบนึงดูว่าผลจะเป็นอย่างไร, หรือ สามารถพิสูจน์ด้วยวิธีอื่นอีกแบบได้หรือไม่. --Ans (คุย) 16:46, 30 ธันวาคม 2562 (+07)

ตย. ของผมไม่เหมือน ตย. 2 ที่คณยกมาครับ. ของคุณนั้น ค่า x ยังขึ้นกับค่าอื่น ที่ให้ค้นหาต่อไปได้ว่า x มีค่าใด, แต่ ตย. ของผม halt(t, t) มันไม่ได้ขึ้นกับค่าอื่นอีกแล้ว, มันมีค่าให้ค้นหาได้เพียงเท่าที่เห็น, ซึ่งเมื่อลองไล่โปรแกรมนี้แบบ ad-hoc จะพบว่ามันจะวนอยู่ที่เดิม, และ พบว่า ไม่มีทาง และ ไม่มีวัน และ ไม่มีหนทางอื่น อีกเลย ที่จะบอกได้เลยว่า มันมีค่าเท่าใด.

สำหรับกรณีที่ว่ามีหลายค่าได้มั้ย ก็ลองดู สมการ x^2 = 1 สิครับ, มันก็ทำให้ x มี 2 ค่าได้ เช่นกัน. --Ans (คุย) 17:01, 30 ธันวาคม 2562 (+07)

ถ้าลองเปลี่ยนเป็นปัญหาง่ายๆ แบบนี้,

 function check_result (t)
     // note: investigate the result of t(t) without running it
     investigate the code of program t with input t (without running the code) if it would return false then
         return false
     else
         return true

ถามว่า check_result(check_result) คืนค่า true หรือ false? --Ans (คุย) 17:18, 30 ธันวาคม 2562 (+07)

external discussion with jittat --Ans (คุย) 17:25, 30 ธันวาคม 2562 (+07)

เดี๋ยวว่าง ๆ จะมาตอบนะครับ แต่ผมดูบทสนทนาของคุณ Ans กับ Jittat ไม่ได้อะครับ คิดว่าเนื่องมาจากบทสนนทนาดังกล่าวไม่ได้ตั้งค่าให้บุคคลจากสาธารณะสามารถเข้าได้ --Nullzero (คุย) 17:43, 30 ธันวาคม 2562 (+07)

@Nullzero: ทุก account ใน fb, ถ้า login จะเปิดอ่านบทสนทนานั้นได้ครับ, ถ้าไม่มี account เดี๋ยวเอามาแปะให้ครับ --Ans (คุย) 17:51, 30 ธันวาคม 2562 (+07)

@Ans:

• ผมมี account ครับ แต่เจอหน้า "Sorry, this content isn't available right now"
• ตอบกลับเรื่อง "ตย. ของผมไม่เหมือน ตย. 2 ที่คณยกมาครับ": โอเคครับ ไม่เหมือนกันอย่างที่คุณว่าจริง ๆ แหละครับ ต้องขอโทษด้วยครับถ้าทำให้สับสน แต่ประเด็นที่ผมต้องการจะสื่อคือ การเอาข้อมูลนำเข้าอันหนึ่ง ($I$) มาทำงานบน Turing machine อันหนึ่ง ($M$) จะได้ผลลัพธ์ที่เหมือนกันเสมอ (นั่นคือ การทำงานเป็นฟังก์ชันทางคณิตศาสตร์) สาเหตุเพราะว่าในสถานะหนึ่ง ๆ ของ Turing machine ($q$) บนเทปข้อมูลหนึ่ง ๆ ($s$) และตำแหน่งหัวอ่านเทปหนึ่ง ๆ ($i$) ถ้า $q$ ไม่ใช่สถานะจบ จะมีเพียงแค่วิธีเดียวในการเปลี่ยนสถานะไปเป็นสถานะถัดไป (ตามนิยามของ Turing machine) จึงสรุปแบบชุ่ย ๆ ได้ว่า $M$ และ $I$ จะนำไปสู่ผลลัพธ์ที่เหมือนกันเสมอ (ถ้าอยากให้รัดกุมก็อาจจะใช้การอุปนัยในการพิสูจน์อะไรทำนอง "หลังจาก $M$ ทำงานด้วยข้อมูล $I$ ไปได้แล้ว $z$ ขั้น แล้วอยู่ในสถานะรวม $(q_{1},s_{1},i_{1})$ และ $(q_{2},s_{2},i_{2})$ จะได้ว่า $q_{1}=q_{2},s_{1}=s_{2},i_{1}=i_{2}$ สำหรับทุก ๆ จำนวนเต็ม $z\geq 0$") เพราะฉะนั้นแล้ว ในบทความ halt(t, t) จึงมีค่าที่เป็นไปได้เพียงค่าเดียวครับ
• ตอบกลับเรื่อง "ลองดู สมการ x^2 = 1 สิครับ, มันก็ทำให้ x มี 2 ค่าได้ เช่นกัน": คือถ้าคุณ Ans พยายาม "แก้สมการ" ก็จะได้ว่าทั้ง true และ false เป็น feasible solution ของ halt(t, t) แหละครับ แต่
  1. นี่ก็ไม่ได้ทำให้ความจริงที่ว่า halt(t, t) เป็นไปได้เพียงแค่ค่าเดียวเท่านั้นเปลี่ยนไป
  2. อีกประการคือ การแก้สมการอาจไม่ได้ characterize ผลลัพธ์อย่างเที่ยงตรงเสมอไป ขอยกตัวอย่างอีกอันคือ ถามว่าเศษส่วนต่อเนื่อง $1+{\frac {1}{1+{\frac {1}{1+\dots }}}}$ มีค่าเป็นเท่าไหร่ เรารู้แน่ ๆ ว่าการหาค่านิพจน์หนึ่ง ๆ ในคณิตศาสตร์ (ไม่ใช่การแก้สมการ ซึ่งอาจมีหลายคำตอบ อันนี้แค่หาค่าตรง ๆ เลย) จะมีเพียงแค่ค่าเดียวเท่านั้น แต่เวลาเราพยายาม formulate ปัญหาเป็นสมการแล้วพยายามแก้ อาจจะได้หลายค่าออกมาก็ได้:

     ${\begin{aligned}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{aligned}}$

     และได้ว่าเซตคำตอบคือ $\{\phi ,-1/\phi \}$ จาก ${\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}$ โดยที่ φ คืออัตราส่วนทอง แต่นี่ไม่ได้แปลว่าค่าของ $1+{\frac {1}{1+{\frac {1}{1+\dots }}}}$ เป็นทั้ง $-1/\phi$ และ $\phi$ ในเวลาเดียวกัน

• ตอบกลับเรื่อง "check_result": มันมีทฤษฎีบทของไรซ์ ที่บอกว่า "investigate the code of program P with input I (without running the code) if it would return false" เป็นปัญหาที่ไม่สามารถตัดสินได้เช่นกันครับ ในกรณีนี้ สามารถพิสูจน์ได้ง่าย ๆ เลยคือ สมมุติถ้าเราสามารถสร้างโปรแกรม is_false (P, I) ที่สามารถ "investigate the code of program P with input I (without running the code) if it would return false" ได้ ผมสามารถสร้างโปรแกรม halt ดังต่อไปนี้

 function halt (P, I)
     function Q (I)
         execute P on I
         return false
     
     if is_false(Q, I) = true
         return true
     else
         return false

• สำหรับ P และ I ใด ๆ ถ้าเอา P มาทำงานบน I แล้วการทำงานยุติ โปรแกรม Q ก็ต้องคืนค่า false แปลว่า is_false(Q, I) ก็ต้องตอบ true ทำให้ halt (P, I) ตอบ true ซึ่งถูกต้อง
• สำหรับ P และ I ใด ๆ ถ้าเอา P มาทำงานบน I แล้วการทำงานไม่ยุติ โปรแกรม Q ก็ต้องไม่ยุติการทำงาน แปลว่า is_false(Q, I) ก็ต้องตอบ false ทำให้ halt (P, I) ตอบ false ซึ่งถูกต้องอีกเช่นกัน

แปลว่าเราสามารถสร้าง halt ได้ ภายใต้สมมุติฐานว่าเราสามารถสร้าง is_false ได้ แต่เรารู้จากทฤษฎีบทของปัญหาการยุติการทำงานว่า เราไม่มีทางที่จะสร้าง halt ได้ นั่นหมายความว่าสมมุติฐานที่ว่า เราสามารถสร้าง is_false ได้ ไม่ถูกต้อง นั่นคือ เราไม่สามารถสร้าง is_false ได้

กล่าวคือ คำถามที่คุณถามเกี่ยวกับ check_result จริง ๆ แล้วแทบจะเป็นคำถามเดียวกันกับ คำถามก่อนหน้าเกี่ยวกับ trouble ไม่ได้เป็นคำถามที่ง่ายกว่า และคำตอบก็เหมือนกัน คือ ในเมื่อ check_result (หรือ trouble) เรียกใช้โปรแกรมที่ไม่สามารถเขียนได้ จึงทำให้โปรแกรม check_result (หรือ trouble) ไม่มีอยู่จริง จึงป่วยการที่จะวิเคราะห์ว่ามันทำงานอย่างไรครับ --Nullzero (คุย) 11:19, 31 ธันวาคม 2562 (+07)

ขอสรุปสั้น ๆ ตามนี้นะครับ

1. คำถามว่าเอา $M$ มาทำงานด้วยข้อมูล $I$ แล้ว $M$ จะยุติการทำงานหรือเปล่า เป็นคำถามที่ valid โดยที่ $M$ ต้องเป็น Turing machine และ $I$ ต้องเป็นข้อมูลนำเข้า และคำตอบก็เป็นไปได้แค่ 2 อย่างเท่านั้น คือยุติการทำงาน หรือไม่ยุติการทำงาน
2. แต่ทฤษฎีบทของปัญหาการยุติการทำงาน ระบุว่า เราไม่สามารถเขียนโปรแกรมที่จะแก้ปัญหายุติการทำงานสำหรับ Turing machine และข้อมูลนำเข้าใด ๆ ได้ นั่นคือ halt ที่เป็นโปรแกรม หรือ Turing machine ไม่มีอยู่จริง
3. แปลว่าโปรแกรมที่เรียกใช้ halt ในฐานะที่เป็นโปรแกรม หรือ Turing machine ก็ไม่มีอยู่จริงเช่นเดียวกัน
4. แปลว่า trouble หรือ การเอา trouble มาเข้ารหัสเป็น string t ก็ไม่มีอยู่จริง
5. ฉะนั้น ในขณะที่คำถามว่าเอา $M$ มาทำงานด้วยข้อมูล $I$ แล้ว $M$ จะยุติการทำงานหรือเปล่า เป็นคำถามที่ valid การถามว่าเอา trouble มาทำงานด้วย t แล้ว trouble จะยุติการทำงานหรือเปล่า จึงผิด เพราะ trouble ไม่ใช่ Turing machine --Nullzero (คุย) 12:35, 31 ธันวาคม 2562 (+07)

ก็เพราะ turing machine + input เดิม คืนค่าๆ เดียวเสมอ ไงครับ, ผมถึงได้บอกว่า การที่ trouble(t) แบบที่ไม่ขัดแย้ง คืนค่าที่ถูกต้องได้ 2 ค่า เป็นสิ่งที่ให้ผลประหลาด (ทำให้มันไม่น่าจะเป็น turing machine ได้). เมื่อมันให้ผลประหลาดที่ให้ค่าถูกต้อง 2 ค่า โดยไม่มีเงื่อนไขอื่นใดที่จำกัดมันให้เหลือค่าเดียวอีกเลย, การใช้ trouble(t) แบบไม่สร้างเงื่อนไขขัดแย้งนี้ ก็อาจเป็นการพิสูจน์ได้เหมือนกันว่า halt() ไม่มีอยู่จริง. --Ans (คุย) 12:05, 3 มกราคม 2563 (+07)

ผมไม่ได้บอกว่า x^2 = 1 มีค่าได้ 2 ค่าในเวลาเดียวกัน, เพียงแต่ว่ามันมีค่าที่ถูกต้องได้ 2 ค่า แต่ไม่ได้เป็นค่านั้นพร้อมๆ กัน. และ trouble(t) แบบที่ว่า ก็มีค่าที่ถูกต้องได้ 2 ค่า, และไม่มีทางเลือกเอาค่าใดค่าหนึ่ง, เพราะ ถ้าเลือกเอาเพียงค่าหนึ่ง, ก็หมายความว่าอีกค่าหนึ่งผิด, แต่อีกค่าหนึ่งมันก็ไม่ผิด, เพราะมันพิสูจน์แล้วว่าอีกค่าหนึ่งมันก็ถูก, จะไปบอกว่ามันผิดได้ยังไง. (จริงๆ ก็ไม่ได้หมายความว่าอีกค่าหนึ่งจะถูกเสมอไป, เพราะในขณะที่เราสมมุติว่าค่าแรกถูก, มันก็จะทำให้ค่าหลังผิด แน่นอนอยู่แล้ว, แต่มันจะผิดก็เฉพาะกรณีที่เราสมมุติว่าค่าแรกถูกไง, แต่กรณีที่เราสมมุติว่าค่าแรกผิด มันก็ทำให้ค่าหลังถูกต้องได้. แต่ประเด็นคือ แล้วไอ้การสมมุติค่าแรกเนี่ย แล้วเมื่อไหร่จะเลิกสมมุติได้ซะที. ปกติการสมมุติก็อาจจะทำเพื่อหาความขัดแย้ง เพื่อตัดค่าที่เป็นไปไม่ได้ออก, แต่นี่สมมุติค่าไหนมันก็ตัดค่าไหนออกไปไม่ได้เลย, และก็ไม่มีวิธีอื่นที่จะตัดค่าใดค่าหนึ่งออกไปได้อีกแล้ว. ที่ผมยก ตย. x^2 = 1, มันก็ไม่มีวันตัดค่าใดค่าหนึ่งออกไปได้, เว้นเสียแต่ว่าจะมีเงื่อนไขเพิ่มเติม เช่น มีสมการเพิ่มอีกสมการ เช่น x < 0 มันก็ทำให้ตัดเหลือค่าเดียวได้, แต่ trouble(t) แบบนั้นมันไม่ได้มีเงื่อนไขอื่น ที่จะตัดค่าที่เป็นไปได้ออกอีกแล้ว(เช่น สมการที่นิยาม halt() เพิ่มเติมจากนิยามเดิม, ซึ่งทำไม่ได้เพราะนิยามเพิ่มเติมจะทำให้ halt() ผิดไปจากนิยามเดิมที่ต้องการพิสูจน์)) --Ans (คุย) 12:42, 3 มกราคม 2563 (+07)

ถ้าผมจะเปลี่ยน check_result() ให้ง่ายกว่านั้น เป็น,

 function check_result ()
     investigate the code of program check_result (without running the code) if it would return false then
         return false
     else
         return true

ผม hard code ให้มัน check เฉพาะ check_result() เท่านั้น, ถามว่า check_result() คืนค่า true หรือ false? --Ans (คุย) 13:06, 3 มกราคม 2563 (+07)

ผมเปิด fb เป็น public นะ, ลองให้คนไม่ใช่ friend เปิด เค้าก็อ่าน comment ข้างในได้, แปลกที่ทำไมบางนอ่านไม่ได้ --Ans (คุย) 13:09, 3 มกราคม 2563 (+07)