Kết quả BB(3, 4) > Ack(14)

 (sligocki.com)
1 điểm bởi GN⁺ 2024-05-25 | 1 bình luận | Chia sẻ qua WhatsApp
  • Đã phát hiện một TM vô địch Busy Beaver 3 trạng thái 4 ký hiệu mới, và nó được tính là để lại ((2 \uparrow^{15} 5) + 14) ký hiệu khác 0 khi dừng
  • Con số này rất lớn ngay cả theo ký hiệu mũi tên lên của Knuth, nên được tổng kết thành cận dưới (BB(3,4) > Ack(14)), vượt số Ackermann thứ 14 được định nghĩa bởi (Ack(n)=n \uparrow^n n)
  • Hành vi cốt lõi của TM có thể được nén gần như thành (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), nhưng để chứng minh điều này cần quy nạp kép
  • Nhờ biểu thức đánh giá dạng đóng của Matthew House, (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2), có thể viết chính xác điểm số cuối cùng (\sigma=(2 \uparrow^{15}5)+14)
  • TM này mô phỏng một hàm ở mức Ackermann mà không có nhánh phần dư kiểu Collatz, và cũng được dùng làm ca kiểm chứng cho Inductive Proof Validator đang được phát triển

Quy mô của nhà vô địch Busy Beaver mới

  • Pavel Kropitz đã phát hiện một nhà vô địch Busy Beaver 3 trạng thái 4 ký hiệu mới
  • TM này có thể tính một hàm “mức Ackermann”, và khi dừng sẽ để lại trên băng số lượng ký hiệu khác 0 như sau
    • ((2 \uparrow^{15} 5) + 14)
  • Vì đây là một giá trị rất lớn ngay cả theo ký hiệu mũi tên lên của Knuth, cận dưới được tóm tắt như sau
    • (BB(3,4) > Ack(14))
  • Ở đây (Ack(14)) là số Ackermann thứ 14, được định nghĩa bởi (Ack(n)=n \uparrow^n n)
  • Trong phạm vi đã biết, đây là trường hợp đầu tiên trong số các TM được phát hiện qua quá trình tìm kiếm thực tế có thể mô phỏng một hàm mức Ackermann

Định nghĩa TM và cấu hình cuối cùng

  • Chuỗi chuyển trạng thái của TM như sau
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • Bảng chuyển trạng thái được định nghĩa cho các trạng thái A, B, C và các ký hiệu 0, 1, 2, 3
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • Cấu hình cuối cùng như sau
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Từ cấu hình này, điểm số (\sigma) được tính chính xác
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Quá trình phát hiện và kiểm chứng

  • Pavel Kropitz đã chia sẻ TM này trên Discord vào ngày 25/04/2024
  • Khi đó, mã chưa thể chỉ định một cận dưới điểm số mà con người đọc được, và hiển thị kết quả là Halt(SuperPowers(13))
    • Điều này có nghĩa là phép chứng minh cần 13 tầng quy tắc quy nạp
  • Sau đó, quá trình kiểm chứng bằng Inductive Proof Validator mới được bắt đầu
  • Ngày 20/05/2024, việc kiểm chứng hoàn tất, định nghĩa chính xác của (g_k^n(m)) được trích xuất, và nhờ đó thu được cận dưới (\sigma > 2 \uparrow^{15} 3)
  • Matthew House đã phát hiện biểu thức đánh giá dạng đóng đơn giản sau vào ngày 22/05/2024
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Biểu thức đánh giá này cho phép biểu diễn giá trị chính xác của (\sigma)

Phân tích hành vi và chứng minh quy nạp kép

  • Định nghĩa cấu hình sau
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • Cấu hình ban đầu sau 241 bước sẽ đạt tới trạng thái sau
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • Quy tắc cốt lõi như sau
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), với (k \ge 1)
  • (g_k) được định nghĩa bằng truy hồi sau
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • Toàn bộ hành vi đơn giản đến mức gần như có thể nén thành một quy tắc duy nhất, nhưng bản thân quy tắc này phải được chứng minh bằng quy nạp kép
  • Các bổ đề và hệ quả xử lý quá trình trạng thái B xử lý các khối 3 và 2^k để tạo ra các 1
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • Định lý 3 cho thấy quy tắc cốt lõi đúng với mọi (k \ge 1, n \ge 0, m \ge 0)
    • Trường hợp cơ sở (k=1) được xử lý bằng quy nạp theo (n)
    • Bước quy nạp sử dụng đồng thời giả thiết quy nạp theo (k) và giả thiết quy nạp theo (n)

Tính giá trị chính xác

  • (g_k) có một đánh giá dạng đóng tương đối đơn giản, chỉ dùng mũi tên lên Knuth và phép số học
  • Với mọi (k \ge 0, m \ge 0), điều sau đúng
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • Ở đây định nghĩa (a \uparrow^0 b = ab)
  • Kết quả này được chứng minh bằng quy nạp theo (k)
    • Ở trường hợp cơ sở (k=0), ta có (g_1(m)=2m+2)
    • Ở bước quy nạp, dùng việc áp dụng lặp ((2 \uparrow^k)^n)
  • Dạng đóng dựa vào sự trùng hợp rằng (2 \uparrow^k 2 = 4) đúng với mọi (k)
    • Nếu tham số chỉ hơi khác và trở thành dạng ((2 \uparrow^k)^{2m+2}5), có lẽ sẽ khó thu được biểu diễn dạng đóng
  • Theo hệ quả, với mọi (k \ge 0, n \ge 0), điều sau đúng
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • Điểm số cuối cùng được suy ra trực tiếp như sau
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Kết quả hoán vị khi đổi trạng thái bắt đầu

  • Nếu đổi trạng thái bắt đầu thành B hoặc C, sẽ thu được các kết quả liên quan nhỏ hơn
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • Điểm số khi trạng thái bắt đầu là B như sau
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Khi trạng thái bắt đầu là C, máy dừng ở bước 72, và điểm số như sau
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • Hoán vị đầu tiên bắt đầu từ B cũng là một TM BB(3,4) thuộc nhóm dẫn đầu khác
  • Khi chuyển nó sang TNF, chuỗi chuyển trạng thái trở thành
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Sự đơn giản khi không có quy tắc kiểu Collatz

  • Một điểm thú vị của TM này là nó đơn giản hơn dự kiến
  • Không có quy tắc kiểu Collatz hoạt động khác nhau tùy theo phần dư của giá trị
  • Vẫn còn quá sớm để biết liệu sự thống trị của các TM kiểu Collatz đã kết thúc hay chưa
  • Có suy đoán rằng các TM kiểu Collatz mức Ackermann có thể vẫn còn, nhưng do thiên lệch lựa chọn nên chưa dễ thấy ngay
  • Lý do TM này được phát hiện là TM mức Ackermann đầu tiên có thể là vì nó đủ đơn giản để chứng minh dừng mà không cần triển khai số học modular trên một hàm mức Ackermann

Inductive Proof Validator

  • TM này phù hợp làm ca kiểm thử cho Inductive Proof Validator đang được phát triển
  • Mục tiêu của dự án là tạo một định dạng chứng chỉ chuẩn hóa cho “chứng minh quy nạp”
  • Ở đây, “chứng minh quy nạp” được dùng như một thuật ngữ bao quát chỉ suy luận tiến và phân tích dựa trên quy tắc nói chung
  • Cách làm là: nếu ai đó có một “inductive decider”, họ có thể viết các quy tắc tương ứng theo định dạng này, và validator có thể kiểm tra chứng minh đó
  • Hệ thống vẫn còn rất thô sơ và chưa sẵn sàng để sử dụng thực tế, nhưng sau một ít thao tác thủ công, nó đã được dùng để chứng minh hành vi của nhiều TM, bao gồm TM này

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-25
Ý kiến trên Hacker News

  • Người ta dễ nghĩ rằng các chương trình máy Turing chạy rất lâu hẳn phải cực kỳ phức tạp hoặc là kiểu mã spaghetti, nhưng nhà vô địch mới lần này gần như là một phản ví dụ
    Chỉ có ba trạng thái A, B, C; B chuyển điều khiển sang A và C, nhưng A và C không “biết” nhau mà chỉ quay lại B
    Nếu thật sự là mã spaghetti thì mỗi trạng thái đã có thể nhảy sang mọi trạng thái khác, còn cái này lại là một dạng cấu trúc mô-đun
    Ngoài ra nó không bao giờ ghi ô trống, và mọi lệnh đều thay đổi ít nhất một trong hai thứ là trạng thái hoặc ký hiệu, nên cũng không có “lệnh lười” chỉ di chuyển vị trí như B1 -> 1LB

    • Ngay trong dự án bbchallenge cũng có tranh luận rằng các đặc tính của những nhà vô địch chạy lâu hiện tại có thực sự là đặc tính của các máy chạy lâu nhất ở kích thước đó hay chỉ là hiệu ứng đèn đường, tức chỉ nhìn thấy những đặc tính dễ cho việc tìm kiếm tự động và chứng minh
      Chưa thể biết được trước khi loại trừ toàn bộ không gian tìm kiếm, dù là một cách tất định hay heuristic
      Mọi kích thước vượt quá BB(5, 2) được cho là đều chứa các máy hỗn loạn/giả ngẫu nhiên mà ta kỳ vọng sẽ chạy mãi mãi, nhưng không thể chứng minh nếu không có đột phá lớn trong số học
      Dù vậy, tôi không nghĩ các máy chạy rất lâu có thể hoàn toàn hỗn loạn
      Nếu chúng phun ra các ký hiệu như ngẫu nhiên lên băng thì sớm muộn cũng sẽ rơi vào cấu hình dừng, cấu hình lặp, hoặc một mẫu đã được đơn giản hóa
      Tuy nhiên vẫn có thể tồn tại những máy mô phỏng thứ gì đó hỗn loạn ở cấp độ cao hơn, tiêu tốn một lượng thời gian vô lý giữa mỗi bước cấp cao rồi cuối cùng mới dừng
    • Máy Turing với n trạng thái và s ký hiệu chỉ có thể chuyển sang tối đa n trạng thái khác nhau
      Vì vậy nếu s=4 hay s=2 thì chỉ các máy Turing rất nhỏ mới có thể trông giống mã spaghetti

  • Kỷ lục gia BB(3,4) mới là như sau
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    (t', d, s') ở hàng s, cột t nghĩa là phép chuyển khi ký hiệu dưới đầu đọc băng là t trong trạng thái s
    Nó ghi đè ký hiệu t thành t', di chuyển sang trái/phải theo hướng d, rồi đổi trạng thái thành s'; nếu s' == Z thì dừng
    Điều này tương ứng với 3*4*log2(4*2*log2(4+1)), tức khoảng 64 bit thông tin
    Trong khi đó chỉ với 49 bit, BBλ(49) đã vượt xa số Graham https://oeis.org/A333479

    • Việc đếm số lượng máy Turing khác nhau không hề đơn giản
      Cách tính trên là cách rộng nhất, giả sử mỗi ô có thể nhận một tổ hợp (ký hiệu, hướng, trạng thái) tùy ý, nên nó đã ước lượng khá dư số bit cần thiết để mô tả một máy Turing bất kỳ
      Với BB(3, 4), nếu dùng Tree Normal Form, tức thuật toán Brady (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), thì chỉ có khoảng 600 tỷ máy Turing khác nhau, tức dưới 40 bit
    • Trong chương trình này, 1R trong 1RZ có vẻ là một giá trị chọn tùy ý
      Vì nó dừng ngay tại đó nên nội dung còn lại trên băng hay việc đầu đọc di chuyển đi đâu đều không quan trọng
      Thực ra việc ghi 1 cũng không quá quan trọng, nhưng nếu ghi 0 thì có lẽ đã không tối ưu
      Trước đó ở vị trí ấy đã có 2, và dù đổi thành 1 thì nếu tính theo số lượng ký hiệu trên băng, 2 cũng sẽ được tính y như vậy
    • Tôi không hiểu lắm hạng log2(4+1) xuất hiện từ đâu
      Tính 3*4*log2(4*2*log2(4+1)) thì ra khoảng 51, và từ góc nhìn của người không chuyên, tôi tưởng phải là 3*4*log2(4*2*4) = 60
      Hay là phải là 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?

  • Vì tò mò về cách nó hoạt động nên tôi đã triển khai ở đây: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    Chạy thử một lúc là có thể thấy chuyện gì đang diễn ra
    Trạng thái B đổi 0 thành 2, 1 thành 1 rồi chuyển sang C, còn trạng thái C đổi 3 thành 2 rồi chuyển sang A
    Vì vậy để sửa 2 -> 1 thì phải đi qua toàn bộ các 3, nên nó liên tục làm tăng theo hàm mũ các đoạn liên tiếp của số 3

    • Tạo ra một máy Turing tăng trưởng theo hàm mũ mãi mãi là chuyện khá dễ
      Phần thực sự khó hiểu là sau một số bước lớn đến mức không thể tưởng tượng nổi, vì sao nó cuối cùng vẫn dừng

  • Nghe toàn bộ chuyện này như một kiểu code golf cực đoan
    Ở một hướng khác, có thể xem thử thứ gọi là BitGrid
    Với BitGrid, mỗi ô chỉ có trạng thái 4 bit, nên một lưới 4x4 ô dù thế nào cũng không thể đếm vượt quá 2^64
    Sẽ khá thú vị nếu tìm xem trên thực tế nó có thể đếm được đến đâu, và với các lưới nhỏ thì cách nối ở biên sẽ chi phối kết quả
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Có lẽ bảng này là mô tả của một máy Turing, nhưng sẽ hay hơn nếu có tài liệu nào đó giải thích cách diễn giải nó

    • trạng thái A, B, C tương ứng với đích của goto, còn màu 0, 1, 2, 3 là dữ liệu trong lúc chạy
      Ở mỗi trạng thái, nó đọc màu hiện tại rồi tùy theo màu đó mà thực thi lệnh “ghi ra màu nào, di chuyển sang trái/phải, chuyển sang trạng thái nào”
      Nếu chuyển sang C thì có thể biểu diễn nguyên xi bằng switch (SCAN) cùng với WRITE, RIGHT/LEFT, và goto
      Tôi tò mò không biết còn dư địa nào để viết lại logic này theo kiểu có cấu trúc hơn hoặc áp dụng tối ưu hóa khác không
    • Mỗi hàng là một trạng thái, mỗi cột là ký hiệu vừa đọc từ băng
      Ví dụ, hàng đầu cột đầu có nghĩa là “đã đọc ký hiệu 0 và trạng thái hiện tại là A”
      Ô trong bảng biểu thị hành động cần thực hiện; 1RB có nghĩa là “đổi ký hiệu trên băng thành 1, di chuyển sang phải một ô, rồi chuyển sang trạng thái B”
      Trạng thái Z tương ứng với trạng thái dừng
    • Với Python, chỉ cần có các hàm L(), R() để di chuyển chỉ số băng sang trái/phải, rồi tạo một bảng ánh xạ từ (trạng thái, ký hiệu hiện tại) sang (ký hiệu cần ghi, hàm di chuyển, trạng thái kế tiếp), sau đó lặp khi state != 'Z'
    • Giải thích đơn giản có ở https://bbchallenge.org/story#turing-machines
      1RZ có thể hiểu là chuyển dừng vì trạng thái Z không có quy tắc nào
      Wikipedia cũng có ví dụ bảng trạng thái máy Turing chi tiết hơn tại https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, và có thể xem vết thực thi của chính máy Turing này tại https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
    • Tôi đã tạo một kho nhỏ tập hợp các kỷ lục gia hiện tại và cả ví dụ chạy bằng Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Có lẽ giờ cũng phải cập nhật cái này rồi

  • Trích dẫn một kết quả lớn của khoa học máy tính nền tảng mà lại là liên kết Discord

    • Tôi không hiểu vì sao lại không được
      Ý tưởng rằng cách duy nhất hợp lệ để công bố kết quả khoa học là qua cái gọi là tạp chí bình duyệt, là di vật từ 200 năm trước khi cộng đồng khoa học còn đủ nhỏ để nằm trong số Dunbar
      Việc đến giờ người ta vẫn bám vào nó là vì một số học giả và nhà xuất bản có thế lực được hưởng lợi, chứ không phải vì nó thật sự có ưu điểm nào về mặt thúc đẩy tiến bộ khoa học
      Thậm chí nó còn có thể chịu phần trách nhiệm khá lớn cho khủng hoảng tái lập hiện đại
      Tôi hoàn toàn ủng hộ phương pháp khoa học, nhưng bình duyệt truyền thống thì theo tôi đã quá hạn dùng từ lâu rồi
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Dù sao thì đó cũng là một máy chủ Discord công khai, và có thể tìm liên kết mời ở góc trên bên phải của https://bbchallenge.org
      Tôi xem những thứ này giống ghi nguồn hơn là trích dẫn
      Lập luận chính chống đỡ cho kết quả đã được tái hiện trong bài blog dưới dạng chặt chẽ hơn nên tự nó đã đứng vững độc lập, còn liên kết Discord chỉ cung cấp bối cảnh lịch sử cho những ai quan tâm
    • Nếu tham gia những cuộc trò chuyện như thế này, nó khá giống với việc cùng nảy ý tưởng và phát triển chúng trên bảng đen trong phòng nghỉ, chỉ khác là có thể trích dẫn lại tương tác đó
      Nếu có thể bổ sung tài liệu học thuật vào đúng thời điểm thì đây là một thay đổi tích cực
    • Tôi hiểu sự khó chịu này, nhưng khá nhiều tiến bộ ấn tượng gần đây trong toán học đến từ cộng tác và lặp lại nhanh
      Ví dụ như dự án cải thiện cận trên khoảng cách giữa các số nguyên tố của Zhang, và ở khía cạnh này những công cụ liên lạc khác có thể không dễ thay thế Discord
      Phải đến nơi mà con người thực sự đang tụ tập
    • Việc tìm số busy beaver lớn hơn không hẳn là công việc nền tảng theo đúng nghĩa, mà gần với toán học giải trí hơn
      Nếu thật sự là nền tảng thì người ta đã gửi nó thành bài báo tạp chí để bình duyệt chứ không phải đăng lên blog

  • Với một máy Turing có thể mô tả bằng lượng ký hiệu không quá lớn như 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC, số khả năng là có hạn
    Vậy mà việc một số trong đó có thể chạy một số bước phi lý đến thế trước khi dừng thật sự rất đáng kinh ngạc

    • Có 2^60 máy Turing 3-trạng-thái 4-ký-hiệu như vậy
      Còn đáng kinh ngạc hơn nữa là các lambda term 49-bit có đầu ra, tức dạng chuẩn, vượt quá số Graham

  • Thành thật mà nói tôi không hiểu 100%, và có lẽ kết quả này cũng hầu như vô dụng, nhưng tôi vẫn bị nó cuốn hút hơn cả những bước tiến LLM hữu ích đến khó tin
    Có lẽ vì tôi tự nhiên bị hấp dẫn bởi chân lý toán học đơn giản hơn là các kết quả kỹ thuật “phức tạp”

  • Có phải là BB(5) > BB(3,4) mới đúng không?
    Trên https://bbchallenge.org có nói họ đang cố chứng minh hoặc bác bỏ phỏng đoán rằng BB(5) vào khoảng 47 triệu, trong khi BB(3,4) có vẻ lớn hơn nhiều

    • Đúng, có vẻ như BB(3, 4) >>> BB(5, 2)
      BB(5) = BB(5, 2), và BB(3, 4) có 12 chuyển tiếp (3*4) trong bảng trong khi BB(5, 2) chỉ có 10, nên cũng không quá ngạc nhiên
      Nhưng có vẻ BB(3, 4) >> BB(6, 2) nữa
      Vì hai bên có cùng số lượng chuyển tiếp, nên với các máy Turing nhỏ kiểu này, nhiều ký hiệu hơn có vẻ khá đáng giá