宜斌

忙碌的海貍（Busy Beaver）游戲的目標是找到運行時間最長的計算機程序，它與數(shù)學有著令人驚訝的聯(lián)系。該游戲是由匈牙利的數(shù)學家Tibor Radó在1962年發(fā)表的論文《On Non-Computable Functions》中提出的。

在計算機科學中，忙碌的海貍是一個在給定參數(shù)后，尋找可能產(chǎn)生的最大輸出的可終止程序。忙碌的海貍游戲包括設計一個可終止的，只輸出0或1的圖靈機，讓其在一條紙帶上盡可能多地輸出1。

然而對于程序員和其他數(shù)學愛好者來說，找到這些程序一直是一個巨大的難題。在過去的幾年中，繁忙的海貍游戲之所以成為一個研究對象，是因為它與某些高階的概念和數(shù)學中的開放性問題產(chǎn)生了聯(lián)系。

忙碌的海貍

程序員通常想要以最小化其代碼執(zhí)行所需的時間。但是在1962年，匈牙利數(shù)學家TiborRadó提出了相反的問題。他問：一個簡單的計算機程序在終止之前可能會運行多長時間？Radó將這些效率極低但仍能正常運行的程序稱為“忙碌的海貍”。

德克薩斯大學奧斯汀分校的理論計算機科學家Scott Aaronson說：“在數(shù)學上，有趣的娛樂與實際上重要的事物之間存在非常容易結(jié)合之處。”

最近的數(shù)據(jù)表明，運行時間長的計算機程序的搜索可以闡明數(shù)學知識的狀態(tài)，甚至可以告訴我們什么是已知的。根據(jù)研究人員的說法，忙碌的海貍游戲為評估某些問題（例如未解決的哥德巴赫猜想和黎曼假設）的難度提供了具體的基準，它甚至可以讓研究者一目了然地了解數(shù)學背后的邏輯基礎。

什么是圖靈機？圖靈機是一個虛擬的機器，盡管這個機器很簡單，但它可以模擬計算機的任何算法，無論這個算法有多復雜。

忙碌的海貍游戲全都涉及圖靈機的行為——圖靈機是1936年由艾倫·圖靈（Alan Turing）構(gòu)思的原始的理想化計算機，圖靈機對被分成正方形的環(huán)形膠帶執(zhí)行動作，根據(jù)規(guī)則列表進行操作。

圖靈機的簡單示意圖

假設有一個無窮的紙帶，紙帶就像一個存儲器一樣。紙帶上面的每個格子是空白的，但是可以讀寫數(shù)據(jù)，在這個例子里，機器只能寫0或1，或者什么也不寫，這個機器就是包含3個信號的圖靈機。

這個機器有一個探頭，這個頭可以移動到每一個空格上，用這個頭，機器可以有3個基本操作——1.讀空格的數(shù)據(jù);2.編輯數(shù)據(jù)，可以是寫一個新的數(shù)據(jù)，可以是擦除數(shù)據(jù);3.移動紙帶向左或者向右，這樣機器可以讀或者編輯旁邊的格子。

不可知的閾值

正如圖靈1936年指出的那樣，為了進行計算，圖靈機最終必須停止運行，它不能陷入無限循環(huán)中。但他還證明，目前沒有可靠的、可重復的方法來區(qū)分停止運行的機器和永久運行的機器，就是所謂的停止問題。

忙碌的海貍游戲會問：給定一定數(shù)量的規(guī)則，圖靈機停止之前可以執(zhí)行的最大步數(shù)是多少？如果只允許一個規(guī)則，并且要確保圖靈機停止，則必須立即添加停止指令。

目前還沒有通用的方法來確定運行時間最長的圖靈機，拋開一大堆的數(shù)學公式計算，馬里蘭大學學院分校的計算機科學家William Gasarch表示，他對固定忙碌的海貍數(shù)量的前景不感興趣，而對“實際上卻無話可說的一般概念”感興趣。他和其他數(shù)學家主要對使用游戲作為衡量標準來衡量數(shù)學中重要的未解決問題的難度，或找出所有數(shù)學上可以理解的東西感興趣。

還有網(wǎng)友問到量子計算機對運行這種忙碌的海貍圖靈機有加速作用嗎？結(jié)論是沒有。因為圖靈機運行過程是順序性的，前面的沒運行過，后面的就運行不了，所以量子計算機的并行運算對它使不上勁。