- ค่าขอบล่างที่ทราบของ BB(6) ถูกยกระดับขึ้นอย่างมากอีกครั้ง และยืนยันได้ว่าเวลาหยุดสูงสุดของเครื่องทัวริง 6 สถานะเป็นจำนวนที่ไกลเกินกว่าขนาดของความเป็นจริงที่สังเกตได้มาก
- BB(6) หมายถึงจำนวนสเต็ปสูงสุดที่ เครื่องทัวริง 6 สถานะ·2 สัญลักษณ์ ซึ่งเริ่มจากเทปที่เต็มไปด้วย 0 สามารถรันได้ก่อนหยุด
- หลังจากการปรับปรุงของ Pavel Kropitz ในปี 2022 mxdys ได้ดันขอบล่างขึ้นอีกครั้งให้อยู่ในระดับที่ใหญ่กว่า จำนวนที่ได้จากการยกกำลังซ้ำของ 10 จำนวน 10 ล้านครั้ง
- ผลล่าสุดแสดงว่า BB(6) มีค่าอย่างน้อย 2 pentated to 5 และมีการใช้การดำเนินการที่สูงกว่าการยกกำลังซ้ำขึ้นไปอีกหนึ่งระดับ
- BB(5) ถูกกำหนดแล้วว่าเป็น 47,176,870 แต่ BB(6) ใหญ่ขึ้นอย่างท่วมท้น จนนำไปสู่การคาดการณ์ว่าจุดที่ BB(n) เป็นอิสระจากระบบสัจพจน์ ZFC อาจอยู่ที่ n=7, 8, 9
ขอบล่างของ BB(6) ใหญ่ขึ้นอีกครั้ง
- ก่อนปี 2022 สำหรับ BB(6) มีข้อมูลเพียงว่า BB(6) > 10^36,534 โดยประมาณ และ Pavel Kropitz ได้ปรับปรุงเป็นระดับที่ใหญ่กว่า จำนวนที่ได้จากการยกกำลังซ้ำของ 10 จำนวน 15 ครั้ง
- tetration หมายถึงการยกกำลังซ้ำ
- เช่น จำนวนที่นำ 10 มาซ้อนกัน 15 ชั้น คือจำนวนในรูป 10 ยกกำลัง 10 ยกกำลัง 10 ยกกำลัง … ต่อเนื่องกัน 15 ครั้ง
- Tristan Sterin ผู้จัด BBchallenge แจ้งว่าสมาชิกทีม mxdys ได้ยกระดับขอบล่างของ BB(6) ขึ้นอีกครั้ง
- การปรับปรุงครั้งแรก: BB(6) > จำนวนที่ได้จากการยกกำลังซ้ำของ 10 จำนวน 10 ล้านครั้ง
- ผลนี้มี บทพิสูจน์ความถูกต้องด้วย Coq
- การปรับปรุงภายหลังของ mxdys แสดงว่า BB(6) มีค่าอย่างน้อย 2 tetrated to 2 tetrated to 2 tetrated to 9
- โดยเฉพาะ BB(6) มีค่าอย่างน้อย 2 pentated to 5
- pentation คือ tetration แบบทำซ้ำ เป็นการดำเนินการที่สูงกว่าการที่ tetration ทำซ้ำการยกกำลังขึ้นไปอีกหนึ่งระดับ
ความต่างสุดขั้วระหว่าง BB(5) กับ BB(6)
- BB(6) คือ จำนวน Busy Beaver ตัวที่ 6
- พิจารณาเครื่องทัวริง 6 สถานะ
- อักษรคือ {0,1}
- เทปอินพุตเริ่มต้นเป็น 0 ทั้งหมด
- หมายถึงจำนวนสเต็ปการรันสูงสุดที่เป็นไปได้ก่อนหยุด
- ทีม BBchallenge ระดับนานาชาติได้กำหนด BB(5) เมื่อปีที่แล้วว่าเป็น 47,176,870
- ในช่วงที่เปลี่ยนจาก BB(5) ไปเป็น BB(6) ฟังก์ชัน Busy Beaver กระโดดจากระดับ หลายสิบล้าน ไปเป็นขนาดที่เกินขอบเขตของความเป็นจริงที่สังเกตได้
จำนวนที่แทบใช้ความรู้สึกเรื่องขนาดไม่ได้
- แม้ในช่วงที่ทราบว่า BB(6) > จำนวนที่ได้จากการยกกำลังซ้ำของ 10 จำนวน 10 ล้านครั้ง ก็แทบเป็นไปไม่ได้ที่จะอธิบายด้วยสัญชาตญาณ
- ตัวอย่างเช่น มีการเปรียบเทียบว่า หากมีเม็ดทรายมากขนาดนั้น ก็สามารถเติมสำเนาของเอกภพที่สังเกตได้ให้เต็มได้ประมาณจำนวนเท่ากัน
- การเปรียบเทียบนี้แสดงให้เห็นว่า เนื่องจากจำนวนนั้นใหญ่กว่าจำนวนระดับจักรวาลอย่าง 10^100 อย่างท่วมท้น แม้จะนำไปหารแล้วก็ยังเหลือขนาดแทบเท่าจำนวนเดิม
ความเป็นไปได้ที่ค่าคาดการณ์เรื่องความเป็นอิสระจาก ZFC จะลดลง
- การที่ BB(6) ใหญ่ขึ้นขนาดนี้ไม่ได้หมายความว่าความคิดทั้งหมดเกี่ยวกับฟังก์ชัน Busy Beaver จะเปลี่ยนไป
- เดิมทีก็เปิดความเป็นไปได้ไว้แล้วว่า BB(6) อาจไม่ได้อยู่ในระดับค่อนข้างเล็กอย่าง 10^36,534 แต่อยู่ใน ขอบเขตของการดำเนินการแบบทำซ้ำ
- เมื่อขอบล่างจริงได้รับการยืนยันว่าอยู่ในระดับนั้น การคาดการณ์เกี่ยวกับจุดที่ค่าของ BB(n) เป็นอิสระจาก ระบบสัจพจน์ทฤษฎีเซต ZFC อาจลดลงได้
- ก่อนหน้านี้อาจคิดว่าอยู่ใกล้ n=20 หรือ 30
- ตอนนี้มองว่าอาจเป็น n=7, 8, 9 ก็ได้
- ผลลัพธ์เกี่ยวกับความเป็นอิสระจาก ZFC ที่ทราบในปัจจุบันอยู่ในระดับที่ BB(n) เป็นอิสระจาก ZFC ที่ n=643
อัปเดตแยกต่างหาก: STOC 2025
- ได้พบกับนักวิจัยหลายคนและรับทราบเรื่องใหม่ ๆ ที่ Prague ซึ่งจัด STOC 2025
- หัวข้อ plenary lecture ของ STOC คือ The Status of Quantum Speedups
- ผู้อ่านที่สนใจสามารถดู PowerPoint slides ของการบรรยายนั้นได้
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ในเซิร์ฟเวอร์ Discord ของ bbchallenge กำลังเดากันอย่างคึกคักว่าต้องใช้สถานะของเครื่องทัวริงกี่สถานะจึงจะเกิน Graham's Number ซึ่งใหญ่กว่า
2^^2^^2^^9ที่แชมป์ BB(6) ล่าสุดทำได้มากถ้าดู functional busy beaver https://oeis.org/A333479 พฤติกรรมระดับ Graham อาจปรากฏเร็วกว่าที่คิด แค่ lambda term ขนาด 49 บิตก็พอ
lambda term แบบปิดที่มีขนาดไม่เกินนั้นมีเพียง 77,519,927,606 ตัว https://oeis.org/A114852 ส่วนเครื่องทัวริง 6 สถานะที่ไม่ซ้ำกันมี
4^12*23836540=399910780272640เครื่อง https://oeis.org/A107668แค่ 6 สถานะก็ทำเพนเทชันได้แล้ว ตอนนี้จึงมีหลายคนมองว่า 7 สถานะก็น่าจะเกิน Graham's Number ได้ ถึงอย่างนั้นผมก็ยังคิดว่าเป็นเรื่องน่าทึ่งมากอยู่ดี ไม่กี่วันก่อนผมพนันก้อนใหญ่กับหนึ่งในคนเหล่านั้นว่าในอีก 10 ปีข้างหน้าจะมีหลักฐานพิสูจน์ว่า
BB(7)>Graham'sหรือไม่ เลยอยากรู้ว่าทุกคนคิดอย่างไรBB ต้องโตเร็วกว่า sequence ใด ๆ ที่คำนวณได้ สิ่งนี้หมายความอย่างเป็นรูปธรรมอย่างไรสำหรับ BB(7) สุดท้ายก็คล้ายการอธิบายแบบกว้าง ๆ ด้วยท่าทาง แต่รู้สึกว่ามันต้องไต่บันไดความแรงของตัวดำเนินการขึ้นไปอย่างรวดเร็วมาก ท้ายที่สุดมันต้องโตเร็วกว่าตัวดำเนินการที่คำนวณได้ใด ๆ ที่เรานิยามขึ้น รวมถึง
up-arrow^nหรือup-arrow^f(n)สำหรับฟังก์ชันที่คำนวณได้fด้วยตามสัญชาตญาณ การเติบโตจาก
47 millionไปเป็น2^^2^^2^^9ดูเหมือนใหญ่กว่าในเชิงคุณภาพด้านความแรงของตัวดำเนินการที่ต้องใช้ มากกว่าการเติบโตจาก2^^2^^2^^9ไปเป็น Graham's Number Graham's Number คือg_64และgในที่นี้อยู่สูงกว่าup_arrow^nราวหนึ่งขั้น ดังนั้น BB(7)>Graham's Number จึงน่าจะเป็นไปได้มากตัวเลขอย่าง BB(748) แถมยังเป็นจำนวนที่คำนวณไม่ได้ด้วย สามารถ “เป็นอิสระจาก ZFC” ได้ ทำให้มึนหัวจริง ๆ รู้สึกเหมือนเป็น category error อะไรสักอย่าง
TM_ZFC_INCถูกกำหนดให้ค้นหาความขัดแย้งภายใน ZFC หรือก็คือหลักฐานพิสูจน์ของFALSEและหยุดก็ต่อเมื่อพบสิ่งนั้นเท่านั้นดังนั้นหลักฐานพิสูจน์ว่า
BB(748)=Nต้องแสดงว่าTM_ZF_INCหยุดภายใน N ขั้นตอน หรือไม่ก็แสดงว่ามันจะไม่หยุดอย่างเด็ดขาด หากสมมติว่า ZFC สอดคล้องกัน ทั้งสองอย่างเป็นไปไม่ได้เพราะผลลัพธ์อันโด่งดังของ GödelBB(n)สำหรับnใด ๆBB(748)นั้นคำนวณได้ ตามนิยามแล้วมันคือจำนวน 1 ที่เครื่องทัวริงบางเครื่องซึ่งมี 748 สถานะเขียนออกมา และเครื่องนั้นก็คำนวณBB(748)ตัวเลขเองเป็นเพียงจำนวนเต็มที่ใหญ่จนจินตนาการไม่ออกจริง ๆ ความเป็นอิสระจาก ZFC จะเข้ามาเกี่ยวเมื่อเราพยายามพิสูจน์ว่าตัวเลขนี้คือค่าที่เรากำลังหา การทำเช่นนั้นต้องใช้ทฤษฎีที่แข็งแรงกว่า ZFC ซึ่งสามารถจับคุณสมบัติของเครื่องทัวริง 748 สถานะได้
การที่พฤติกรรมของเครื่องทัวริง 6 สถานะอาจคาดการณ์ไม่ได้ด้วยข้อความไม่กี่บรรทัดนั้นไม่น่าประหลาดใจเลย
ตอน Gödel ประกาศทฤษฎีบทความไม่สมบูรณ์บทแรก ผมคิดว่าวงการคณิตศาสตร์ทั้งหมดน่าจะวิ่งเต็มสปีดไปหาสัจพจน์เพิ่มเติม แต่ตลอดเกือบหนึ่งศตวรรษ งานของ Gödel กลับมักถูกมองเป็นข้อเท็จจริงแปลก ๆ ในพื้นที่แคบ ๆ ของรากฐานคณิตศาสตร์ มากกว่าจะเป็นโปรแกรมกระแสหลัก ผมรู้จัก Feferman, Friedman และคนอื่น ๆ อยู่ แต่การวิจัยในด้านนี้มีน้อยกว่าหัวข้ออื่นส่วนใหญ่ของคณิตศาสตร์มาก
BB(748)ดังนั้นจึงไม่มีโปรแกรมที่ ZFC สามารถพิสูจน์ได้ว่าส่งออกค่า
BB(748)แต่เช่นเดียวกับตัวเลขอื่นทั้งหมด โปรแกรมที่ส่งออกBB(748)นั้นมีอยู่จริงเป็นที่รู้กันว่า BB(14) ใหญ่กว่า Graham's Number แต่จากผลลัพธ์ครั้งนี้ ดูเหมือนว่า
BB(7)ก็น่าจะใหญ่กว่า Graham's Number เช่นกันตามสัญชาตญาณ เทคนิคที่ต้องใช้เพื่อไปจากเพนเทชันถึง Graham's Number ดูเรียบง่ายกว่าเทคนิคที่ต้องใช้เพื่อไปจาก
47,176,870ไปเป็น2 5ตอนเห็นคำอธิบายว่า
ตัวยกด้านซ้ายหมายถึง tetration หรือการยกกำลังซ้ำ ๆ ตอนแรกนึกว่าเป็นพิมพ์ผิด เพิ่งเคยเจอ tetration เป็นครั้งแรกไม่เข้าใจตรงที่บอกว่า “ลองจินตนาการว่ามีเม็ดทราย
10,000,000sub10เม็ด จากนั้นก็สามารถใช้ทรายนั้นเติมเอกภพที่สังเกตได้ได้ประมาณ10,000,000sub10แห่ง”นี่กำลังปัดค่าที่ได้จากการนำปริมาตรของเอกภพที่สังเกตได้หารด้วยปริมาตรเฉลี่ยของเม็ดทราย แล้วตัดทิ้งจริง ๆ เหรอ? นั่นต่างกันหลายหลักมากกว่ามวลรวมของเอกภพที่มักใช้เปรียบเทียบกันเสียอีก
10↑↑10,000,000 / (จำนวนเม็ดทรายต่อหนึ่งเอกภพ)ยังใหญ่กว่า10↑↑9,999,999อย่างท่วมท้นด้วยซ้ำในระบบที่ใช้จำนวนแบบนี้ แทบไม่มีวิธีแสดงที่ดีกว่าเขียนตรง ๆ ว่า
(จำนวนที่ใหญ่มาก)/(จำนวนที่เป็นแค่ระดับจักรวาล)และในสัญกรณ์ฝั่งจำนวนที่ใหญ่มาก สุดท้ายก็ถูกปัดแทบจะเป็น(จำนวนที่ใหญ่มาก)อยู่ดี10^100000หรือปริมาณอย่างจำนวนเม็ดทรายที่ใส่ลงไปได้มากมายเหลือเกิน จนต่อให้หารด้วยปริมาณระดับนั้นก็แทบไม่เปลี่ยนแปลง อย่างน้อยก็ไม่ได้ลดลงจนเข้าใกล้9,999,999sub1010,000,000^10,000,000ก็ใหญ่พอจนเรื่องระดับนั้นไม่สำคัญแล้ว ยิ่งเมื่อ ตัวชี้กำลังเอง ถูกยกกำลังซ้ำอีกเก้าครั้ง ก็ยิ่งไม่ต้องพูดถึงHow Much Math Is Knowable? ของ Scott Aaronson [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
เคยถูกนำขึ้น HN เมื่อไม่กี่เดือนก่อนด้วย: https://news.ycombinator.com/item?id=43776477
ตรรกะที่สมบูรณ์ที่สุดซึ่งสามารถแจกแจงบทพิสูจน์ได้ด้วยเครื่องทัวริง 5 สถานะเท่านั้นคืออะไร?
เวอร์ชันนี้เคยลองคิดดูอยู่บ้าง แต่ไปได้ไม่ไกลเพราะไม่มีความเชี่ยวชาญด้านตรรกะอันดับหนึ่งพอ เท่าที่รู้ Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA เป็นหนึ่งในเครื่องที่พิสูจน์ทางคณิตศาสตร์ว่าไม่หยุดได้ยากที่สุด https://arxiv.org/abs/2407.02426 ดังนั้นถ้าทฤษฎีใดพิสูจน์ได้ว่า Skelet #17 ไม่หยุด ก็น่าจะมีโอกาสตัดสินเครื่อง 5 สถานะที่เหลือได้สูง
พอเห็นคำอธิบายว่า “BB(6) คือจำนวน Busy Beaver ลำดับที่หก กล่าวคือจำนวนขั้นตอนสูงสุดที่เครื่องทัวริง 6 สถานะซึ่งมีอักษร
{0,1}สามารถทำได้ก่อนหยุด เมื่อเริ่มรันบนเทปที่เป็น 0 ทั้งหมด” สำหรับคนนอกวงการอย่างผมกลับรู้สึกว่าเข้าใจได้ดีเกินคาดนี่ต้องเป็น บล็อกสายฮาร์ดคอร์ สำหรับคนที่ทำงานวิจัยแนวนี้มาหลายสิบปีแน่ ๆ การได้บังเอิญเจอบทความที่เขียนอย่างเข้มข้นและเต็มไปด้วยศัพท์เฉพาะอย่างไม่เกรงใจเพื่อผู้อ่านเฉพาะกลุ่มนี่ค่อนข้างเจ๋ง
มันเป็นศัพท์เฉพาะสายย่อยก็จริง แต่การมองว่ามีแค่คนที่ทุ่มเทมาหลายสิบปีเท่านั้นถึงจะเข้าถึงได้ เป็นการประเมินตัวเองต่ำไป
จำนวนที่ใหญ่ขนาดนั้นมนุษย์นึกภาพไม่ออก วิธีแทนจำนวนไม่ได้มีแค่การนับอย่างเดียว
ตัวอย่างเช่น เม็ดทรายหนึ่งเม็ดก็ถือได้ว่ามีสถานะที่เป็นไปได้เป็นอนันต์ มีจำนวนจริงอนันต์ ดังนั้นจะบอกว่าเม็ดทรายหนึ่งเม็ดสามารถแทน
BB(6)ได้ก็อาจพูดได้ การจัดหมู่อาจโตแบบเอ็กซ์โปเนนเชียล ดังนั้นวิธีแบบนั้นอาจมีประโยชน์ต่อการแทนค่ากล่าวคือเป็นเรื่องว่าระบบหนึ่งสามารถแสร้งทำเป็นไม่ขัดแย้งกันได้ดีแค่ไหนก่อนจะถูกจับได้ ระบบที่ขัดแย้งกันซึ่งแสร้งว่ามีความสอดคล้องผ่าน
BB(3)จะ “ถูกจับได้” เร็วกว่าระบบที่แสร้งว่ามีความสอดคล้องผ่านBB(6)มาก ในที่นี้การแสร้งว่ามีความสอดคล้องหมายถึงการอ้างว่าโปรแกรมทุกตัวที่รันนานกว่าBB(n)ขั้นตอนสำหรับnบางค่า จะไม่หยุดการดึงความละเอียดอนันต์เข้ามาเพื่อทำให้ดูเหมือนจัดการได้ง่าย สำหรับผมแล้วใกล้เคียงกับกลเม็ดมากกว่า เวลาจะอธิบายขนาดควรใช้จำนวนเต็มดีกว่า
สงสัยว่าเอกภพที่สังเกตได้มีขนาดใหญ่พอจะเขียนค่าที่แน่นอนของ BB(6) ได้หรือไม่
ใช้
R ≈ 46.5 billion light-yearsหรือก็คือรัศมีของเอกภพที่สังเกตได้ และใช้E ≈ปริมาณมวล-พลังงานรวมของเอกภพที่สังเกตได้มวล-พลังงานนี้รวมถึงสสารปกติ สสารมืด และพลังงานมืด ตามค่าประมาณปัจจุบัน เอกภพที่สังเกตได้มีปริมาณเทียบเท่ามวล-พลังงานประมาณ
10^53 kgเมื่อนำไปใส่ใน
S ≤ 2πER/ℏcจะได้ปริมาณข้อมูลสูงสุดราวระดับ10^120 bitsS ≤ 2πER/ℏcS ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)S ≤ 2.654135e+124S ≤ 10^120ดังนั้นจึงเป็นไปไม่ได้
¹⁵10แล้ว ซึ่งหมายถึง10^(¹⁴10)ดังนั้นจึงมีจำนวนหลักอยู่¹⁴10หลัก เพราะฉะนั้นเขียนไม่ได้แต่ในปริภูมิเวลาเชิงสัมพัทธภาพ คำว่า “พร้อมกัน” ไม่ได้ถูกนิยามไว้อย่างดี ความเห็นพี่น้องด้านบนถูกต้องแน่นอนในกรอบอ้างอิงที่รังสีไมโครเวฟพื้นหลังของจักรวาลบ่งชี้ไว้ เพียงแต่ผมสงสัยว่าในบางกรอบอ้างอิง อาจมีวิธีหั่นปริภูมิเวลาให้สามารถแสดงมัน “พร้อมกัน” ได้หรือไม่