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

BB(3, 4) > Ack(14)

Ngày 22 tháng 5 năm 2024
- Pavel đã phát hiện một máy Turing (Turing Machine, TM) 3 trạng thái 4 ký hiệu
- Máy này tính một hàm ở mức Ackermann và dừng lại với chính xác (2↑155)+14 ký hiệu khác 0
- Ký pháp mũi tên lên của Knuth trở nên hơi bất tiện, nên có thể xấp xỉ như sau: BB(3,4)>Ack(14)
- Ở đây Ack(14) được định nghĩa là số Ackermann thứ 14: Ack(n)=n↑nn
- Đây là TM đầu tiên được phát hiện "ngoài thực tế" có thể mô phỏng một hàm ở mức Ackermann

Máy

Bảng chuyển trạng thái

| 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
- 0∞32g153(0)+12161 Z> 0∞
- Chính xác σ=2g153(0)+18=(2↑155)+14 ký hiệu khác 0 còn lại trên băng

Ghi công

Người phát hiện
- TM này được Pavel Kropitz(@uni) phát hiện và chia sẻ trên Discord vào ngày 25 tháng 4 năm 2024
- Mã của anh ấy không thể chỉ định một cận dễ đọc đối với điểm số TM, và đơn giản được ghi là Halt(SuperPowers(13))
- Anh ấy bắt đầu xác minh kết quả này bằng một "trình xác thực chứng minh quy nạp" mới
- Vào ngày 20 tháng 5 năm 2024, anh ấy trích xuất được định nghĩa chính xác của gkn(m) và thu được cận σ>2↑153
- Matthew House(@LegionMammal978) đã tìm ra một dạng đóng đơn giản của gkn(0)=2↑k(n+2)2−2 vào ngày 22 tháng 5 năm 2024

Phân tích

Định nghĩa B(k,n,m)
```
B(k,n,m)=0∞32m+12k A> 1n
```

Chứng minh

0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

Định nghĩa gk(m)
```
g0(m)=m+1
gk+1(m)=gk2m+2(0)
```

Chứng minh bằng quy nạp kép

Quy tắc chính
```
B(k,n,m)→B(k,0,gk−1n(m))
```
Bổ đề 1
```
For all k≥1: 32k<B→2k+12k<B1
```

Hệ quả 2

For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

Định lý 3

For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

Giá trị chính xác

Định lý

For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

Hệ quả

For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

Kết luận
```
σ=2g153(0)+18=(2↑155)+14
```

Hoán vị

Bắt đầu từ trạng thái B
```
σB=2g63(0)+9=(2↑65)+5
```

Bắt đầu từ trạng thái C

σC=2g03(0)+3=(2↑05)−1=9 (dừng sau 72 bước)

TNF đã biến đổi

| 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Không phải Collatz

Điểm thú vị
- TM này đơn giản đến mức đáng ngạc nhiên
- Không có quy tắc kiểu Collatz
- Điều này không loại trừ khả năng tồn tại TM ở mức Ackermann kiểu Collatz

Trình xác thực chứng minh quy nạp

Mục tiêu dự án
- Đang phát triển một trình xác thực "chứng minh quy nạp"
- Phát triển một định dạng chứng chỉ chuẩn hóa để có thể xác minh nhiều loại chứng minh quy nạp khác nhau
- Vẫn đang ở giai đoạn đầu, nhưng đã thành công trong việc chứng minh hoạt động của nhiều TM

Ý kiến của GN⁺

Điểm thú vị
- Bài viết này rất hữu ích để hiểu độ phức tạp của máy Turing và hàm Ackermann
- Điểm hấp dẫn là những quy tắc đơn giản có thể thực hiện các phép tính phức tạp
Góc nhìn phê bình
- Cần có nền tảng toán học để hiểu được độ phức tạp của cỗ máy này
- Nội dung tập trung nhiều hơn vào sự thú vị về mặt lý thuyết hơn là ứng dụng thực tiễn
Công nghệ liên quan
- Trình xác thực chứng minh quy nạp có thể đóng góp lớn cho việc phát triển các hệ thống chứng minh toán học tự động
- Cũng có khả năng được áp dụng cho các bài toán tính toán phức tạp khác
Điểm cần cân nhắc
- Khi áp dụng công nghệ này, cần cân nhắc độ chính xác và hiệu quả của quá trình xác minh
- Cần thời gian để hiểu và áp dụng các khái niệm toán học phức tạp

1 bình luận

GN⁺ 2024-05-25

Ý kiến trên Hacker News

Tóm tắt các bình luận trên Hacker News

Chương trình máy Turing đơn giản
Trái với suy nghĩ rằng chương trình máy Turing sẽ là kiểu mã spaghetti phức tạp, chương trình mới này tương đối đơn giản. Có ba trạng thái (A, B, C), trong đó trạng thái B chuyển quyền điều khiển sang A và C, còn A và C không biết về nhau mà chỉ chuyển điều khiển về B. Đây là một cấu trúc mô-đun; trong mã spaghetti thực sự, mỗi trạng thái có thể chuyển điều khiển sang mọi trạng thái khác.
Các đặc điểm thú vị
Chương trình này không ghi ra ô trống, và mọi lệnh đều thay đổi trạng thái hoặc màu. Kỷ lục gia BB(3,4) mới có khoảng 64 bit thông tin. BBλ(49) với 49 bit vượt xa số Graham.
Ví dụ triển khai
Khi tự triển khai chương trình, kết quả là trạng thái B đổi 0 thành 2 và 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. Điều này tạo ra các chuỗi số 3 dài ra theo cấp số mũ.
Sự tương đồng với code golf
Tất cả điều này trông như một dạng code golf cực đoan. Một dự án sở thích cá nhân tên BitGrid chỉ có trạng thái 4 bit cho mỗi ô, và lưới 4x4 có thể đếm tối đa đến 2^64. Với các lưới nhỏ, cách nối các cạnh ảnh hưởng rất lớn đến kết quả.
Yêu cầu tài liệu diễn giải máy Turing
Có người đã xin tài liệu về cách diễn giải bảng. Có vẻ đây là mô tả của một máy Turing.
Giới hạn của máy Turing
Số lượng máy Turing có thể mô tả bằng một số lượng ký hiệu hữu hạn là có giới hạn. Thật đáng kinh ngạc khi một số máy Turing có thể thực hiện số bước khổng lồ trước khi dừng.
Yêu cầu giải thích điểm đặc biệt
Có người muốn được giải thích vì sao tập lệnh cụ thể này lại ấn tượng. Họ cũng tò mò hàm ở mức Ackermann là gì và thực sự nó đang tính toán điều gì.
Sự hứng thú với chân lý toán học
Một kết quả có vẻ vô dụng lại thú vị hơn cả những tiến bộ LLM rất hữu ích. Có lẽ vì nó tự nhiên hấp dẫn nhờ những chân lý toán học đơn giản.
So sánh BB(5) và BB(3,4)
Có câu hỏi liệu BB(5) có lớn hơn BB(3,4) không. Trên trang bbchallenge.org, BB(5) được ghi là khoảng 47 triệu, nhưng BB(3,4) thì lớn hơn nhiều.
Tác giả cung cấp ngữ cảnh
Mọi người đánh giá cao việc tác giả đã cung cấp thêm một phần ngữ cảnh.