尋找最長的計算機程序的搜索

但是有多困難呢？ 1962年，數學家TiborRadó發明了一種新的方式來探索這個問題 繁忙的海狸遊戲。要玩，請從選擇特定數量的規則開始 – 命名此數字 n。您的目標是找到 n– 圖裡的機器運行最長的時間最終停止。這台機器稱為繁忙的海狸，以及相應的繁忙海狸號，BB（n），是它採取的步驟數。

首先，如果您想為任何給定的繁忙的海狸找到繁忙的海狸 n您只需要做一些事情即可。首先，記錄所有優勢 n– 機械師。然後使用計算機程序模擬每個計算機的執行。尋找機器永遠不會停止的指示性跡象 – 例如，許多機器都會落入經驗不足的重複循環中。丟棄所有這些非hALF機器。最後，在停止之前，記錄彼此彼此需要多少個步驟。運行時間最長的一個是您忙碌的海狸。

實際上，這變得困難。對於初學者來說，隨著每個新規則，可能的機器數量正在迅速增加。對所有個人的分析將是沒有希望的，因此您需要編寫一個自定義的計算機程序來分類和丟棄機器。有些機器易於排序：要么快速停止或陷入易於識別的經驗不足的環路。但是其他人已經跑了很長時間，沒有顯示任何明顯的模式。對於這些機器而言，不高興的問題值得它的聲譽。

您添加的規則越多，您需要的越多。但是暴力力量還不夠。一些機器正在運行很長時間，然後停止逐步模擬的內容是不可能的。您需要智能數學技巧來衡量他們的時代。

他說：“技術改進肯定會有所幫助。” 肖恩·利戈基（Shawn Ligocki）軟件工程師和長期存在的海狸獵人。 “但是他們只有到目前為止的幫助。”

時代的末端

在1990年代和2000年代，在BB Hunt的僵局（5）期間，公共汽車獵人開始認真擺脫BB（6）問題。其中包括肖恩·利戈基（Shawn Ligocki）和他的父親特里（Terry），他是一位應用數學家，他們在勞倫斯·伯克利國家實驗室（Lawrence Berkeley National Laboratory）的歐洲銷售計劃中運行了搜索計劃。在2007年，他們發現了一台圖靈機，在運行時間最長的時間裡打破了記錄：中斷之前所需的步驟數近3,000位。這是一個具有任何普通措施的巨大數字。但這並不太大。在12點字體中，這3,000位數字只能覆蓋一張紙。

三年後，一名名叫Pavel Kropitz的斯洛伐克大學本科生決定將BB（6）視為一個更高的論文項目。他編寫了自己的搜索時間表，並將其設置為在大學實驗室中的30個計算機網絡上運行。一個月後，他發現了一台機器的運行要比Ligockis發現的速度要多得多，這是繁忙的海狸獵人Lingo中的新“冠軍”。

“我很幸運。因為實驗室中的人們已經抱怨使用我的CPU，我們必須減少一點。” 繁忙的海狸挑戰服務器。又一個月的搜索後，他用一台機器打破了自己的記錄，該機器的執行時間超過30,000位數字 – 足以填寫約10頁。