BusyBeaver(6) thực sự khổng lồ

• Số Busy Beaver thứ 6 (BB(6)) gần đây đã có cận dưới tăng mạnh nhờ nghiên cứu mới
• Trước đây người ta biết rằng BB(6) > 10↑36,534, nhưng đến năm 2022 đã được nâng lên thành BB(6) > 10↑1510
• Gần đây, tại BBchallenge, cận này tiếp tục được nâng lên thành BB(6) > 10↑10,000,00010, rồi sau đó cập nhật tiếp lên 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
• Kích thước của BB(6) vượt xa sức tưởng tượng, đến mức con số này đủ để lấp đầy toàn bộ vũ trụ vô số lần
• Những tiến triển này là dịp để nhận thức lại giới hạn và tiềm năng của logic toán học và lý thuyết tính toán

---

Tổng quan về thành tựu nghiên cứu gần đây của BB(6)

• Trong vài năm gần đây, thế giới và môi trường nghiên cứu liên tục tạo cảm giác nặng nề, khó khăn
• Tuy vậy, bước tiến lần này trong nghiên cứu Busy Beaver đã trở thành dịp nhắc lại niềm đam mê thuần túy với nghiên cứu
• Năm 2022, Pavel Kropitz đã chứng minh rằng BB(6) > 10↑1510
  • BB(6) là số bước tối đa mà một máy Turing có 6 trạng thái có thể chạy trên băng toàn số 0 trước khi dừng
  • Ở đây ^1510 là giá trị nhận được khi lấy 10 lũy thừa chồng lên chính nó 15 lần (tetration)
• Trong nghiên cứu trước đó, BB(5) được xác định là 47,176,870 (nhóm BBchallenge), và đây là thời điểm giá trị bắt đầu tăng vọt vượt ra ngoài phạm vi của thực tại có thể quan sát

Quá trình cập nhật cận dưới gần đây

• "mxdys" của BBchallenge đã chứng minh BB(6) > 10↑10,000,00010
  • Chứng minh này dựa trên một chứng minh hình thức được viết bằng ngôn ngữ Coq
• Sau đó, cận dưới lại được cập nhật thành BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ↑↑ nghĩa là tetration (lặp phép lũy thừa), tức là lấy 2 tetration với 2, rồi lại tetration với kết quả đó, lặp theo dạng này đến 9
  • Cỡ số như vậy thuộc về một miền vượt quá mọi trực giác hiểu biết trước đây
• Tham khảo thêm, pentation là phép lặp của tetration, tức một phép toán vượt lên trên nhân, lũy thừa và tetration

Hiểu về độ lớn của các số khổng lồ

• Theo đề nghị của phóng viên, cần phải giải thích độ lớn của con số 10↑10,000,00010
• Lượng cát này đủ để lấp đầy 10↑10,000,00010 vũ trụ bằng cát
• Qua đó truyền đạt rằng giá trị BB(6) vượt xa thế giới quan sát thực tế đến mức không thể hình dung

Suy ngẫm về giới hạn bản chất của thuật toán BB

• Độ lớn khủng khiếp của giá trị BB(6) cho thấy tiềm năng thực sự của hàm Busy Beaver
• Người ta từng ước tính thời điểm mà giá trị BB(n) trở nên độc lập với hệ tiên đề của lý thuyết tập hợp (ZFC) là khoảng n=20~30, nhưng nay có thể dự đoán rằng có lẽ ngay từ n=7~9 nó cũng đã độc lập
  • Hiện tại, người ta chính thức biết rằng nó độc lập ở n=643

Phụ lục: tin tức về sự kiện và bài giảng gần đây

• Tác giả gần đây đã tham dự sự kiện STOC'2025 tổ chức tại Prague, giao lưu với nhiều nhà nghiên cứu và thu nhận thông tin mới
• Tác giả cũng chia sẻ slide bài giảng keynote về tình hình tăng tốc lượng tử của mình
• Bài chia sẻ chi tiết hơn về nội dung này sẽ được đăng sau

[GN⁺]

Ý kiến trên Hacker News

• Trên máy chủ Discord của bbchallenge, mọi người chia sẻ cảnh họ đoán cần bao nhiêu trạng thái máy Turing để vượt qua Graham's Number. Dù 2^^2^^2^^9 mà quán quân BB(6) gần đây đạt được đã là một con số khổng lồ, nhiều người vẫn ngạc nhiên vì kiểu tăng trưởng ở mức Graham có thể xuất hiện sớm hơn tưởng tượng. Bài viết nhắc tới tài liệu về functional busy beaver [1], theo đó chỉ cần lambda term 49 bit là đủ, và số closed lambda term ở kích thước đó chỉ là 77519927606[2], trong khi số máy Turing 6 trạng thái lại lên tới 399910780272640[3]. Sau khi pentation được hiện thực chỉ với 6 trạng thái, bầu không khí hiện nay dường như là khá nhiều người trong giới tin rằng 7 trạng thái cũng có thể vượt Graham's Number. Dù vậy, người viết vẫn thấy điều đó khá bất ngờ. Họ kể rằng vài ngày trước mình đã cá lớn về việc trong 10 năm tới sẽ xuất hiện chứng minh BB(7) vượt Graham's Number, và hỏi ý kiến của người khác. (1, 2, 3 cung cấp liên kết)
  • Tôi không giả làm chuyên gia, nhưng dự đoán BB(7) sẽ lớn hơn Graham's Number. Busy beaver phải tăng nhanh hơn mọi dãy số tính được bất kỳ, nên dù rất khó hình dung chính xác BB(7) lớn tới đâu, hướng chung là cuối cùng nó phải tăng nhanh hơn mọi toán tử tính được như up-arrow^n. Tôi có cảm giác độ nhảy từ 47176870 lên 2^^2^^2^^9 còn kịch tính hơn nhiều, xét theo sức mạnh toán tử, so với khoảng từ 2^^2^^2^^9 lên Graham's Number. Graham's Number là g_64, mà bản thân nó cũng có thể được hiểu là một khái niệm cao hơn một bậc so với up-arrow^n, nên tôi có trực giác rằng BB(7) sẽ vượt Graham's Number.
• Việc một số không tính được như BB(748) lại độc lập với ZFC (hệ tiên đề tập hợp) thật sự rất kỳ lạ. Thành thật mà nói, nó gần giống như một lỗi phân loại phạm trù.
  • Lý do BB(748) độc lập với ZFC không nằm ở chính giá trị đó, mà vì một trong các máy 748 trạng thái, TM_ZFC_INC, chỉ dừng nếu nó tìm thấy mâu thuẫn trong ZFC (một chứng minh sai). Để chứng minh BB(748)=N, ta phải chỉ ra TM_ZFC_INC dừng trong N bước hoặc chạy mãi mãi; theo định lý bất toàn của Gödel, nếu ZFC là nhất quán thì đó là một hệ quả không thể chứng minh trong ZFC.
  • Điều gây ngạc nhiên hơn là việc người ta từng nghĩ một số ít dòng văn bản, tức chính các tiên đề ZFC, có thể biểu đạt đầy đủ các chân lý số học quan trọng với con người. Thực tế rằng ta còn không thể dự đoán đơn giản hành vi của cả máy Turing 6 trạng thái thì là điều dễ hiểu. Sau khi định lý bất toàn của Gödel được công bố, đáng ra giới toán học phải tích cực hơn nhiều trong việc tìm thêm các tiên đề, nhưng trên thực tế điều đó chỉ được bàn tới trong một phần nghiên cứu nền tảng, điều này khá đáng tiếc.
  • Một ví dụ hay là giá trị chân lý của giả thuyết continuum, nếu nhìn theo chủ nghĩa Platon thì là 1 hoặc 0, đã được chứng minh là độc lập với ZFC. Không phải một số khổng lồ, chỉ riêng 1 bit thôi cũng không được ZFC đảm bảo.
  • Cần phân biệt rõ BB(n) là không tính được, còn BB(748), theo định nghĩa là số lượng số 1 mà một máy Turing 748 trạng thái ghi ra, nên là một số tính được. Nhãn “độc lập” ở đây có nghĩa là để chứng minh rằng con số này đúng là giá trị ta mong muốn trong ZFC, ta cần một lý thuyết mạnh hơn.
  • Điều độc lập với ZFC không phải bản thân con số, mà là quá trình tính BB(748). (Mọi số nguyên đều có thể biểu diễn trong ZFC)
• Việc BB(14) lớn hơn Graham's Number là điều nổi tiếng, và nghiên cứu lần này khiến tôi có trực giác rằng BB(7) cũng sẽ ít nhất ngang Graham's Number. Về mặt trực giác, ý tưởng đi từ pentation tới Graham's Number dường như còn đơn giản hơn việc đi từ 47,176,870 tới 2 <pentate> 5.
  • Thông tin hay đấy, có vẻ sẽ là một câu trả lời tuyệt vời cho bài viết của tôi.
• Chia sẻ liên kết tới bài giảng YouTube “How Much Math Is Knowable?” của Scott Aaronson [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c và bài thảo luận HN gần đây https://news.ycombinator.com/item?id=43776477
• Có người cho biết “chỉ số trên bên trái” là tetration, tức lũy thừa lặp, và giải thích rằng ¹⁵10 nghĩa là 10 của 10 của... lặp 15 lần. Họ nói đây là khái niệm lần đầu thấy nên lúc đầu còn tưởng là lỗi gõ.
  • Nối tiếp chủ đề các phép toán lặp, người này phản ứng rằng lần này họ mới biết tới “pentation”.
  • Tôi từng thấy tetration trước đây, nhưng thích ký pháp up-arrow của Knuth[1] hơn vì nó phổ biến hơn và thuận tiện cho việc tổng quát hóa. (1)
• Giải thích rằng BB(6) là số bước tối đa mà máy Turing 6 trạng thái 2 ký hiệu ({0,1}) thực hiện trước khi dừng trên băng toàn số 0 ban đầu là rất hữu ích cho người không chuyên. Tôi cảm nhận đây là một lĩnh vực dày đặc và chuyên môn hóa, dành cho những người đã nghiên cứu hàng chục năm, nhưng thật thú vị khi tình cờ đọc được một bài sâu đến vậy.
  • Tôi nghĩ nếu ở mức sinh viên cử nhân khoa học máy tính thì dù mới gặp bài toán busy beaver lần đầu cũng vẫn nắm được ý chính. Đúng là có nhiều thuật ngữ chuyên biệt, nhưng không cần cảm thấy đây là thứ chỉ dành cho người có vài chục năm kinh nghiệm.
  • Cần nói rõ rằng định nghĩa đó là tiêu chuẩn trong lý thuyết khoa học máy tính hơn là trong software engineering.
• Tôi thấy khó hiểu với lời giải thích rằng nếu có “10,000,000 sub10” hạt cát thì có thể lấp đầy vũ trụ quan sát được gấp 10,000,000 sub10 lần. So sánh theo khối lượng của vũ trụ quan sát được có vẻ thường gặp hơn, và cách nói này dường như đã vượt xa lượng vật chất thực tế.
  • Đúng vậy. Dù có chia cho số hạt cát hay số vũ trụ thì bản thân nó vẫn gần như cùng bậc lớn đến mức khổng lồ, còn các số liền kề nhau trong ký pháp này thì chênh lệch ghê gớm. 10↑↑10,000,000 / (hạt cát/vũ trụ) vẫn lớn hơn rất nhiều so với 10↑↑9,999,999. Có thể ví rằng trong hệ của chúng ta, một giá trị (rất lớn) / (lớn cỡ vũ trụ) vẫn cứ được xem là (rất lớn).
  • Với tetration, ta không còn nói về số chữ số đơn thuần nữa, mà là tốc độ tăng trưởng ở mức “số chữ số của số chữ số”.
  • Dù có chia cho cỡ 10^100000 hạt cát thì con số này cũng chẳng giảm đi đáng kể, nên việc chia gần như không ảnh hưởng bản chất của nó.
  • Ngay cả 10,000,000^10,000,000 cũng đã đủ vô lý rồi, nên thêm một tầng mũ nữa thì việc so sánh hầu như mất hết ý nghĩa.
  • Một ví dụ quen thuộc hơn: trong khái niệm chữ số có nghĩa, nói 1 tỷ - 1 triệu = 1 tỷ cũng không phải là cường điệu.
• Có người bày tỏ tò mò rằng trong các hệ logic có thể liệt kê chứng minh bằng máy Turing 5 trạng thái, hệ nào là “giàu” nhất.
  • Câu trả lời sẽ khác tùy cách bạn định nghĩa “liệt kê”. Một câu hỏi liên quan là: hệ logic mạnh nhất nào vẫn không thể chứng minh được việc dừng hay không dừng của mọi máy Turing 5 trạng thái? Cá nhân tôi cho rằng việc chứng minh bằng toán học rằng Skelet #17 [0] không dừng là cực kỳ khó, nên nếu có một lý thuyết chứng minh được điều đó thì có lẽ cũng sẽ quyết định được toàn bộ các máy Turing 5 trạng thái còn lại. (0, 1)
  • Cần làm rõ trước giả định rằng các chuỗi nhị phân hữu hạn được diễn giải như việc liệt kê chứng minh logic theo cách nào.
• Có người đặt câu hỏi liệu vũ trụ quan sát được có đủ lớn để ghi chính xác giá trị của BB(6) hay không.
  • Nếu xem vũ trụ quan sát được là một hệ kín và áp dụng Bekenstein bound, giới hạn lưu trữ thông tin chỉ vào khoảng 10^120 bit. Theo ước tính hiện tại, tổng khối lượng-năng lượng vào cỡ 10^53kg, và thay vào công thức cũng chỉ cho ra khoảng 10^120 bit. Vì vậy là không thể, và có thể giải thích điều đó bằng số liệu cụ thể.
  • Lượng thông tin có thể lưu trong vũ trụ chỉ khoảng 10^120 bit, và dù có sai lệch vài bậc cỡ nghìn tỷ đi nữa thì điều đó cũng không có ý nghĩa gì, vì rõ ràng là hoàn toàn không đủ.
  • Có lẽ câu hỏi đang giả định việc lưu toàn bộ giá trị cùng một lúc. Nếu không yêu cầu tính đồng thời thì về mặt lý thuyết có thể ghi dần qua thời gian vô hạn, nhưng vẫn phải tính đến các giới hạn thực tế như cái chết nhiệt của vũ trụ. Trong hệ quy chiếu của CMB thì không thể, nhưng biết đâu nếu nghĩ theo một kiểu cắt không-thời gian khác thì còn có thể bàn tiếp.
  • Ngay từ con số đầu tiên trong bài đã là ¹⁵10, tức dạng 10^(¹⁴10), nên riêng số chữ số của nó đã là ¹⁴10; xét vậy thì hoàn toàn không thể.
  • Xin xác nhận ngắn gọn: không thể.
• Mỗi lần nhìn các kết quả như thế này trong lý thuyết độ phức tạp tính toán, tôi lại càng thấy những diễn ngôn thời thượng kiểu “siêu AI là thần thánh” hoàn toàn không có cơ sở. Dù có biến mọi nguyên tử trong vũ trụ thành siêu máy tính và dùng cả năng lượng hố đen đi nữa, việc tính trạng thái dừng của BB(6) vẫn là điều vĩnh viễn bất khả.
  • Mấy lập luận rơm kiểu đó vốn dĩ ngay từ đầu đã chẳng có sức thuyết phục gì.