計算機程序揭示了數學基本極限

宜斌

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

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

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

忙碌的海貍

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

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

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

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

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

圖靈機的簡單示意圖

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

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

不可知的閾值

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

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

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

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