BusyBeaver(6) thực sự rất lớn

 (scottaaronson.blog)
2 điểm bởi GN⁺ 2025-06-29 | 1 bình luận | Chia sẻ qua WhatsApp
  • Cận dưới đã biết của BB(6) lại tăng vọt, xác nhận rằng thời gian dừng tối đa của máy Turing 6 trạng thái vượt xa mọi quy mô thực tế có thể quan sát được
  • BB(6) là số bước tối đa mà một máy Turing 6 trạng thái, 2 ký hiệu có thể chạy trước khi dừng, khi bắt đầu từ một băng toàn số 0
  • Sau cải thiện của Pavel Kropitz vào năm 2022, mxdys lại đẩy cận dưới lên mức lớn hơn 10 được lũy thừa lặp lại 10 triệu lần
  • Kết quả mới nhất cho thấy BB(6) ít nhất là 2 pentated to 5, tức xuất hiện cả phép toán cao hơn một bậc so với lũy thừa lặp lại
  • BB(5) đã được xác định là 47,176,870, nhưng BB(6) lớn áp đảo, dẫn tới suy đoán rằng điểm mà BB(n) trở nên độc lập với hệ tiên đề ZFC có thể là ở n=7, 8 hoặc 9

Cận dưới của BB(6) lại tăng

  • Trước năm 2022, với BB(6) người ta chỉ biết rằng BB(6) > khoảng 10^36,534, và Pavel Kropitz đã cải thiện con số này lên mức lớn hơn 10 được lũy thừa lặp lại 15 lần
  • Tetration là phép lũy thừa lặp lại
    • Ví dụ, số tạo bằng cách xếp 10 chồng lên nhau 15 lần có dạng 10 mũ 10 mũ 10 mũ … kéo dài 15 tầng
  • Tristan Sterin, người tổ chức BBchallenge, cho biết thành viên nhóm mxdys đã tiếp tục nâng cận dưới của BB(6)
  • Cải thiện tiếp theo của mxdys cho thấy BB(6) ít nhất là 2 tetrated to 2 tetrated to 2 tetrated to 9
    • Đặc biệt, BB(6) ít nhất là 2 pentated to 5
    • Pentation là phép lặp lại tetration, tức một phép toán cao hơn một bậc so với việc tetration lặp lại phép lũy thừa

Khác biệt cực đoan giữa BB(5) và BB(6)

  • BB(6) là số Busy Beaver thứ 6
    • Xét các máy Turing 6 trạng thái
    • Bảng chữ cái là {0,1}
    • Băng đầu vào ban đầu toàn là 0
    • Đây là số bước chạy tối đa có thể có trước khi dừng
  • Nhóm quốc tế BBchallenge năm ngoái đã xác định BB(5) là 47,176,870
  • Khi chuyển từ BB(5) sang BB(6), hàm Busy Beaver nhảy vọt từ quy mô vài chục triệu lên kích thước vượt khỏi phạm vi của hiện thực có thể quan sát được

Những con số gần như không còn trực giác để hình dung

  • Ngay cả ở thời điểm BB(6) > 10 được lũy thừa lặp lại 10 triệu lần, việc giải thích bằng trực giác gần như đã bất khả thi
  • Chẳng hạn, có thể ví rằng nếu có chừng ấy hạt cát, bạn có thể lấp đầy số bản sao của vũ trụ quan sát được với số lượng xấp xỉ như vậy
  • Phép ví von này cho thấy con số đó áp đảo đến mức lớn hơn hẳn các con số mang tầm vũ trụ như 10^100, nên dù đem chia đi thì nó vẫn gần như giữ nguyên cùng cấp độ khổng lồ ban đầu

Khả năng hạ thấp ước lượng về tính độc lập với ZFC

  • Việc BB(6) lớn đến vậy không có nghĩa là mọi suy nghĩ về hàm Busy Beaver đều thay đổi
  • Khả năng BB(6) không chỉ ở mức tương đối nhỏ như 10^36,534 mà nằm trong miền của các phép toán lặp vốn dĩ từ trước đã là một khả năng mở
  • Nay khi cận dưới thực tế đã được xác nhận ở quy mô như vậy, ước lượng về điểm mà giá trị của BB(n) trở nên độc lập với hệ tiên đề tập hợp ZFC có thể sẽ được kéo xuống thấp hơn
    • Trước đây có thể người ta nghĩ tới vùng quanh n=20 hoặc 30
    • Giờ đây có thể là n=7, 8 hoặc 9
  • Kết quả hiện đã biết về tính độc lập với ZFC là BB(n) trở nên độc lập với ZFC ở mức n=643

Cập nhật riêng: STOC 2025

  • Tại Prague, nơi STOC 2025 diễn ra, tác giả đã gặp nhiều nhà nghiên cứu và tiếp nhận thêm thông tin mới
  • Tựa bài giảng toàn thể tại STOC là The Status of Quantum Speedups
  • Bạn đọc quan tâm có thể xem PowerPoint slides của bài giảng đó

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-06-29
Ý kiến trên Hacker News

  • Trên máy chủ Discord của bbchallenge, mọi người đang tích cực suy đoán xem cần bao nhiêu trạng thái máy Turing để vượt qua Graham's Number, vốn lớn hơn rất nhiều so với 2^^2^^2^^9 mà nhà vô địch BB(6) mới nhất đã đạt được
    Nhìn vào functional busy beaver https://oeis.org/A333479, có vẻ hành vi ở cấp độ Graham có thể xuất hiện nhanh bất ngờ. Chỉ cần một lambda term 49 bit
    Chỉ có 77,519,927,606 closed lambda term không vượt quá kích thước đó https://oeis.org/A114852, trong khi có 4^12*23836540=399910780272640 máy Turing 6 trạng thái khác biệt https://oeis.org/A107668
    Vì chỉ với 6 trạng thái đã đạt tới pentation, nên giờ có khá nhiều người cho rằng với 7 trạng thái có thể vượt qua Graham's Number. Dù vậy tôi vẫn thấy đây là điều khá đáng kinh ngạc. Vài ngày trước tôi còn cá cược lớn với một người trong số đó về việc liệu trong 10 năm tới có xuất hiện chứng minh BB(7)>Graham's hay không, nên cũng tò mò mọi người nghĩ sao

    • Tôi không dám tỏ ra là chuyên gia, nhưng BB(7) có lẽ sẽ lớn hơn Graham's Number
      BB phải tăng nhanh hơn bất kỳ dãy số tính được nào. Rốt cuộc điều đó có nghĩa cụ thể gì với BB(7) thì vẫn khá mang tính diễn giải bằng trực giác, nhưng cảm giác là nó phải leo thang rất nhanh trên chiếc thang về độ mạnh của các toán tử. Cuối cùng nó phải tăng nhanh hơn bất kỳ toán tử tính được nào mà ta định nghĩa, bao gồm chẳng hạn up-arrow^n hay up-arrow^f(n) với hàm tính được f
      Theo trực giác của tôi, mức tăng từ 47 million lên 2^^2^^2^^9 có vẻ lớn hơn về mặt chất lượng trong độ mạnh toán tử cần thiết, so với mức tăng từ 2^^2^^2^^9 lên Graham's Number. Graham's Number là g_64, trong đó g đại khái ở cao hơn một bậc so với up_arrow^n, nên có lẽ BB(7)>Graham's Number là điều khá khả thi

  • Việc một con số như BB(748), lại còn là một số không tính được, có thể “độc lập với ZFC” thật sự làm tôi choáng váng. Cảm giác như một kiểu nhầm lẫn phạm trù

    • Điều khiến BB(748) trở nên độc lập với ZFC không phải là chính giá trị đó, mà là vì một trong các máy 748 trạng thái, TM_ZFC_INC, được thiết kế để tìm một mâu thuẫn trong ZFC, tức là chứng minh của FALSE, và chỉ dừng khi tìm thấy nó
      Vì thế, chứng minh BB(748)=N phải cho thấy TM_ZF_INC dừng trong vòng N bước, hoặc chứng minh rằng nó sẽ không bao giờ dừng. Nếu giả sử ZFC là nhất quán, thì theo kết quả nổi tiếng của Gödel, cả hai điều này đều là bất khả thi
    • Thứ không tính được là BB(n). Tức là không tồn tại thuật toán nào, với mọi n, có thể xuất ra giá trị của BB(n)
      BB(748) thì tính được. Theo định nghĩa, đó là số lượng ký tự 1 mà một máy Turing nào đó với 748 trạng thái ghi ra, và chính máy đó tính ra BB(748)
      Bản thân con số ấy chỉ đơn giản là một số nguyên lớn đến mức không thể tưởng tượng nổi. Tính độc lập với ZFC xuất hiện khi ta cố chứng minh rằng đây chính là con số ta đang tìm. Để làm được vậy, cần một lý thuyết mạnh hơn ZFC, có thể nắm bắt được tính chất của các máy Turing 748 trạng thái
    • Điều đáng ngạc nhiên hơn là việc người ta từng nghĩ rằng một đoạn văn bản ngắn đến mức dư sức viết trên mặt sau tờ giấy, như các tiên đề ZFC, lại có thể “đủ” để nắm bắt chân lý số học hay các khía cạnh của thực tại vật lý chủ yếu liên quan đến hoạt động của loài người
      Việc hành vi của một máy Turing 6 trạng thái có thể không dự đoán được chỉ bằng vài dòng văn bản thì hoàn toàn không làm tôi ngạc nhiên
      Ngay khi Gödel công bố định lý bất toàn thứ nhất, tôi đã nghĩ cả giới toán học hẳn sẽ lao hết tốc lực vào việc tìm thêm tiên đề. Nhưng suốt gần một thế kỷ, công trình của Gödel lại thường bị xem như một sự thật kỳ lạ chỉ nằm trong góc hẹp của nền tảng học, hơn là một chương trình chủ đạo. Tôi biết đến Feferman, Friedman và vài người khác, nhưng nghiên cứu trong lĩnh vực này vẫn ít hơn rất nhiều so với hầu hết các chủ đề toán học khác
    • Không phải bản thân con số là độc lập với ZFC. Mọi số nguyên đều biểu diễn được trong ZFC. Thứ độc lập với ZFC là quá trình tính BB(748)
    • Từng con số riêng lẻ thì không phải là không tính được. Không có cặp nào gồm một con số và một chứng minh trong ZFC chứng minh rằng con số đó là giá trị của BB(748)
      Vì vậy cũng không có chương trình nào mà ZFC có thể chứng minh là sẽ xuất ra giá trị BB(748). Nhưng cũng như với mọi con số khác, vẫn tồn tại chính chương trình xuất ra BB(748)

  • Người ta đã biết rằng BB(14) lớn hơn Graham's Number, nhưng nhìn vào kết quả lần này thì có vẻ BB(7) cũng có lẽ sẽ lớn hơn Graham's Number
    Theo trực giác, kỹ thuật cần để đi từ pentation tới Graham's Number có vẻ đơn giản hơn kỹ thuật cần để đi từ 47,176,870 tới 2 5

  • Khi thấy giải thích rằng 왼쪽 위첨자 nghĩa là tetration, tức lũy thừa lặp, ban đầu tôi còn tưởng đó là lỗi đánh máy. Đây là lần đầu tôi biết đến tetration

    • Trước đây tôi cũng từng thấy rồi, nhưng hồi đó tôi dùng ký hiệu mũi tên lên của Knuth vì thích việc nó tổng quát hóa rất gọn https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
    • Tiếp nối chuỗi phép lặp đó, lần này tôi cũng впервые biết đến pentation

  • Tôi không hiểu đoạn: “Hãy tưởng tượng có 10,000,000sub10 hạt cát. Khi đó bạn có thể lấp đầy khoảng 10,000,000sub10 vũ trụ quan sát được bằng số cát đó”
    Có phải là lấy thể tích của vũ trụ quan sát được chia cho thể tích trung bình của một hạt cát rồi làm tròn bỏ qua không? Chênh lệch số chữ số đó còn lớn hơn rất nhiều so với tổng khối lượng của vũ trụ vốn thường được dùng để so sánh

    • Đúng. Việc chia theo tỷ lệ đó thực ra gần như không ảnh hưởng gì, vì trong ký pháp này các số “liền kề” đã tạo ra thay đổi lớn hơn rất nhiều
      10↑↑10,000,000 / (số hạt cát trong một vũ trụ) chẳng hạn vẫn lớn áp đảo so với 10↑↑9,999,999
      Trong hệ dùng những con số như thế này, gần như không có cách diễn đạt nào tốt hơn cho (số rất lớn)/(một con số chỉ ở quy mô vũ trụ) ngoài việc viết đúng như vậy, và ở phía ký pháp của số cực lớn thì cuối cùng nó gần như vẫn được làm tròn thành (số rất lớn)
    • Với tetration, ta không còn xử lý quy mô của số chữ số nữa, mà là quy mô của quy mô số chữ số
    • Một ví dụ quen thuộc hơn cho kiểu so sánh này là, xét theo chữ số có nghĩa thì 1 tỷ trừ 1 triệu vẫn là 1 tỷ
    • Chính xác. Con số này lớn đến mức 10^100000 hay việc một vũ trụ chứa bao nhiêu hạt cát đều chẳng đáng kể, nên dù có chia cho lượng đó thì về thực chất cũng không đổi. Ít nhất nó sẽ không giảm xuống gần mức 9,999,999sub10
    • Đúng. Đó chỉ là chênh lệch số chữ số ở mức thông thường. Ngay cả 10,000,000^10,000,000 cũng đã lớn đến mức sự khác biệt kiểu đó không còn quan trọng, huống chi là sau khi lũy thừa hóa chính số mũ đó thêm chín lần nữa

  • How Much Math Is Knowable? của Scott Aaronson [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    Vài tháng trước cũng đã được đăng trên HN: https://news.ycombinator.com/item?id=43776477

  • Logic phong phú nhất là gì mà chỉ với máy Turing 5 trạng thái thôi vẫn có thể liệt kê các chứng minh?

    • Câu hỏi đó phụ thuộc vào việc bạn xem liệt kê là gì, nhưng có một câu hỏi liên quan là “logic phong phú nhất nào mà không thể chứng minh được việc dừng hay không của mọi máy Turing 5 trạng thái?” Nói cách khác, logic phong phú nhất nào mà trong đó tính dừng của một máy Turing 5 trạng thái nào đó là độc lập
      Tôi có suy nghĩ đôi chút về phiên bản này, nhưng vì không đủ chuyên môn về logic bậc nhất nên không đi xa được. Theo những gì tôi biết, Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA là một trong những máy khó chứng minh không dừng nhất về mặt toán học https://arxiv.org/abs/2407.02426, nên nếu có một lý thuyết có thể chứng minh Skelet #17 không dừng thì rất có thể nó cũng sẽ quyết định được các máy 5 trạng thái còn lại
    • Điều đó hoàn toàn phụ thuộc vào cách diễn giải các chuỗi nhị phân hữu hạn thành việc liệt kê các chứng minh logic

  • Khi đọc mô tả “BB(6) là số Busy Beaver thứ sáu, tức số bước tối đa mà một máy Turing 6 trạng thái với bảng chữ cái {0,1} có thể thực hiện trước khi dừng khi chạy trên băng ban đầu toàn số 0”, tôi lại có cảm giác là, với tư cách người không chuyên, mình hiểu quá rõ mất rồi
    Đây rõ ràng là một blog hardcore dành cho những người đã làm nghiên cứu kiểu này hàng chục năm. Thật thú vị khi tình cờ bắt gặp một bài viết đặc quánh, đầy thuật ngữ, được viết không chút dè dặt cho đúng độc giả mục tiêu của nó

    • Nếu đã được đào tạo cử nhân khoa học máy tính thì dù lần đầu gặp bài toán Busy Beaver, bạn vẫn có thể nắm đại khái chuyện gì đang xảy ra từ phần giải thích đó
      Đúng là thuật ngữ chuyên biệt, nhưng cho rằng chỉ những người đã đầu tư hàng chục năm mới tiếp cận được thì là đang tự đánh giá thấp bản thân
    • Định nghĩa đó là nội dung chuẩn trong lý thuyết khoa học máy tính ở bậc đại học. Chỉ là nó có thể không phải kiến thức chuẩn trong kỹ nghệ phần mềm

  • Những con số lớn đến mức đó con người không thể hình dung được. Cách biểu diễn số không chỉ có đếm đơn thuần
    Chẳng hạn, có thể xem ngay cả một hạt cát cũng có vô hạn trạng thái khả dĩ. Số thực là vô hạn, nên cũng có thể nói một hạt cát biểu diễn được BB(6). Tổ hợp có thể tăng theo cấp số mũ, nên có lẽ kiểu biểu diễn đó cũng hữu ích

    • Từ một ngưỡng nào đó trở đi, số lớn không còn gần với “một lượng lớn” nữa mà gần với độ mạnh nhất quán của một hệ hình thức hơn nhiều
      Tức là vấn đề một hệ có thể giả vờ không mâu thuẫn được bao lâu trước khi bị lộ. Một hệ mâu thuẫn giả vờ nhất quán thông qua BB(3) sẽ bị “bóc trần” nhanh hơn rất nhiều so với hệ giả vờ nhất quán thông qua BB(6). Ở đây, giả vờ nhất quán nghĩa là khẳng định rằng với một n nào đó, mọi chương trình chạy lâu hơn BB(n) bước đều không dừng
    • Nếu vũ trụ được làm tròn tới đơn vị Planck gần nhất, thì số trạng thái mà một hạt cát có thể có đột nhiên không còn nhiều đến vậy nữa
      Với tôi, việc lôi độ chính xác vô hạn vào để làm cho nó có vẻ dễ xử lý giống một tiểu xảo hơn. Khi mô tả độ lớn thì dùng số nguyên vẫn tốt hơn
    • Ví dụ này gây rối. Nếu số hạt cát và số vũ trụ quan sát được là như nhau, thì chẳng phải là một hạt cát cho mỗi vũ trụ sao?

  • Tò mò liệu vũ trụ quan sát được có thực sự đủ lớn để viết ra giá trị chính xác của BB(6) hay không

    • Nếu xem vũ trụ quan sát được là một hệ kín thì có thể thử áp dụng giới hạn Bekenstein
      Dùng R ≈ 46.5 billion light-years, tức bán kính của vũ trụ quan sát được, và E ≈ tổng hàm lượng khối lượng-năng lượng của vũ trụ quan sát được
      Khối lượng-năng lượng thường bao gồm vật chất thông thường, vật chất tối và năng lượng tối. Theo ước tính hiện nay, vũ trụ quan sát được có lượng tương đương khối lượng-năng lượng xấp xỉ 10^53 kg
      Thế vào S ≤ 2πER/ℏc thì lượng thông tin tối đa ra khoảng cỡ 10^120 bits
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      Nên là không thể
    • Chắc chắn là không đủ. Lượng thông tin có thể lưu trữ trong vũ trụ vào khoảng 10^120 bit. Kể cả nếu tôi sai tới một nghìn tỷ chữ số thì kết quả cũng không thay đổi
    • Ngay cả con số khởi đầu trong bài cũng đã là ¹⁵10. Điều này có nghĩa là 10^(¹⁴10), và vì thế nó có ¹⁴10 chữ số. Vậy nên không thể viết ra được
    • Có lẽ ý ở đây là trạng thái mà mọi phần của biểu diễn đầy đủ đều cùng tồn tại đồng thời. Nếu không cần tồn tại đồng thời, thì khi thời lượng tồn tại của vũ trụ là vô hạn, có lẽ vẫn “viết ra” được. Tôi không rõ cái chết nhiệt sẽ ảnh hưởng thế nào ở đây, nên chỉ là “có lẽ” thôi
      Tuy nhiên trong không-thời gian tương đối tính, khái niệm “đồng thời” không được định nghĩa rõ ràng. Các bình luận cùng nhánh chắc chắn đúng trong hệ quy chiếu mà bức xạ nền vi sóng vũ trụ gợi ý. Nhưng tôi vẫn tự hỏi liệu trong một số hệ quy chiếu nào đó có thể có cách cắt không-thời gian sao cho cách diễn đạt “đồng thời” trở nên khả dĩ hơn không