BusyBeaver(6) ใหญ่มหาศาลจริง ๆ

 (scottaaronson.blog)
2 คะแนน โดย GN⁺ 2025-06-29 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ค่าต่ำสุดของ Busy Beaver ลำดับที่ 6 (BB(6)) เพิ่มขึ้นอย่างมากจากงานวิจัยใหม่เมื่อไม่นานนี้
  • ก่อนหน้านี้ทราบกันว่า BB(6) > 10↑36,534 แต่ในปี 2022 ได้มีการปรับเพิ่มเป็น BB(6) > 10↑1510
  • ล่าสุดใน BBchallenge ได้ปรับเพิ่มอีกเป็น BB(6) > 10↑10,000,00010 และต่อมาก็อัปเดตเป็น 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ขนาดของ BB(6) นั้นเกินกว่าจะจินตนาการได้ และตัวเลขนี้ใหญ่พอที่จะเติมเต็มจักรวาลทั้งหมดได้ซ้ำแล้วซ้ำเล่านับไม่ถ้วน
  • ความก้าวหน้านี้เป็นโอกาสให้ตระหนักถึงขีดจำกัดและศักยภาพของ ตรรกศาสตร์คณิตศาสตร์และทฤษฎีการคำนวณ อีกครั้ง

ภาพรวมผลงานวิจัยล่าสุดเกี่ยวกับ BB(6)

  • ในช่วงไม่กี่ปีที่ผ่านมา สถานการณ์ของโลกและสภาพแวดล้อมการวิจัยทำให้หลายอย่างรู้สึกยากลำบากอย่างต่อเนื่อง
  • แต่ความก้าวหน้าของงานวิจัย Busy Beaver ครั้งนี้ทำให้หวนระลึกถึงความหลงใหลอันบริสุทธิ์ต่อการวิจัยอีกครั้ง
  • ในปี 2022 Pavel Kropitz ได้พิสูจน์ว่า BB(6) > 10↑1510
    • BB(6) หมายถึงจำนวนครั้งการทำงานสูงสุดของเครื่องทัวริงที่มี 6 สถานะบนเทปที่เป็นศูนย์ทั้งหมดก่อนจะหยุดทำงาน
    • ในที่นี้ ^1510 หมายถึงการยกกำลังซ้ำของ 10 กับตัวเอง 15 ครั้ง (tetration)
  • งานวิจัยก่อนหน้านี้พบว่า BB(5) มีค่าเป็น 47,176,870 (โดยทีม BBchallenge) ซึ่งเป็นจุดที่ค่าดังกล่าวพุ่งเข้าสู่ขอบเขตที่เกินกว่าความเป็นจริงที่สังเกตได้

กระบวนการอัปเดตค่าต่ำสุดล่าสุด

  • "mxdys" แห่ง BBchallenge ได้พิสูจน์ว่า BB(6) > 10↑10,000,00010
    • การพิสูจน์นี้อาศัยการพิสูจน์อย่างเป็นทางการที่เขียนด้วยภาษา Coq
  • หลังจากนั้นค่าต่ำสุดก็ถูกอัปเดตอีกครั้งเป็น BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
    • ↑↑ หมายถึง tetration (การยกกำลังซ้ำ) ซึ่งอยู่ในรูปของการทำ tetration ของ 2 ด้วย 2 แล้วนำผลลัพธ์นั้นไปทำ tetration ซ้ำอีก โดยวนลักษณะนี้รวม 9 ครั้ง
    • ตัวเลขระดับนี้อยู่ในขอบเขตที่เกินกว่าความเข้าใจเชิงสัญชาตญาณใด ๆ ที่เคยมีมา
  • สำหรับ pentation นั้นหมายถึงการทำซ้ำของ tetration และเป็นการดำเนินการที่อยู่เหนือการคูณ การยกกำลัง และ tetration

ทำความเข้าใจขนาดของจำนวนที่ใหญ่มหาศาล

  • ตามคำขอของผู้สื่อข่าว จำเป็นต้องอธิบายขนาดของจำนวน 10↑10,000,00010
  • จำนวนนี้มากพอที่จะเติมจักรวาลจำนวน 10↑10,000,00010 แห่งให้เต็มไปด้วยเม็ดทรายได้
  • นี่ช่วยสื่อให้เห็นว่าค่า BB(6) นั้นก้าวล้ำเกินกว่าโลกที่เราสังเกตได้จริงอย่างมหาศาล

ข้อพิจารณาเรื่องขีดจำกัดโดยเนื้อแท้ของอัลกอริทึม BB

  • ขนาดอันมหาศาลของค่า BB(6) แสดงให้เห็นศักยภาพที่แท้จริงของฟังก์ชัน Busy Beaver
  • เดิมมีการประเมินว่าจุดที่ค่า BB(n) จะเป็นอิสระจากระบบสัจพจน์ของทฤษฎีเซต (ZFC) น่าจะอยู่ราว n=20~30 แต่ตอนนี้ชวนให้คาดการณ์ว่าอาจเป็นอิสระได้แล้วตั้งแต่ n=7~9
    • ปัจจุบันมีการทราบอย่างเป็นทางการว่าเป็นอิสระที่ n=643

ภาคผนวก: ข่าวงานอีเวนต์และการบรรยายล่าสุด

  • ผู้เขียนเพิ่งเข้าร่วมงาน STOC'2025 ที่กรุงปราก และได้พบปะนักวิจัยหลากหลายคนพร้อมรับข้อมูลใหม่ ๆ
  • ยังได้แชร์สไลด์บรรยายหลักเกี่ยวกับ สถานะล่าสุดของ quantum speedup ของตนเองด้วย
  • รายงานฉบับละเอียดกว่านี้เกี่ยวกับเนื้อหาดังกล่าวจะนำมาแบ่งปันในภายหลัง

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

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

 
GN⁺ 2025-06-29
ความคิดเห็นบน Hacker News
  • บนเซิร์ฟเวอร์ Discord ของ bbchallenge มีการแชร์ว่าผู้คนกำลังเดากันว่าเครื่องทัวริงต้องมีสถานะกี่สถานะจึงจะเหนือกว่า Graham's Number ได้ แม้ 2^^2^^2^^9 ที่ผู้ชนะ BB(6) ล่าสุดทำได้จะเป็นจำนวนมหาศาลอยู่แล้ว แต่ก็น่าประหลาดใจที่รูปแบบการเติบโตระดับ Graham อาจปรากฏขึ้นได้เร็วกว่าที่คิด มีการพูดถึงข้อมูล functional busy beaver [1] ที่บอกว่าเพียงแค่ lambda term ขนาด 49 บิตก็เพียงพอแล้ว และจำนวน closed lambda term ขนาดนั้นมีเพียง 77519927606 รายการ[2] ขณะที่เครื่องทัวริงแบบ 6-state กลับมีอยู่มากถึง 399910780272640 เครื่อง[3] อีกทั้งหลังจากมีการทำให้ pentation ถูกอิมพลีเมนต์ได้ด้วยแค่ 6 สถานะ ตอนนี้หลายคนในวงการจึงเริ่มเชื่อว่า 7 สถานะก็น่าจะพอให้เกิน Graham's Number ได้ ผู้เขียนเองก็ยังมองว่าเป็นเรื่องเหนือความคาดหมาย และเล่าว่าไม่กี่วันก่อนเพิ่งพนันก้อนใหญ่ไว้ว่าภายใน 10 ปีข้างหน้าจะมีการพิสูจน์ว่า BB(7) มากกว่า Graham's Number พร้อมถามความเห็นจากคนอื่น ๆ ด้วย (มีลิงก์ 1, 2, 3)
    • ไม่ได้แกล้งทำเป็นผู้เชี่ยวชาญ แต่คาดว่า BB(7) จะใหญ่กว่า Graham's Number แน่ ๆ เพราะ BB ต้องเติบโตเร็วกว่าลำดับจำนวนที่คำนวณได้ใด ๆ แม้จะประเมินด้วยมือได้แค่ว่า BB(7) จริง ๆ ใหญ่แค่ไหน แต่ทิศทางคือมันต้องโตเร็วกว่าตัวดำเนินการที่คำนวณได้ทั้งหมดในที่สุด (เช่น up-arrow^n เป็นต้น) ความกระโดดจาก 47176870 ไปเป็น 2^^2^^2^^9 ดูเหมือนจะเปลี่ยนระดับความรุนแรงของตัวดำเนินการมากกว่าช่วงจาก 2^^2^^2^^9 ไป Graham's Number เสียอีก และ Graham's Number คือ g_64 ซึ่งก็มองได้ว่าเป็นแนวคิดที่อยู่เหนือ up-arrow^n ไปอีกขั้น จึงมีสัญชาตญาณว่า BB(7) จะเกิน Graham's Number
  • รู้สึกทึ่งมากที่จำนวนแบบไม่อาจคำนวณได้อย่าง BB(748) กลับเป็นสิ่งที่เป็นอิสระจาก ZFC (ระบบสัจพจน์ทฤษฎีเซต) มันให้ความรู้สึกเหมือนเป็น category error อย่างหนึ่ง
    • เหตุที่ BB(748) เป็นอิสระจาก ZFC ไม่ใช่เพราะค่าตัวเลขนั้นเอง แต่เพราะหนึ่งในเครื่อง 748 สถานะคือ TM_ZFC_INC ซึ่งจะหยุดก็ต่อเมื่อพบความขัดแย้งใน ZFC (พิสูจน์ความเท็จได้) หากจะพิสูจน์ว่า BB(748)=N ก็ต้องแสดงว่า TM_ZFC_INC หยุดภายใน N สเต็ป หรือวนลูปไม่สิ้นสุด ซึ่งตามทฤษฎีบทความไม่สมบูรณ์ของ Gödel นั่นคือสิ่งที่ ZFC จะพิสูจน์ไม่ได้ หาก ZFC ไม่มีความขัดแย้ง
    • สิ่งที่น่าทึ่งยิ่งกว่าคือการที่ข้อความเพียงไม่กี่บรรทัด (ตัวสัจพจน์ของ ZFC เอง) สามารถแสดงความจริงเชิงเลขคณิตที่สำคัญต่อมนุษย์ได้มากมายอยู่แล้ว ส่วนการที่เราทำนายพฤติกรรมของเครื่องทัวริง 6 สถานะอย่างง่าย ๆ ไม่ได้นั้นกลับเป็นเรื่องธรรมดา รู้สึกเสียดายว่าหลังการประกาศทฤษฎีบทความไม่สมบูรณ์ของ Gödel วงการคณิตศาสตร์น่าจะเดินหน้าค้นหาสัจพจน์เพิ่มกันอย่างจริงจังกว่านี้ แต่ในความเป็นจริงกลับมีเพียงบางส่วนของงานวิจัยพื้นฐานเท่านั้นที่สนใจเรื่องนี้
    • ตัวอย่างที่ดีคือค่าความจริงของสมมติฐานความต่อเนื่อง ซึ่งถ้ามองแบบเพลโตนิยมก็มีค่าเป็น 1 หรือ 0 แต่ได้รับการพิสูจน์แล้วว่าเป็นอิสระจาก ZFC ไม่ใช่แค่จำนวนมหึมา แม้แต่เพียง 1 บิตก็ยังไม่มีการรับประกันจาก ZFC
    • แยกให้ชัดว่า BB(n) เป็นฟังก์ชันที่คำนวณไม่ได้ ส่วน BB(748) นั้น (ตามนิยาม) คือจำนวนเลข 1 ที่เครื่องทัวริง 748 สถานะเขียนไว้ จึงเป็นจำนวนที่คำนวณได้ ป้ายคำว่า "เป็นอิสระ" หมายความว่าในกระบวนการพิสูจน์ว่าค่านี้คือค่าที่เราต้องการจริง ๆ อาจต้องใช้ทฤษฎีที่แข็งแรงกว่า ZFC
    • เน้นว่าไม่ใช่ตัวเลขนั้นเองที่เป็นอิสระจาก ZFC แต่เป็นกระบวนการคำนวณ BB(748) ที่เป็นอิสระ (จำนวนเต็มทุกจำนวนสามารถนิยามใน ZFC ได้)
  • เป็นที่รู้กันว่า BB(14) ใหญ่กว่า Graham's Number และงานวิจัยครั้งนี้ก็ทำให้รู้สึกโดยสัญชาตญาณว่า BB(7) ก็น่าจะอย่างน้อยเท่ากับ Graham's Number เช่นกัน ในเชิงสัญชาตญาณ แนวคิดที่จะไปจาก pentation ถึง Graham's Number ดูเรียบง่ายกว่าการไปจาก 47,176,870 ถึง 2 <pentate> 5 เสียอีก
    • ข้อมูลดีมาก และน่าจะเป็นคำตอบชั้นยอดสำหรับโพสต์ของตนเอง
  • แชร์ลิงก์วิดีโอบรรยาย YouTube ของ Scott Aaronson เรื่อง “How Much Math Is Knowable?” [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c และกระทู้ HN ล่าสุด https://news.ycombinator.com/item?id=43776477
  • แจ้งว่า "เลขยกกำลังด้านซ้ายบน" คือ tetration หรือการยกกำลังซ้ำ เช่น ¹⁵10 หมายถึง 10 ยกกำลังของ 10 ยกกำลังของ... ซ้ำ 15 ครั้ง บอกด้วยว่าเพิ่งเคยเห็นแนวคิดนี้ ตอนแรกนึกว่าเป็นพิมพ์ผิด
    • ต่อเนื่องจากธีมของการทำซ้ำตัวดำเนินการ คราวนี้ตอบว่าตนเพิ่งเจอคำว่า ‘pentation’ เป็นครั้งแรก
    • เคยเห็น tetration มาก่อน แต่ชอบสัญกรณ์ up-arrow ของ Knuth[1] มากกว่า เพราะแพร่หลายกว่าและเหมาะกับการทำให้เป็นนามทั่วไป (1)
  • คำอธิบายว่า BB(6) คือจำนวนสเต็ปสูงสุดก่อนหยุดของเครื่องทัวริง 6 สถานะ 2 สัญลักษณ์ ({0,1}) บนเทปศูนย์เริ่มต้นนั้นมีประโยชน์มากสำหรับคนที่ไม่ใช่ผู้เชี่ยวชาญ ทำให้สัมผัสได้ว่าสาขานี้เต็มไปด้วยความหนาแน่นระดับยากมากและศัพท์เฉพาะสำหรับนักวิจัยมาหลายสิบปี แต่ก็รู้สึกดีที่บังเอิญได้เจอบทความลึกขนาดนี้
    • คิดว่าถ้าอยู่ระดับนักศึกษาปริญญาตรีวิทยาการคอมพิวเตอร์ ต่อให้เพิ่งเห็นปัญหา busy beaver ครั้งแรกก็น่าจะพอจับประเด็นได้ แน่นอนว่ามีศัพท์เฉพาะเยอะ แต่ไม่จำเป็นต้องรู้สึกว่าเป็นเรื่องเฉพาะคนที่มีประสบการณ์หลายสิบปีเท่านั้น
    • เสริมว่านิยามนี้เป็นมาตรฐานในสายทฤษฎีวิทยาการคอมพิวเตอร์มากกว่าวิศวกรรมซอฟต์แวร์
  • รู้สึกสับสนกับคำอธิบายที่ว่าถ้ามีเม็ดทราย "10,000,000 sub10" เม็ด ก็จะเติมเต็มเอกภพที่สังเกตได้ได้ 10,000,000 sub10 เท่า ปกติคนมักเปรียบเทียบด้วยมวลของเอกภพที่สังเกตได้ แต่ในวิธีนี้ตัวเลขก็ดูใหญ่เกินปริมาณสสารจริงไปไกลแล้ว
    • มีคนตอบว่าใช่ ต่อให้หารด้วยเม็ดทรายต่อเอกภพ ก็ยังเป็นจำนวนมหึมาระดับใกล้เคียงกัน และในสัญกรณ์นี้จำนวนที่อยู่ติดกันต่างกันอย่างเหลือเชื่อ 10↑↑10,000,000 / (เม็ดทราย/เอกภพ) ก็ยังใหญ่กว่า 10↑↑9,999,999 มาก เป็นการเปรียบเทียบว่าในระบบของเรา ค่า (ใหญ่มาก) / (ใหญ่ระดับจักรวาล) ก็ยังสรุปได้ว่าเป็นแค่ (ใหญ่มาก)
    • เสริมว่าใน tetration เราไม่ได้เทียบกันที่จำนวนหลักธรรมดาแล้ว แต่เป็นการเติบโตระดับ "จำนวนหลักของจำนวนหลัก"
    • ยืนยันอีกครั้งว่าต่อให้ใช้เม็ดทราย 10^100000 เม็ดมาหักลบ จำนวนนี้ก็แทบไม่ลดลงอย่างมีนัยสำคัญ ดังนั้นหารไปก็แทบไม่กระทบสาระสำคัญ
    • ยกตัวอย่างว่าแม้ 10,000,000^10,000,000 เองก็ใหญ่ไร้สาระมากอยู่แล้ว และถ้าเติมหางเลขชี้กำลังเพิ่มอีกชั้น การเปรียบเทียบก็แทบหมดความหมาย
    • ยกตัวอย่างที่คุ้นกว่าคือในแนวคิดเรื่องเลขนัยสำคัญ การพูดว่า 1 พันล้าน - 1 ล้าน = 1 พันล้าน ก็ไม่ได้เกินจริงนัก
  • สงสัยว่าระบบตรรกะที่ "สมบูรณ์" ที่สุดซึ่งสามารถไล่เรียงบทพิสูจน์ได้ด้วยเครื่องทัวริง 5 สถานะคืออะไร
    • คำตอบอาจต่างกันไปตามว่าให้นิยามคำว่า 'ไล่เรียง' อย่างไร อีกคำถามที่เกี่ยวกันคือ 'ระบบตรรกะที่ทรงพลังที่สุดซึ่งยังพิสูจน์การหยุดของเครื่องทัวริง 5 สถานะทุกเครื่องไม่ได้คืออะไร' ก็มีความหมายเหมือนกัน มีความเห็นส่วนตัวว่าการพิสูจน์ทางคณิตศาสตร์ว่า Skelet #17 [0] ไม่หยุดนั้นยากมาก จนถ้ามีทฤษฎีที่พิสูจน์สิ่งนี้ได้ ก็น่าจะใช้ตัดสินเครื่องทัวริง 5 สถานะที่เหลือทั้งหมดได้ด้วย (0, 1)
    • ต้องทำให้ชัดก่อนว่าเราจะตีความสตริงไบนารีจำกัดอย่างไรให้เป็นการไล่เรียงบทพิสูจน์เชิงตรรกะ จึงจะอภิปรายสมมติฐานนี้ได้
  • มีคนถามว่าเอกภพที่สังเกตได้จะใหญ่พอสำหรับเขียนค่าที่แน่นอนของ BB(6) หรือไม่
    • ถ้ามองเอกภพที่สังเกตได้เป็นระบบปิด แล้วใช้ Bekenstein bound จะคำนวณได้ว่าขีดจำกัดการเก็บข้อมูลอยู่ที่ราว 10^120 บิต ปัจจุบันประเมินว่ามวล-พลังงานรวมทั้งหมดอยู่ราว 10^53kg และเมื่อนำไปแทนในสูตรก็ยังได้ประมาณ 10^120 บิต ดังนั้นจึงเป็นไปไม่ได้ พร้อมอธิบายด้วยตัวเลขประกอบ
    • เน้นว่าเอกภพเก็บข้อมูลได้ราว 10^120 บิต และถึงจะคลาดเคลื่อนไปอีกมหาศาลก็ไม่สำคัญ เพราะมัน "ไม่พออย่างเห็นได้ชัด"
    • คาดว่าคำถามนี้สมมติว่าต้องเก็บค่าทั้งหมดพร้อมกัน หากไม่บังคับเรื่องความพร้อมกัน การบันทึกตลอดเวลาไม่สิ้นสุดอาจเป็นไปได้ในทางทฤษฎี แต่ก็ต้องคำนึงถึงข้อจำกัดจริงอย่างความตายความร้อนของเอกภพด้วย ในกรอบอ้างอิง CMB นั้นเป็นไปไม่ได้ แต่ก็มีคนตั้งคำถามว่าในแนวคิดการตัดแบ่งปริภูมิเวลาแบบอื่นอาจพอคิดได้หรือไม่
    • แค่ตัวเลขแรกในบทความก็เป็น ¹⁵10 อยู่แล้ว ซึ่งคือรูปแบบ 10^(¹⁴10) และนั่นหมายความว่าเพียงจำนวนหลักของมันก็เป็น ¹⁴10 จึงเป็นไปไม่ได้โดยสิ้นเชิง
    • ยืนยันสั้น ๆ อีกครั้งว่าเป็นไปไม่ได้
  • ทุกครั้งที่เห็นผลลัพธ์แนวนี้ในทฤษฎีความซับซ้อนเชิงคำนวณ ก็ยิ่งรู้สึกว่ากระแสพูดทำนอง "ซูเปอร์ AI คือพระเจ้า" นั้นไร้หลักฐานโดยสิ้นเชิง ต่อให้เปลี่ยนอะตอมทั้งหมดในจักรวาลเป็นซูเปอร์คอมพิวเตอร์และใช้พลังงานจากหลุมดำทั้งหมด ก็ยังไม่มีวันคำนวณสถานะการหยุดของ BB(6) ได้
    • มีคนตอบสั้น ๆ ว่าข้อโต้แย้งแบบฟางนั้นเดิมทีก็ไม่น่าเชื่อถืออยู่แล้ว