Nhưng khó hơn bao nhiêu? Năm 1962, nhà toán học Tibor Radó đã phát minh ra một cách mới để khám phá câu hỏi này thông qua những gì ông gọi là trò chơi hải ly bận rộn. Để chơi, hãy bắt đầu bằng cách chọn một số lượng quy tắc cụ thể, gọi số đó N. Mục tiêu của bạn là tìm N-Rule Turing Machine chạy lâu nhất trước khi dừng lại. Máy này được gọi là hải ly bận rộn và số hải ly bận rộn tương ứng, BB (N), là số bước mà nó thực hiện.
Về nguyên tắc, nếu bạn muốn tìm thấy hải ly bận rộn cho bất kỳ Nbạn chỉ cần làm một vài điều. Đầu tiên, hãy liệt kê tất cả những điều có thể N-RULE MÁY TURING. Tiếp theo, sử dụng một chương trình máy tính để mô phỏng việc chạy mỗi máy. Tìm kiếm các dấu hiệu nhận biết rằng các máy sẽ không bao giờ dừng lại, ví dụ, nhiều máy sẽ rơi vào các vòng lặp lại vô hạn. Loại bỏ tất cả các máy không phải là nửa này. Cuối cùng, ghi lại số bước mà mỗi máy khác đã thực hiện trước khi tạm dừng. Người có thời gian chạy dài nhất là hải ly bận rộn của bạn.
Trong thực tế, điều này trở nên khó khăn. Đối với người mới bắt đầu, số lượng máy có thể phát triển nhanh chóng với mỗi quy tắc mới. Phân tích tất cả chúng riêng lẻ sẽ là vô vọng, vì vậy bạn sẽ cần viết một chương trình máy tính tùy chỉnh để phân loại và loại bỏ các máy. Một số máy rất dễ phân loại: chúng dừng nhanh hoặc rơi vào các vòng vô hạn dễ nhận dạng. Nhưng những người khác chạy trong một thời gian dài mà không hiển thị bất kỳ mẫu rõ ràng nào. Đối với những cỗ máy này, vấn đề tạm dừng xứng đáng với danh tiếng đáng sợ của nó.
Bạn càng thêm các quy tắc, bạn càng cần nhiều sức mạnh tính toán. Nhưng vũ phu là không đủ. Một số máy chạy quá lâu trước khi tạm dừng việc mô phỏng chúng từng bước là không thể. Bạn cần các thủ thuật toán học thông minh để đo lường thời gian chạy của họ.
Cải tiến công nghệ chắc chắn giúp ích, Shawn Ligocki, một kỹ sư phần mềm và Hunter Beaver Hunter lâu năm cho biết. Nhưng họ chỉ giúp đỡ cho đến nay.
Kết thúc một kỷ nguyên
Những thợ săn hải ly bận rộn bắt đầu sứt mẻ trong vấn đề BB (6) một cách nghiêm túc trong những năm 1990 và 2000, trong một cuộc săn lùng trong cuộc săn lùng BB (5). Trong số đó có Shawn Ligocki và cha anh, Terry, một nhà toán học ứng dụng, người đã điều hành chương trình tìm kiếm của họ trong giờ nghỉ trên các máy tính mạnh mẽ tại Phòng thí nghiệm quốc gia Lawrence Berkeley. Vào năm 2007, họ đã tìm thấy một cỗ máy Turing sáu quy tắc đã phá vỡ kỷ lục về thời gian chạy dài nhất: số bước đã thực hiện trước khi tạm dừng có gần 3.000 chữ số. Đó là một con số khổng lồ bởi bất kỳ biện pháp thông thường. Nhưng nó không quá lớn để viết ra. Trong phông chữ 12 điểm, 3.000 chữ số đó sẽ chỉ bao gồm một tờ giấy.
Ba năm sau, một sinh viên khoa học máy tính đại học người Slovakia tên Pavel Kropitz đã quyết định giải quyết cuộc săn lùng BB (6) như một dự án luận án cao cấp. Ông đã viết chương trình tìm kiếm của riêng mình và thiết lập nó để chạy trong nền trên mạng gồm 30 máy tính trong phòng thí nghiệm đại học. Sau một tháng, anh ta đã tìm thấy một cỗ máy chạy lâu hơn nhiều so với máy được phát hiện bởi Ligockis, một nhà vô địch mới của người Viking, trong trò chơi biệt ngữ của những thợ săn hải ly bận rộn.
Tôi đã may mắn, bởi vì những người trong phòng thí nghiệm đã phàn nàn về việc sử dụng CPU của tôi và tôi đã phải thu nhỏ lại một chút, ông Kropitz đã viết trong một cuộc trao đổi tin nhắn trực tiếp trên máy chủ Discer Discer Busy Challenge. Sau một tháng nữa để tìm kiếm, anh ta đã phá vỡ kỷ lục của chính mình bằng một chiếc máy có thời gian chạy có hơn 30.000 chữ số, đủ để điền vào khoảng 10 trang.