ความเข้าใจผิดแบบซอมบี้ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี

 (scottaaronson.blog)
1 คะแนน โดย GN⁺ 2024-07-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

ความเข้าใจผิดแบบซอมบี้ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี

บทนำ

  • ในตำรา "Introduction to the Theory of Computation" ของ Michael Sipser มีโจทย์แบบฝึกหัดที่สมบูรณ์แบบข้อหนึ่ง
  • โจทย์: "เมื่อฟังก์ชัน f:{0,1}*→{0,1} คืนค่า 1 หรือ 0 ตามการมีอยู่ของพระเจ้า f สามารถคำนวณได้หรือไม่?"
  • คำตอบ: "ได้ f สามารถคำนวณได้" (เพราะฟังก์ชันค่าคงที่สามารถคำนวณได้)

แนวคิดของการคำนวณได้

  • การคำนวณได้เป็นแนวคิดที่ใช้กับฟังก์ชันหรืออนุกรมอนันต์
  • ไม่ได้ใช้กับคำถามใช่/ไม่ใช่แบบเฉพาะข้อ หรือจำนวนเต็มเดี่ยว ๆ
  • ความยากในการเขียนโปรแกรมไม่เกี่ยวข้องกับการคำนวณได้

ปัญหา P กับ NP

  • ปัญหา P กับ NP เป็นคำถามใช่/ไม่ใช่แบบเฉพาะข้อ
  • ความเป็น NP-hard ใช้กับฟังก์ชันหรือภาษา
  • ปัญหา P กับ NP ไม่อาจเป็นสิ่งที่คำนวณไม่ได้หรือเป็น NP-hard ได้

ฟังก์ชัน Busy Beaver

  • ฟังก์ชัน Busy Beaver คำนวณไม่ได้
  • จำนวนเต็มเดี่ยว ๆ อย่าง BB(6) คำนวณได้
  • สิ่งที่คำนวณไม่ได้คือฟังก์ชัน BB ทั้งหมด

ความเข้าใจผิดแบบซอมบี้ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี

  • การนำแนวคิดที่ใช้กับอนุกรมอนันต์และฟังก์ชันไปใช้ผิดกับจำนวนเต็มเดี่ยว ๆ และปัญหาเปิด
  • การสับสนระหว่างความคำนวณไม่ได้ของปัญหาการหยุดทำงานกับทฤษฎีบทความไม่สมบูรณ์ของเกอเดล

คำถามถึงผู้อ่าน

  • ถามผู้อ่านว่าจะป้องกันความเข้าใจผิดแบบซอมบี้นี้ได้อย่างไร

สรุปโดย GN⁺

  • บทความนี้กล่าวถึงความเข้าใจผิดที่เกิดขึ้นบ่อยในวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • การคำนวณได้เป็นแนวคิดที่ใช้กับฟังก์ชันหรืออนุกรมอนันต์ ไม่ใช่กับจำนวนเต็มเดี่ยว ๆ หรือคำถามใช่/ไม่ใช่
  • ปัญหา P กับ NP เป็นคำถามเฉพาะข้อ จึงไม่เกี่ยวกับแนวคิดความเป็น NP-hard
  • ฟังก์ชัน Busy Beaver คำนวณไม่ได้ แต่ค่ารายตัวสามารถคำนวณได้
  • บทความนี้จะช่วยให้เข้าใจแนวคิดพื้นฐานของวิทยาการคอมพิวเตอร์เชิงทฤษฎีได้ชัดเจนยิ่งขึ้น

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-11
ความเห็นจาก Hacker News

  • การมีอยู่ของอัลกอริทึมที่คำนวณ Kolmogorov complexity เกี่ยวข้องกับความเป็นอนันต์

    • ไม่มีอัลกอริทึมที่สามารถคำนวณ Kolmogorov complexity ของสตริงที่มีความยาวตามอำเภอใจได้
    • แต่มีอัลกอริทึมที่คำนวณ Kolmogorov complexity ของสตริงที่มีความยาวน้อยกว่า n ได้
    • ทำได้ด้วยการสร้างตาราง lookup ขนาดมหึมาสำหรับสตริงที่เป็นไปได้ทั้งหมด
    • ปัญหาแบบจำกัดสามารถแก้ได้ด้วยโปรแกรมเสมอ แต่ปัญหาแบบอนันต์ไม่เป็นเช่นนั้น

  • ความเห็นว่าคณิตศาสตร์เชิงสร้างสอดคล้องกับสัญชาตญาณของผู้คนมากกว่า

    • ยังไม่มีหลักฐานว่ามีโปรแกรมสำหรับปัญหา P=NP อยู่จริง
    • Mark Braverman พิสูจน์ว่า Julia set (กำลังสอง) ทุกอันสามารถคำนวณได้ แต่ไม่สามารถคำนวณได้แบบสม่ำเสมอ
    • ในคณิตศาสตร์เชิงสร้าง จะมีการแบ่งระนาบเชิงซ้อนออกเป็นหลายบริเวณ และพิสูจน์ว่า Julia set ภายในแต่ละบริเวณเป็น compact

  • เหตุผลที่เข้าใจความตัดสินไม่ได้ของปัญหาหยุดทำงานได้ยาก

    • ในบรรดาโปรแกรม "return true" และ "return false" จะมีหนึ่งตัวที่ให้คำตอบถูกต้องเสมอ
    • ความสามารถในการตัดสินจะกลายเป็นตัดสินไม่ได้ก็ต่อเมื่อขยายไปยังชุดเครื่องจักร/อินพุตที่เป็นอนันต์

  • การอธิบายปัญหาที่ต้องใช้ modal logic

    • คำถามว่า "f คำนวณได้หรือไม่?" เป็นคำถามที่ผิดในเชิง modal
    • คำถามว่า "f จะคำนวณได้ไหม?" แม่นยำกว่า
    • สิ่งนี้คล้ายกับ compiler directive หรือ pragma

  • การนิยามฟังก์ชัน f ที่ทำให้สับสน

    • ฟังก์ชัน f ไม่ได้แยกกรณีตามค่าของ "God exists"
    • ไม่ว่า f จะเป็น 0 หรือ 1 ก็ยังคำนวณได้
    • ความสับสนเกิดจากการผลัก free variable เข้าไปเป็นเงื่อนไขของการแยกกรณี

  • ความแตกต่างของความหมายระหว่างการตัดสินได้ การคำนวณได้ และการมีอยู่

    • ความหมายต่างกันในบริบททางวิชาการกับบริบทในชีวิตประจำวัน
    • ตัวเลขขนาดใหญ่มากมีอยู่และคำนวณได้ในเชิงวิชาการ แต่ในทางปฏิบัติไม่สามารถใส่ลงไปในเอกภพได้

  • ปัญหาของคำถามที่เกี่ยวกับ "God exists"

    • ยังไม่ชัดเจนว่า "God exists" เป็นจริงหรือเท็จ
    • นี่เป็นปัญหาที่เกิดขึ้นเมื่อผสมภาษาธรรมชาติกับคณิตศาสตร์

  • เหตุผลที่วิทยาการคอมพิวเตอร์เชิงทฤษฎีและทฤษฎีความซับซ้อนยากสำหรับนักศึกษาปริญญาตรี CS

    • คำอย่าง NP-hard มักถูกแทนที่ด้วยอุปมาและจินตนาการแบบสาธารณะ

  • ข้อบ่นเกี่ยวกับวิธีเน้นข้อความของบล็อก

    • สีพื้นหลังของข้อความที่เลือกไม่เปลี่ยน ทำให้ไม่เป็นธรรมชาติในการใช้งาน

  • ข้อเสนอให้แทนที่ "God exists" ด้วยประพจน์ทางคณิตศาสตร์อื่น

    • ควรกำหนดให้ชัดเจนว่า "God exists" เป็นจริงหรือเท็จ