Vì sao BB(3, 3) lại khó: Bigfoot
(sligocki.com)- Máy Turing 3 trạng thái 3 ký hiệu Bigfoot là một trường hợp mà để chứng minh có dừng hay không từ băng trắng, ta phải giải một bài toán kiểu Collatz, cho thấy (BB(3, 3)) cũng có thể khó đến mức đó
- Cỗ máy này là một trong 160 ứng viên chưa được giải của (BB(3, 3)) trên bbchallenge.org, được định nghĩa bởi bảng chuyển
1RB2RA1LC_2LC1RB2RB_---2LA1LA - Hoạt động của nó quy về các quy tắc lặp trên cấu hình (A(a,b,c)), trong đó a tăng hoặc giảm tùy theo (b \bmod 6), và chỉ dừng khi (a) sắp giảm xuống dưới 0
- Từ băng trắng, sau 69 bước nó đạt tới (A(2,1,2)), và sau 24 triệu lần lặp thì (a) tăng đến (3,999,888), khiến khả năng dừng theo thực nghiệm trông cực kỳ thấp
- Dãy (b \bmod 6) là tất định, nhưng ở quy mô lớn lại trông giống một random walk lệch với xu hướng sang phải 2/3 và sang trái 1/3; để chứng minh nó chạy mãi, cần chỉ ra hàm kiểu Collatz này không bao giờ chạm tới chuyển tiếp dừng
Vì sao Bigfoot khiến (BB(3, 3)) trở nên khó
- Để chứng minh tính dừng của một máy Turing 3 trạng thái 3 ký hiệu, ta phải giải một bài toán kiểu Collatz
- Vì vậy, việc giải bài toán (BB(3, 3)) có thể khó ngang với việc giải chính bài toán kiểu Collatz đó
- Paul Erdős từng nói về các bài toán kiểu Collatz rằng: “Mathematics may not be ready for such problems”
- Bài viết trước Mother of Giants đã bàn về một họ máy Turing được phát hiện trong quá trình tìm kiếm Busy Beaver “Beeping”
- Với họ đó, để chứng minh có rơi vào trạng thái gần-dừng (quasihalt) hay không, cần mô phỏng hiệu quả hoặc giải hoàn toàn một bài toán kiểu Collatz
- Bigfoot là một trường hợp được tìm thấy trong trò chơi Busy Beaver thông thường, không phải một biến thể
Các trường hợp Busy Beaver khó trước đây
- Nhiều máy Turing do con người tự xây dựng cung cấp các ví dụ mà để chứng minh một giá trị Busy Beaver nhất định, phải chứng minh một mệnh đề toán học khó khác
- (BB(745)): cần chứng minh tính nhất quán của ZFC
- (BB(27)): cần chứng minh Goldbach Conjecture
- (BB(15)) và (BB(5,4)): cần chứng minh giả thuyết của Erdős rằng với (n > 8), biểu diễn cơ số 3 của (2^n) có ít nhất một chữ số 2
- Tuy nhiên, các giá trị Busy Beaver này hiện đều nằm ngoài tầm tiếp cận
- Trong 60 năm qua, các giá trị mới chỉ được chứng minh là (BB(2), BB(3), BB(4), BB(2,3)), và đã biết (BB(6) > 10 \uparrow\uparrow 15)
- Trước khi phân tích Bigfoot, người ta từng cho rằng vẫn có thể chứng minh được (BB(3, 3))
Định nghĩa và nguồn gốc của Bigfoot
- Máy Turing này có tên là Bigfoot, và bảng chuyển của nó được định nghĩa bởi chuỗi sau
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- Đây là cỗ máy được đăng trên bbchallenge
- Bảng chuyển như sau
| Trạng thái | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot là một trong 160 holdout không chính thức còn lại của (BB(3,3)) được chia sẻ trên kênh Discord của bbchallenge.org
- Máy Turing cụ thể này lần đầu được @savask chia sẻ trên cùng kênh Discord vào ngày 14 tháng 10 năm 2023, kèm mô tả hành vi ở mức thấp
- Các phân tích sau đó cho thấy cấu trúc kiểu Collatz và tính chất random walk lệch
Hoạt động quy về cấu hình (A(a,b,c))
- Xét cấu hình tổng quát như sau
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Khi Bigfoot đi vào cấu hình (A(a,b,c)) với (c \ge 1), các quy tắc dưới đây mô tả chính xác toàn bộ hành vi tiếp theo của nó cho đến khi dừng hoặc chạy mãi
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Các quy tắc này lặp một hàm kiểu Collatz theo các tham số (b) và (c)
- (a) vận động như một giá trị tích lũy
- Nếu (b \equiv 1 \pmod{6}) hoặc (b \equiv 4 \pmod{6}) thì (a) tăng
- Nếu (b \equiv 2 \pmod{6}) thì (a) giảm
- Bigfoot chỉ dừng khi (a) sắp giảm xuống dưới 0
Quỹ đạo quan sát được từ băng trắng
- Khi bắt đầu từ băng trắng, Bigfoot đạt cấu hình (A(2,1,2)) sau 69 bước
- Trong mô phỏng tiếp theo, (a) có vẻ tăng đều, và sau 24 triệu lần lặp thì (a = 3,999,888)
- Nếu giả sử dãy phần dư (b \bmod 6) là ngẫu nhiên đều, thì quá trình này tương đương với một random walk lệch trên trục số
- Xác suất đi sang phải ở mỗi bước là (\frac{2}{3})
- Xác suất đi sang trái là (\frac{1}{3})
- Trong lý thuyết Markov chain, có thể chứng minh rằng nếu vị trí hiện tại là (a=n), thì xác suất trong tương lai đạt tới (a=-1) là ((\frac{1}{2})^{n+1})
- Dãy (b \bmod 6) thực tế không ngẫu nhiên mà hoàn toàn tất định, và luôn tuân theo mẫu lẻ·lẻ·chẵn·chẵn
- Dù vậy, ở quy mô lớn nó vẫn cho thấy quỹ đạo tương tự một Markov chain ngẫu nhiên
- Sau 24 triệu bước, Markov chain được kỳ vọng sẽ đi sang phải 8 triệu lần và sang trái 4 triệu lần
- Điều này rất gần với giá trị thực tế của (a), khoảng 4 triệu
Heuristic “Probviously” rằng nó không dừng
- Khi (a \approx 4,000,000), xác suất để random Markov chain đạt tới (a=-1) xấp xỉ ((\frac{1}{2})^{4,000,000})
- Giá trị này nhỏ đến mức trong thực hành khoa học có thể xem như chắc chắn thất bại
- Nếu Bigfoot vận hành tương tự Markov chain đó, thì có vẻ nó sẽ không dừng
- Nhưng đây không phải là một mệnh đề toán học chặt chẽ, mà chỉ là heuristic thực nghiệm
- Ta vẫn không thể loại trừ khả năng Bigfoot dừng sau googolplex lần lặp
- John Conway đặt ra cách nói này để mô tả heuristic rằng giả thuyết Collatz có lẽ đúng theo kiểu “probviously”, nhưng cho đến nay vẫn chưa thấy được chứng minh
Hai kết cục có thể có của Bigfoot
- Bigfoot chỉ có thể rơi vào một trong hai trường hợp
- dừng
- chạy mãi mãi
- Nếu nó dừng, ta có thể chứng minh bằng cách tăng tốc đủ mức việc lặp hàm kiểu Collatz để mô phỏng đến tận cùng
- Nếu nó chạy mãi mãi, ta phải chứng minh rằng hàm kiểu Collatz này tuyệt đối không bao giờ chạm tới chuyển tiếp dừng tại (a=0)
- Theo heuristic của Markov chain, trường hợp thứ hai có vẻ hợp lý hơn và cũng khó chứng minh hơn nhiều
Tên gọi Cryptids
- Loại máy này có thể quy hành vi về những quy tắc toán học tương đối đơn giản, nhưng các quy tắc đó lại rơi vào một lớp bài toán toán học còn bỏ ngỏ
- Nó giống những sinh vật huyền thoại chỉ có lời đồn là tồn tại hay không tồn tại, nhưng không bên nào đưa ra được bằng chứng cụ thể
- Đã có đề xuất gọi các cỗ máy kiểu này là Cryptids
- Đây là phép so sánh với các sinh vật huyền thoại như Loch Ness Monster hay Chupacabra
- Máy Turing này được đặt tên Bigfoot vì nó trông như đang bước đi ngẫu nhiên
Hành vi kiểu Collatz này có thực sự khó không
- Động lực học của hàm kiểu Collatz cụ thể này có vẻ là một bài toán hầu như chưa từng được phân tích trước đây
- Vẫn còn khả năng có thể tìm ra một tính chất toán học khéo léo nào đó, dùng một chút lý thuyết số và tính toán, chỉ áp dụng cho riêng bài toán này
- Nếu tìm ra được tính chất như vậy, ta sẽ biết rằng chứng minh (BB(3,3)) vẫn còn trong tầm tiếp cận
- Về mặt thực nghiệm, các câu hỏi có thể đặt ra với các bài toán kiểu Collatz thường chia làm hai loại
- những câu hỏi chứng minh được khá dễ dàng
- những câu hỏi mà chưa có nhà toán học nào biết cách chứng minh
- Trong Bigfoot, việc (b) lặp lại mẫu lẻ·lẻ·chẵn·chẵn, hay việc sau khi áp dụng quy tắc Collatz cổ điển (3n+1) thì kết quả luôn chẵn và ở bước sau sẽ chia được cho 2, thuộc loại thứ nhất
- Gần như mọi câu hỏi khác về hành vi của các hệ Collatz đều có thể xem là thuộc loại thứ hai
Biểu diễn thay thế với 81 trường hợp
- Một biểu diễn thay thế được bổ sung vào ngày 18 tháng 10 năm 2023 giúp giảm bớt sự bất tiện của mô tả (A(a,b,c)) ban đầu
- Mô tả cũ có ba điểm bất tiện
- các tham số (b) và (c) bị ràng buộc với nhau
- modulo 6 ở đầu vào và modulo 8 ở đầu ra có ước chung là 2
- (b) tuân theo mẫu lặp lẻ·lẻ·chẵn·chẵn
- Matthew House chỉ ra rằng có thể tránh các vấn đề này nếu định nghĩa cấu hình mới như sau
[ B(a,b)=A(a,2b+1,2) ]
- Nếu đặt (b=81k+r) và gộp 4 phép chuyển gốc thành một phép chuyển duy nhất, ta có thể biểu diễn hành vi kiểu Collatz của Bigfoot bằng các quy tắc gồm 81 trường hợp
- Biểu diễn này xử lý được ba đặc điểm của cách biểu diễn (A) cũ và trông giống bài toán Collatz cổ điển hơn
- Tuy vậy, nó hơi khó thao tác vì phải xử lý đủ cả 81 trường hợp
- Một số quy tắc phụ thuộc vào điều kiện (a \ge 2)
1 bình luận
Các ý kiến trên Hacker News
Có lẽ nói rằng bản thân BB(3, 3) khó thì không chính xác bằng việc nó đang mã hóa một bài toán kiểu Collatz, và các bài toán kiểu đó nhìn chung được xem là rất khó
Tuy nhiên, việc instance cụ thể này có thật sự khó hay không lại là chuyện khác. Hành vi của nó trông khá lệch về một phía, và khác với bài toán Collatz cổ điển, ta không cần xem quỹ đạo của mọi số nguyên mà chỉ cần xem một quỹ đạo duy nhất
Tôi cũng đồng ý ở một mức nào đó về điểm một quỹ đạo so với nhiều quỹ đạo. Tuy vậy, nếu giả sử ta đang ở thế giới nơi máy Turing này không dừng, thì việc chứng minh quỹ đạo duy nhất của hệ này có thể được xem là “khó hơn” một quỹ đạo duy nhất của giả thuyết Collatz cổ điển. Nếu giả thuyết Collatz là đúng, thì chứng minh cho một quỹ đạo đơn lẻ bất kỳ rốt cuộc chỉ cần một phép tính hữu hạn; còn quỹ đạo đơn lẻ trong bài viết thì phải chứng minh rằng nó không bao giờ dừng, nên cần toán học tinh tế hơn
Tôi không muốn phóng đại. Điều này không có nghĩa là để giải BB(3, 3) thì nhất thiết phải chứng minh giả thuyết Collatz hay một bài toán mở đã được nghiên cứu kỹ trong toán học. Dù vậy, tôi nghĩ nó vẫn có ý nghĩa như một kết quả “tốt hạng nhì”: một bài toán khó giống với một bài toán đã được nghiên cứu kỹ. Bài toán tương tự Collatz này khó đến đâu thì có lẽ cứ xem ai có thể giải được là biết
Tôi muốn giúp làm rõ chỗ này. Có một máy Turing 748 trạng thái [0], và tôi hiểu rằng máy này chỉ dừng khi ZFC mâu thuẫn
Máy này là một đối tượng “vật lý” có thể được triển khai và chạy trên máy tính. Năng lực tính toán hiện nay không đủ, nhưng về nguyên lý thì không có gì ngăn ta chạy máy này trong BB(748) bước. Nếu nó dừng, theo Định lý 1, ta đã chứng minh ZFC mâu thuẫn; còn nếu nó không dừng, có vẻ như ta đã chứng minh ZFC nhất quán
Đây là điểm gây bối rối cốt lõi. Nó trông không giống một kết quả trừu tượng, mà giống một phép tính có thể thực sự thực hiện và thu được giá trị
Tất nhiên, theo định lý bất toàn thứ hai của Gödel, trong ZFC không thể chứng minh tính nhất quán của ZFC. Nhưng nếu máy Turing nói trên dừng, thì dường như ta đã chứng minh ZFC nhất quán, trông như một mâu thuẫn
Sai ở đâu? Phỏng đoán hiện tại của tôi là trong chứng minh Định lý 1, để chỉ ra rằng máy Turing 748 trạng thái chỉ dừng khi ZFC mâu thuẫn, người ta đã dùng một siêu lý thuyết mạnh hơn ZFC. Nếu vậy thì không có mâu thuẫn. Dù có thể chạy nó trong BB(748) bước, điều đó chỉ cho thấy ZFC+ chứng minh được tính nhất quán của ZFC, vốn là điều đã biết. Chẳng hạn ZFC + “tồn tại một lực lượng không thể đạt tới” có thể đóng vai trò như vậy
Tôi chưa xem kỹ bài báo nên không biết thực tế có đúng vậy không. Ai đã suy nghĩ sâu về vấn đề này có thể chia sẻ góc nhìn không?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Nếu vị thần busy beaver cho ta biết giá trị đó, thì về lý thuyết ta có thể chạy máy Turing ngần ấy bước và, như bạn nói, chứng minh được ZFC có nhất quán hay không. Nhưng để con người tính BB(748), trên thực tế ta phải biết liệu riêng máy Turing 748 trạng thái này có bao giờ dừng hay không, và cả việc tất cả các máy Turing 748 trạng thái khác có dừng hay không
Dù dùng toàn bộ vật chất và năng lượng của vũ trụ để xây máy tính, và máy tính đó chỉ làm mỗi việc này với hiệu suất cao nhất mà vật lý cho phép, nó vẫn không thể hoàn tất phép tính
Vì vậy có một điểm mà toán học tách khỏi vật lý và hiện thực. Ta có thể nói và suy luận về những đối tượng như vậy, nhưng chúng không còn mang ý nghĩa vật lý nữa
Nhưng chứng minh nó không dừng thì khó hơn nhiều. Dù chạy đến TREE(3) bước, đó vẫn không phải là chứng minh rằng nó sẽ không dừng ở bước TREE(3)+1
Vì vậy, đáng buồn là không thể nói “cứ chạy là được”
Tôi thích văn phong của tác giả. Nó giúp hiểu chủ đề mà không có vẻ dài dòng, và đạt được điểm cân bằng đó không dễ
Tài liệu liên quan: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... và https://googology.fandom.com/wiki/Googology_Wiki
Nói BB không thể tính toán được có phải mang nghĩa như thế này không? Khi BB càng lớn thì nó chứa đựng toàn bộ toán học, và cuối cùng có nghĩa là phải chứng minh mọi thứ?
Phần còn lại của toàn bộ toán học được “đưa lậu” vào BB thông qua bài toán dừng. Vì ta có thể viết một chương trình chỉ dừng khi một phỏng đoán toán học tùy ý là đúng hoặc sai, nên để giải bài toán dừng hay BB thì phải biết toàn bộ toán học[0]. Điều này khả dĩ vì tính Turing-complete là ranh giới của khả năng tính toán. Thứ gì có thể chứa một máy tính thì bản thân nó cũng là một máy tính
[0] Thực ra bản thân điều này không phải là lý do khiến việc quyết định dừng trở nên bất khả quyết. Tính bất khả quyết đến từ việc một chương trình “kéo chính nó vào trong bài toán dừng”, theo kiểu một bộ phán định dừng giả định sẽ chỉ dừng khi nó nói rằng chính nó không dừng
Có những bài toán toán học mà chúng ta “biết” là không thể chứng minh cũng không thể bác bỏ. Định lý bất toàn thứ nhất của Gödel nói rằng điều đó đúng, trừ khi mọi mệnh đề đều có thể được chứng minh vừa đúng vừa sai. Nếu mọi mệnh đề đều có thể được chứng minh là cả đúng lẫn sai thì hệ thống chứng minh đó vô dụng, việc chứng minh chẳng còn ý nghĩa gì, nên ta phải chọn một hệ thống chứng minh khác không có chuyện như vậy. Vì thế thông thường ta giả định trường hợp thứ nhất, tức là có những bài toán không thể chứng minh cũng không thể bác bỏ. Nói thêm, định lý bất toàn thứ hai của Gödel nói rằng ta không bao giờ có thể chứng minh chính việc mình đang ở trong trường hợp thứ nhất
Và việc BB không tính được có nghĩa là khi BB lớn lên, đến một lúc nào đó nó có thể mã hóa một chương trình chỉ dừng khi một bài toán không thể chứng minh cũng không thể bác bỏ là đúng. Vì vậy ta không thể chứng minh chương trình đó dừng hay không dừng
Nói chặt chẽ, việc chứng minh hoặc bác bỏ một điều không thể chứng minh cũng không thể bác bỏ tương đương với chứng minh điều sai, và điều đó rốt cuộc có thể được dùng để “chứng minh” mọi mệnh đề, nên nói rằng nó “bao quát toàn bộ toán học” theo một nghĩa nào đó là đúng. Tuy nhiên đây là một điều kiện tới hạn, và nó phát huy tác dụng từ rất lâu trước khi xuất hiện một máy Turing đủ lớn để mã hóa “mọi” bài toán toán học. Trên thực tế không có số trạng thái hữu hạn nào đủ để mã hóa mọi bài toán toán học, vì ta luôn có thể làm chuỗi số học dài hơn nữa
Sau đó thì việc tồn tại những BB mà ta không giải được không còn đáng ngạc nhiên nữa; điều thú vị trở thành việc khảo sát BB nào giải được và BB nào không
Tôi không hiểu vì sao đoạn “Do đó, giải bài toán BB(3, 3) khó ít nhất ngang với việc giải bài toán giống Collatz này” lại đáng ngạc nhiên. Thực ra nó trông gần như hiển nhiên. Chẳng phải mọi bài toán BB(x, y) đều quy về bài toán kiểu Collatz sao?
BB(x, y) có thể dễ dàng chuyển thành bài toán dừng. Tìm trong tất cả các máy có x trạng thái và y ký hiệu những máy nào dừng, rồi để riêng những máy không dừng. Sau đó chạy tất cả các máy dừng song song từng bước một cho đến khi tất cả đều dừng; số bước đã chạy chính là giá trị BB(x, y)
Theo tôi biết Conway đã đưa ra cách quy bài toán dừng về bài toán kiểu Collatz. Nếu vậy, có vẻ ta có thể giảm BB(x, y) với x, y bất kỳ thành một bài toán kiểu Collatz bằng phép quy hai bước: từ BB sang bài toán dừng, rồi từ đó sang bài toán Collatz
Điều cần là phép quy từ Collatz sang bài toán dừng, rồi tiếp sang B(x,y). Từ Collatz sang bài toán dừng là hiển nhiên, nhưng từ bài toán dừng sang B(x,y) thì kém hiển nhiên hơn. Cần định nghĩa chính xác tập con nào của bài toán dừng vừa có thể được quy từ Collatz, vừa không khó hơn B(3,3)
Bài toán dừng dường như thường “chặn” nhiều cách tiếp cận trong lý thuyết thông tin thuật toán và quy nạp dựa trên các chương trình tính được. Nhưng tôi tò mò liệu có nghiên cứu nào về việc bài toán dừng có tác động vật chất đến năng lực quy nạp trong thế giới thực hay không
Ví dụ, giả sử có một oracle cho biết liệu một máy Turing phổ quát đơn điệu tùy ý, trong lúc chạy, đã đạt đến điểm mà nó sẽ không ghi thêm gì lên băng đầu ra nữa hay chưa. Kết quả quy nạp dùng oracle này có khác biệt lớn so với cách duyệt vét cạn không gian chương trình, rồi nếu một chương trình không tạo đầu ra trong n bước đủ lớn thì cứ “bỏ qua” sang chương trình tiếp theo không?
Ý tôi là quy nạp trên dữ liệu nén được “bình thường”, chứ không phải các trường hợp biên được cố ý tạo ra như BB(3,3) hay ví dụ đối kháng
Là một nhà nghiên cứu bảo mật, tôi trực tiếp viết fuzzer. Fuzzer là công cụ tự động tìm các đầu vào có ý nghĩa về mặt bảo mật cho chương trình được kiểm thử. Nó tạo và biến đổi đầu vào bằng thuật toán, đưa vào chương trình, rồi quan sát điều gì xảy ra hàng chục, hàng trăm, hàng nghìn lần mỗi giây
Nếu một đầu vào làm chương trình crash, có thể xem như nó đã khiến chương trình “dừng”. Có lẽ để tạo một fuzzer tìm được mọi lỗi trong thời gian thực tế cho bất kỳ chương trình nào, ta sẽ phải giải bài toán dừng. Thực tế là dù đã kiểm thử hàng tỷ lần, vẫn có người tìm ra lỗi trong trình giải mã ảnh, nên đúng là các fuzzer của chúng ta không hoàn hảo
Đồng thời, trong thực tế tôi cũng thấy rằng nếu được cho đủ thời gian, fuzzer thâm nhập sâu vào bên trong các chương trình phức tạp hơn dự đoán. Việc kiểm tra hợp lệ đầu vào do đối tượng kiểm thử thực hiện, cùng bộ nhớ và lưu trữ hữu hạn của PC hiện đại, phần nào đặt fuzzer lên đúng quỹ đạo. Ngoại lệ là khi có mật mã học tham gia; với fuzzer, nó giống như một vũng hắc ín tính toán. Những chương trình được phòng vệ tốt và đặc tả rõ ràng đóng vai trò như các lan can tự thân, để fuzzer không cần giải bài toán dừng
Vì vậy, về việc phát hiện lỗi bảo mật trong chương trình, tôi nhìn nhận thế này: trừ mật mã học, fuzzer mạnh khi nhắm vào các chương trình có kiểm tra đầu vào nghiêm ngặt. Ngược lại, với những chương trình không kiểm tra đầu vào nghiêm ngặt thì không nhất thiết cần fuzzer, và ở đó fuzzer cũng không nhất thiết hoạt động tốt
Có trực giác nào về việc vì sao BBB, tức Busy Beaver phát tiếng bíp, có thể chạy lâu hơn rất nhiều trước khi gần như dừng không?
Một điều thấy được là về cơ bản không cần dùng trạng thái dừng. Theo nghĩa đó, BBB 3 trạng thái có thể giống BB 4 trạng thái. Tôi tò mò không biết còn gì khác không
Vì vậy có thể làm cho một chương trình hoặc máy Turing kích thước X mô phỏng việc chạy mọi chương trình kích thước Y, với Y >> X. Nếu mỗi lần một trong các chương trình đó dừng thì phát tiếng bíp, tiếng bíp cuối cùng sẽ xảy ra khi mô phỏng việc chương trình BB(Y) dừng sau nhiều bước hơn BB(Y). Do đó BBB(X) > BB(Y) >> BB(X)
Nếu tôi nhớ đúng, về cơ bản do cùng một cách xây dựng, nếu biết BB(N) thì có thể tính rất chậm bài toán dừng của các chương trình có kích thước không quá N, còn nếu biết BBB(N) thì có thể tính còn chậm hơn nhiều bài toán dừng đối với các máy Turing được cấp oracle dừng có kích thước không quá đó
Nội dung này quá nerd đối với tôi
Tôi tò mò muốn hiểu những thứ này thì cần kiến thức nền gì. Chỉ biết giải tích cơ bản có đủ không? Chủ đề hay môn học cụ thể nào sẽ là nền tảng tốt?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Theo một giáo trình nhập môn khoa học máy tính lý thuyết sẽ giúp hiểu được phần lớn. Sinh viên ngành khoa học máy tính thường học vào năm 1–2, và nó không dễ. Ở trường tôi, đây từng là một trong những kỳ thi đáng sợ nhất
Sách nhập môn của Hopcroft & Ullmann khá tốt. Tuy vậy, nội dung liên quan rất rộng nên có thể xem đó là điểm xuất phát
Nhiều chương trình cử nhân khoa học máy tính hẳn có các khóa học với tài liệu công khai
Nên đọc
1RB2RA1LC_2LC1RB2RB_---2LA1LAnhư thế nào?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Ví dụ, nếu đang ở trạng thái B và giá trị băng tại vị trí đầu đọc hiện tại là 0, thì ghi 2, di chuyển đầu đọc sang trái một ô, rồi chuyển sang trạng thái C
3 ký tự đó lần lượt nghĩa là ký hiệu sẽ ghi, trạng thái mới, và hướng di chuyển. Trạng thái
---là dừng(trạng thái, giá trị băng)hiện tại được ánh xạ thành bộ ba(giá trị băng mới, hướng di chuyển của đầu đọc băng, trạng thái mới)[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA