Khi nhắc đến cụm từ “busy beaver”, nhiều người sẽ nghĩ ngay đến một người lao động chăm chỉ không biết mệt mỏi, hoặc đối với các nhà sinh học, nó gợi nhớ đến một kỹ sư hệ sinh thái vô cùng quan trọng. Tuy nhiên, đối với các nhà toán học, “busy beaver” lại mang một ý nghĩa đặc trưng và độc đáo. Theo như mô tả của chuyên gia máy tính Christopher Moore trong một video cho Quanta Magazine, ý tưởng này biểu thị cho một khối lượng công việc lớn, nhưng công việc đó lại hướng tới một câu hỏi cụ thể: “Điều gì là chức năng phức tạp và dài nhất mà một máy tính có thể thực hiện, rồi dừng lại?” Hay nói cách khác, đó là chức năng dài nhất mà một máy tính có thể chạy mà không bị mắc kẹt trong vòng lặp vô hạn.
Giải pháp cho câu hỏi này được gọi là số Busy Beaver, hay BB
, với n đại diện cho số lượng chỉ dẫn, được gọi là ‘trạng thái’, mà một tập hợp máy tính—cụ thể là một loại máy tính đơn giản mang tên máy Turing—phải tuân theo. Mỗi trạng thái tạo ra một số chương trình nhất định, và mỗi chương trình sẽ có một máy Turing riêng, vì vậy mọi thứ trở nên phức tạp nhanh chóng. BB(1), với chỉ 1 trạng thái, yêu cầu sử dụng 25 máy Turing. Trong suốt nhiều thập kỷ, các nhà toán học tin rằng bài toán số Busy Beaver với bốn trạng thái là giới hạn tối đa đã biết. Thế nhưng, một nhóm chuyên gia đã xác nhận được giải pháp cho BB(5) vào năm 2024 (trên Discord, thật bất ngờ). Hiện tại, những người tham gia thử thách Busy Beaver đang khám phá những sự thật thú vị về ranh giới tiếp theo—BB(6)—và làm thế nào nó có thể đại diện cho giới hạn của toán học, theo báo cáo mới từ New Scientist.
Để giải thích một cách ngắn gọn, BB(1)—phiên bản đơn giản nhất của vấn đề BB—sử dụng chỉ một bộ quy tắc và chỉ cho ra hai kết quả: di chuyển vô hạn trên băng và dừng lại ở số đầu tiên. Bởi vì 1 là số bước tối đa mà bất kỳ 25 máy Turing nào của BB(1) sẽ hoàn thành trước khi hoàn tất chương trình (được gọi là halting), câu trả lời cho BB(1) là 1. Khi số lượng trạng thái gia tăng, số bước và số máy Turing cần thiết để chạy các chương trình cũng gia tăng, có nghĩa là mỗi BB tiếp theo lại trở nên khó giải quyết hơn theo cấp số nhân. BB(2) và BB(3) có giá trị lần lượt là 6 và 21, nhưng BB(4) lại là 107 và yêu cầu tới bảy tỷ máy Turing khác nhau để giải quyết. Dĩ nhiên, nhiều máy trong số này sẽ tiếp tục chạy mãi mãi và có thể bị loại bỏ, nhưng vẫn còn nhiều máy khác không như vậy.
Số Busy Beaver được nhà toán học Hungary Tiber Radó đặt ra lần đầu tiên vào năm 1962, và đã mất 12 năm trước khi nhà khoa học máy tính Allen Brady xác định rằng BB(4) chạy trong 107 bước trước khi dừng lại. Trong nhiều thập kỷ, điều này dường như là giới hạn tuyệt đối của những gì có thể nhận biết được, nhưng sau đó, vào năm 2024, các nhà toán học đã giải được BB(5) sau khi sàng lọc qua 17 triệu tỷ (với chữ t) máy Turing khả thi. Câu trả lời thật đáng kinh ngạc: 47,176,870 bước. Quanta Magazine cũng đã có một bài phân tích tuyệt vời về cách mà điều này được thực hiện.
Nhưng việc giải quyết BB(5) đã đặt ra câu hỏi tiếp theo rất rõ ràng: Vậy BB(6) thì sao? Tất nhiên, việc chỉ thêm một quy tắc nữa làm cho bài toán trở nên khó khăn hơn một cách vượt bậc, vì BB(6) ước tính sẽ yêu cầu 60 triệu triệu máy Turing. “Vấn đề Busy Beaver cung cấp cho bạn một thang đo cụ thể để suy ngẫm về ranh giới của tri thức toán học,” nhà khoa học máy tính Tristan Stérin, người đã giúp khởi động Thử thách Busy Beaver vào năm 2022, chia sẻ với New Scientist.
Trong một bài đăng mới, người dùng ẩn danh “mxdys”—người đã đóng vai trò quan trọng trong việc xác nhận BB(5)—cho biết rằng câu trả lời cho BB(6) có thể lớn đến mức khó tin đến nỗi chính số đó cần có một giải thích riêng, vì nó có thể quá lớn để mô tả bằng phép lũy thừa. Thay vào đó, nó dựa vào tetration (được viết là, ví dụ, yx, thay vì lũy thừa xy), trong đó chỉ số cũng được lặp lại, tạo thành một tháp các chỉ số. Như Scott Aaronson, một nhà khoa học máy tính người Mỹ đã giúp xác định BB(5), đã lưu ý trên blog của mình, điều đó có nghĩa là 1510 có thể được hiểu là “10 lên 10 lên 10 và cứ như vậy 15 lần”.
Theo mxdys, BB(6) là ít nhất 2 được tetrated với 2 được tetrated với 2 được tetrated với 9. Một nhà toán học nói chuyện với New Scientist cho biết rằng số lượng nguyên tử trong vũ trụ có lẽ sẽ trông “mảnh mai” so với con số này. Mặc dù những con số khổng lồ này khiến chúng ta choáng ngợp, chúng cũng cho các nhà toán học thấy được những giới hạn của nền tảng toán học hiện đại—được gọi là lý thuyết tập hợp Zermelo–Fraenkel (ZFC)—cũng như những khái niệm toán học trơn tru như giả thuyết Collatz.
Khó có khả năng các nhà toán học sẽ giải quyết được BB(6), nhưng nếu Thử thách Busy Beaver là một minh chứng, điều này chắc chắn sẽ không ngăn cản họ cố gắng.
Nguồn tham khảo: https://www.popularmechanics.com/science/math/a65357535/busy-beaver-six/
Giải pháp cho câu hỏi này được gọi là số Busy Beaver, hay BB
, với n đại diện cho số lượng chỉ dẫn, được gọi là ‘trạng thái’, mà một tập hợp máy tính—cụ thể là một loại máy tính đơn giản mang tên máy Turing—phải tuân theo. Mỗi trạng thái tạo ra một số chương trình nhất định, và mỗi chương trình sẽ có một máy Turing riêng, vì vậy mọi thứ trở nên phức tạp nhanh chóng. BB(1), với chỉ 1 trạng thái, yêu cầu sử dụng 25 máy Turing. Trong suốt nhiều thập kỷ, các nhà toán học tin rằng bài toán số Busy Beaver với bốn trạng thái là giới hạn tối đa đã biết. Thế nhưng, một nhóm chuyên gia đã xác nhận được giải pháp cho BB(5) vào năm 2024 (trên Discord, thật bất ngờ). Hiện tại, những người tham gia thử thách Busy Beaver đang khám phá những sự thật thú vị về ranh giới tiếp theo—BB(6)—và làm thế nào nó có thể đại diện cho giới hạn của toán học, theo báo cáo mới từ New Scientist.
Để giải thích một cách ngắn gọn, BB(1)—phiên bản đơn giản nhất của vấn đề BB
—sử dụng chỉ một bộ quy tắc và chỉ cho ra hai kết quả: di chuyển vô hạn trên băng và dừng lại ở số đầu tiên. Bởi vì 1 là số bước tối đa mà bất kỳ 25 máy Turing nào của BB(1) sẽ hoàn thành trước khi hoàn tất chương trình (được gọi là halting), câu trả lời cho BB(1) là 1. Khi số lượng trạng thái gia tăng, số bước và số máy Turing cần thiết để chạy các chương trình cũng gia tăng, có nghĩa là mỗi BB tiếp theo lại trở nên khó giải quyết hơn theo cấp số nhân. BB(2) và BB(3) có giá trị lần lượt là 6 và 21, nhưng BB(4) lại là 107 và yêu cầu tới bảy tỷ máy Turing khác nhau để giải quyết. Dĩ nhiên, nhiều máy trong số này sẽ tiếp tục chạy mãi mãi và có thể bị loại bỏ, nhưng vẫn còn nhiều máy khác không như vậy.Số Busy Beaver được nhà toán học Hungary Tiber Radó đặt ra lần đầu tiên vào năm 1962, và đã mất 12 năm trước khi nhà khoa học máy tính Allen Brady xác định rằng BB(4) chạy trong 107 bước trước khi dừng lại. Trong nhiều thập kỷ, điều này dường như là giới hạn tuyệt đối của những gì có thể nhận biết được, nhưng sau đó, vào năm 2024, các nhà toán học đã giải được BB(5) sau khi sàng lọc qua 17 triệu tỷ (với chữ t) máy Turing khả thi. Câu trả lời thật đáng kinh ngạc: 47,176,870 bước. Quanta Magazine cũng đã có một bài phân tích tuyệt vời về cách mà điều này được thực hiện.
Nhưng việc giải quyết BB(5) đã đặt ra câu hỏi tiếp theo rất rõ ràng: Vậy BB(6) thì sao? Tất nhiên, việc chỉ thêm một quy tắc nữa làm cho bài toán trở nên khó khăn hơn một cách vượt bậc, vì BB(6) ước tính sẽ yêu cầu 60 triệu triệu máy Turing. “Vấn đề Busy Beaver cung cấp cho bạn một thang đo cụ thể để suy ngẫm về ranh giới của tri thức toán học,” nhà khoa học máy tính Tristan Stérin, người đã giúp khởi động Thử thách Busy Beaver vào năm 2022, chia sẻ với New Scientist.
Trong một bài đăng mới, người dùng ẩn danh “mxdys”—người đã đóng vai trò quan trọng trong việc xác nhận BB(5)—cho biết rằng câu trả lời cho BB(6) có thể lớn đến mức khó tin đến nỗi chính số đó cần có một giải thích riêng, vì nó có thể quá lớn để mô tả bằng phép lũy thừa. Thay vào đó, nó dựa vào tetration (được viết là, ví dụ, yx, thay vì lũy thừa xy), trong đó chỉ số cũng được lặp lại, tạo thành một tháp các chỉ số. Như Scott Aaronson, một nhà khoa học máy tính người Mỹ đã giúp xác định BB(5), đã lưu ý trên blog của mình, điều đó có nghĩa là 1510 có thể được hiểu là “10 lên 10 lên 10 và cứ như vậy 15 lần”.
Theo mxdys, BB(6) là ít nhất 2 được tetrated với 2 được tetrated với 2 được tetrated với 9. Một nhà toán học nói chuyện với New Scientist cho biết rằng số lượng nguyên tử trong vũ trụ có lẽ sẽ trông “mảnh mai” so với con số này. Mặc dù những con số khổng lồ này khiến chúng ta choáng ngợp, chúng cũng cho các nhà toán học thấy được những giới hạn của nền tảng toán học hiện đại—được gọi là lý thuyết tập hợp Zermelo–Fraenkel (ZFC)—cũng như những khái niệm toán học trơn tru như giả thuyết Collatz.
Khó có khả năng các nhà toán học sẽ giải quyết được BB(6), nhưng nếu Thử thách Busy Beaver là một minh chứng, điều này chắc chắn sẽ không ngăn cản họ cố gắng.
Nguồn tham khảo: https://www.popularmechanics.com/science/math/a65357535/busy-beaver-six/
