นักวิจัยเข้าใกล้ขีดจำกัดของการคำนวณด้วย Busy Beaver ตัวที่ห้า

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

  • บทนำ

    • เมื่อ 40 ปีก่อน นักวิทยาการคอมพิวเตอร์รวมตัวกันที่ดอร์ทมุนด์ ประเทศเยอรมนี เพื่อแข่งขันกันตามหา Busy Beaver ตัวที่ห้า
    • Busy Beaver คือโปรแกรมคอมพิวเตอร์แบบเรียบง่ายที่ใช้เวลาทำงานยาวนานมาก
    • โปรแกรมเหล่านี้เกี่ยวข้องกับปัญหาคณิตศาสตร์ที่มีชื่อเสียงซึ่งยังไม่ได้รับการแก้ และมีที่มาจากปัญหาเก่าแก่ในวิทยาการคอมพิวเตอร์
    • เมื่อ 2 ปีก่อน Tristan Stérin นักศึกษาปริญญาโทได้เริ่ม Busy Beaver Challenge และมีผู้ร่วมสมทบมากกว่า 20 คนจากทั่วโลกเข้าร่วม
    • วันนี้ ทีมได้ยืนยันค่าของ BB(5) ว่าเป็น 47,176,870

  • จะหยุดหรือไม่หยุด

    • โปรแกรม Busy Beaver ถูกเขียนเป็นคำสั่งสำหรับคอมพิวเตอร์เชิงทฤษฎีที่เรียกว่าเครื่องทัวริง
    • เครื่องทัวริงทำการคำนวณโดยอ่านและเขียน 0 กับ 1 บนเทปที่ไม่มีที่สิ้นสุด
    • ปัญหาในการทำนายว่าเครื่องทัวริงจะหยุดหรือทำงานไปตลอดกาลเรียกว่า halting problem
    • halting problem ไม่มีวิธีแก้ทั่วไป และนั่นยิ่งทำให้การล่า Busy Beaver น่าสนใจมากขึ้น

  • การปรากฏตัวของบีเวอร์

    • นักคณิตศาสตร์ Tibor Radó เป็นผู้คิดค้นเกม Busy Beaver ในปี 1962
    • เครื่องทัวริงที่ทำงานได้นานที่สุดในแต่ละชุดกฎจะถูกเรียกว่า Busy Beaver
    • BB(n) หมายถึงจำนวนขั้นตอนที่เครื่อง Busy Beaver ซึ่งมีกฎจำนวน n ข้อต้องใช้ก่อนจะหยุดทำงาน

  • ฝูงบีเวอร์ของ Brady

    • Allen Brady พัฒนาเทคนิคการล่า Busy Beaver ในช่วงทศวรรษ 1960 และกำหนดค่าของ Busy Beaver ตัวที่สี่ได้ในปี 1974
    • BB(4) ได้รับการยืนยันว่าเป็นเครื่องที่หยุดหลังจาก 107 ขั้นตอน

  • บีเวอร์ตัวที่ห้า

    • การล่าครั้งใหญ่ครั้งแรกเพื่อหา Busy Beaver ตัวที่ห้าเริ่มต้นขึ้นในการแข่งขันที่ดอร์ทมุนด์ปี 1984
    • ในปี 1989 Heiner Marxen ค้นพบเครื่องที่หยุดหลังจาก 47,176,870 ขั้นตอน
    • ในปี 2003 Georgi Georgiev ยุติการล่า BB(5) โดยยังเหลือเครื่องทัวริงที่ยังตัดสินไม่ได้ 43 เครื่อง

  • เรียกนักล่าทุกคน

    • Tristan Stérin เริ่ม Busy Beaver Challenge ในปี 2022 และมีผู้ร่วมสมทบจากทั่วโลกเข้าร่วม
    • Shawn Ligocki เข้าร่วมทีมในปี 2022 และมีส่วนสำคัญอย่างมาก
    • Justin Blanchard พัฒนาวิธี closed tape language ซึ่งเป็นหนึ่งในเทคนิคที่ทรงพลังที่สุดของทีม

  • การเข้าใกล้สัตว์ประหลาด

    • Skelet #1 และ #17 เป็นเครื่องที่ยากเป็นพิเศษ และทีมได้ผสานแนวคิดหลากหลายเพื่อแก้ปัญหาเหล่านี้
    • ในเดือนพฤษภาคม 2023 ผู้ร่วมสมทบนิรนามชื่อ mxdys ได้ทำ proof ใน Coq เสร็จสมบูรณ์

  • ถิ่นที่บีเวอร์เดินเพ่นพ่าน

    • ทีมกำลังเขียนบทความวิชาการอย่างเป็นทางการ และบางคนก็กำลังพยายามตามหา Busy Beaver ตัวถัดไป
    • BB(6) ดูเหมือนจะแก้ได้ยาก เนื่องจากมีปัญหาที่คล้ายกับข้อคาดการณ์ Collatz

ความเห็นของ GN⁺

  • บทความนี้นำเสนอตัวอย่างที่น่าสนใจของการสำรวจขีดจำกัดของวิทยาการคอมพิวเตอร์
  • Busy Beaver Challenge แสดงให้เห็นถึงความสำคัญของงานวิจัยแบบร่วมมือกัน
  • การแก้ BB(5) มีความหมายอย่างมากต่อชุมชนวิทยาการคอมพิวเตอร์และคณิตศาสตร์
  • โครงการที่มีลักษณะคล้ายกันคือการวิจัยข้อคาดการณ์ Collatz
  • เมื่อต้องนำเทคโนโลยีใหม่หรือโอเพนซอร์สมาใช้ ความร่วมมือและการทำซ้ำได้เป็นสิ่งสำคัญ

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

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

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

  • มีการแชร์ความคิดเห็นเกี่ยวกับบล็อกโพสต์ของ Scott Aaronson

    • มีลิงก์ไปยังเธรดก่อนหน้าที่เกี่ยวข้อง

  • มีรูปแบบย่อยของปัญหา Busy Beaver อยู่หลากหลาย

    • มีรูปแบบที่ใช้แลมบ์ดาแคลคูลัส
    • มีรูปแบบที่อธิบายด้วยความซับซ้อนของ Kolmogorov

  • มีการแชร์เรื่องราวของวิศวกรคนหนึ่งที่ลาออกจากงานเพื่อศึกษาปัญหา Busy Beaver

    • มีการสงสัยว่าวิศวกรคนนี้คือ mxdys หรือไม่

  • มีการกล่าวถึงการพิสูจน์ด้วย Coq

    • มีการตั้งข้อสังเกตว่าอาจไม่ใช่การพิสูจน์ที่จัดระเบียบตั้งแต่ต้น แต่เป็นการพิสูจน์ที่ถูกจัดระเบียบเป็นครั้งแรก

  • มีความเห็นว่าบทความต้นฉบับของ Tibor Radó เกี่ยวกับ Busy Beaver อ่านง่ายและน่าสนุก

    • มีการให้ลิงก์ไปยังเวอร์ชันสมัยใหม่ของบทความ

  • ปัญหาการหยุดทำงานของโปรแกรมเครื่องทัวริงแบบ 5 สถานะ 2 สีได้รับการแก้แล้ว

    • มีการตั้งคำถามว่าสามารถนำไปใช้กับกรณี 2 สถานะ 4 สีได้หรือไม่

  • มีการกล่าวถึงความเข้าใจผิดที่ว่ามนุษย์สามารถแก้ปัญหาการหยุดทำงานได้ด้วยสัญชาตญาณ

  • มีการแชร์ประสบการณ์การเขียนโปรแกรมเพื่อแก้ปัญหา Cutting Stock ในโปรเจ็กต์ส่วนตัว

    • ใช้วิธีเพิ่มประสิทธิภาพที่คล้ายกับโปรแกรมของ Brady

  • มีความเห็นว่าการสามารถพิสูจน์ได้ว่าโปรแกรมเครื่องทัวริงแบบ 5 สถานะหยุดทำงานหรือไม่นั้นเป็นเรื่องของโชคพอสมควร

  • ตามบล็อกโพสต์ของ Scott Aaronson มีเครื่องทัวริงแบบ 5 สถานะอยู่ 16,679,880,978,201 เครื่อง

    • มีการสงสัยว่ามีกี่เปอร์เซ็นต์ในจำนวนนี้ที่หยุดทำงาน

  • มีการแชร์ค่าของฟังก์ชัน Busy Beaver

    • พิสูจน์แล้วว่า BB(5) มีค่าเป็น 47,176,870
    • BB(6) มีค่าอย่างน้อย 10^10^...^10 (หอคอยเลขยกกำลัง 15 ชั้น)