BB(3, 3) rất khó

• Bài viết bàn về một máy Turing 3 trạng thái, 3 ký hiệu mà không thể chứng minh việc nó có dừng hay không nếu chưa giải được một bài toán tương tự Collatz, và vì vậy cho rằng bài toán BB(3,3) khó ngang với việc giải bài toán kiểu Collatz đó.
• Tác giả nhắc đến một họ máy Turing (TM) mà để chứng minh trạng thái "quasihalt", cần có mô phỏng hiệu quả hoặc lời giải hoàn chỉnh cho một bài toán tương tự Collatz.
• Tác giả lấy ví dụ từ trò chơi Busy Beaver thông thường và phát hiện ra nhiều TM cho ra kết quả trong trò chơi Busy Beaver.
• Tác giả giới thiệu một TM tên là "Bigfoot", một trong 160 ứng viên kháng cự BB(3,3) phi chính thức còn lại.
• Hành vi của Bigfoot được mô tả là lặp lại một hàm tương tự Collatz trên b và c, trong khi a giữ vai trò tổng tích lũy.
• Tác giả dùng lý thuyết chuỗi Markov để mô tả hành vi của Bigfoot và kết luận rằng Bigfoot "probviously" sẽ không bao giờ dừng.
• Tác giả cho rằng chúng ta đang sống trong một trong hai thế giới: thế giới nơi Bigfoot dừng lại hoặc thế giới nơi nó chạy mãi mãi, và ông tin rằng chúng ta đang sống trong thế giới thứ hai.
• Tác giả đề xuất gọi những cỗ máy kiểu này là "Cryptids", như một phép so sánh với các sinh vật huyền thoại như quái vật hồ Loch Ness hay Chupacabra.
• Tác giả mời gọi các ý tưởng về cách tấn công bài toán này và bày tỏ hy vọng rằng vẫn có thể chứng minh được BB(3,3).
• Cuối cùng, tác giả nói rằng theo kinh nghiệm của mình, những câu hỏi có thể đặt ra về các bài toán tương tự Collatz thường chỉ thuộc hai loại: hoặc tương đối dễ chứng minh, hoặc ngay cả các nhà toán học cũng chưa biết cách chứng minh.

[GN⁺]

Ý kiến Hacker News

• Thảo luận về độ phức tạp của BB(3, 3), được biết đến như một dạng bài toán kiểu Collatz, nhưng có ý kiến cho rằng chưa chắc nó đã khó, vì chỉ cần xét hành vi có thiên lệch và một quỹ đạo duy nhất.
• Thảo luận về máy Turing 748 trạng thái, cỗ máy sẽ dừng nếu ZFC (lý thuyết tập hợp Zermelo-Fraenkel và tiên đề chọn) là không nhất quán. Bày tỏ sự bối rối về hàm ý của việc chạy cỗ máy này ở bước BB(748) và khả năng mâu thuẫn với định lý bất toàn thứ hai của Gödel.
• Khen ngợi văn phong của tác giả vì rõ ràng và súc tích, giúp độc giả hiểu chủ đề mà không bị dài dòng.
• Đặt câu hỏi về ý nghĩa của việc BB (Busy Beaver) là không thể tính được, và liệu khi BB tăng lên thì có phải mọi thứ đều cần được chứng minh hay không.
• Đề xuất rằng mọi bài toán BB(x, y) đều có thể được rút gọn về một bài toán giống Collatz, và do đó việc tìm BB(x, y) cho một số giá trị x và y cũng có thể được rút gọn về một bài toán kiểu Collatz.
• Hỏi vì sao Beeping Busy Beavers (BBB) có thể gần như dừng trước khi chạy lâu hơn rất nhiều, với giả thuyết rằng có thể là vì không cần dùng trạng thái dừng.
• Đặt nghi vấn về ảnh hưởng của bài toán dừng đối với suy luận quy nạp trong thế giới thực, với một kịch bản giả định có oracle có thể quyết định liệu một máy Turing cho trước có in ra thứ gì đó khác trên băng đầu ra hay không.
• Hỏi về kiến thức nền cần thiết để hiểu các chủ đề này, và yêu cầu gợi ý những chủ đề hoặc môn học cụ thể có thể cung cấp nền tảng tốt.
• Hỏi cách đọc chuỗi cụ thể 1RB2RA1LC_2LC1RB2RB_---2LA1LA.