聞樂 發自 凹非寺
量子位 | 公眾號 QbitAI

衡量圖靈機最大運行步數的海貍數（busy beaver number）紀錄，被刷新了！

一位神秘人突破了第六個海貍數的新下限，而且數值大到超乎想象——

假如將宇宙里的每個原子都刻上數字，也無法完全容納它。

也就是說，用咱平時熟悉的十進制根本沒辦法完全表示，得用超復雜的五冪運算來描述：指數套指數再套指數

△圖源：QuantaMagazine

這到底是個什么樣的神秘數字呢？

研究圖靈機極限能力的數字

海貍數，專業點說叫忙碌海貍數BB(n)。它背后藏著圖靈在1936年就證明的停機問題：

你永遠沒法用通用程序判斷一臺圖靈機到底是運行有限步驟后就停機，還是會一直無限運行下去。

所以找這個數，本質是在觸碰計算機能解決問題的邊界

圖靈機的計算方式是在無限長的磁帶上讀取和寫入0和1，磁帶劃分為很多個單元格，一個讀寫頭一次可以操作一個單元格。

每臺圖靈機都有自己的規則，規則規定讀寫頭在進入新的單元格時，遇到0或1分別該進行什么操作。

除此之外還有一個特殊的規則告訴圖靈機要停止運行。

于是圖靈機在運行過程中會出現運行有限次就停機或者無限循環運行兩種狀態。

1962年，數學家Tibor Radó發明了忙碌海貍游戲，通過尋找特定規則數的圖靈機在停機前運行最長時間來定義忙碌海貍數BB(n)。

例如，若選擇規則數n=5，目標就是找到有5條規則的圖靈機中運行時間最長才停機的那個，它在停機前執行的步數，就是BB(5)。

這就好比一群運動員在跑步，看誰堅持的時間最長，這個最長時間就是海貍數。

從20世紀70年代起，數學家們就踏上了尋找海貍數的漫漫長路。

對于BB(1)，情況相對簡單，因為單一規則的圖靈機實際上只有兩種可能性，要么第一步就停機，要么一直運行下去，所以很容易就確定了BB(1)=1

到了BB(2)，難度稍有提升。此時，需要考慮超過6000個不同的圖靈機。但一個相對簡單的程序足以證明BB(2)=6

而確定 BB(3) 時，挑戰大幅增加。因為三規則的圖靈機數量膨脹到數百萬。1965年，研究人員經過大量的研究和推算，在16777216個圖靈機中，找出了最多可以執行21個計算步驟的圖靈機，即BB(3)=21

1974年，數學家Allen Brady證明了BB(4)=107

確定前四個海貍數就耗費了幾十年時間，而BB(5)更是直到去年，才被一個業余的數學家團隊成功攻克，確定BB(5)=47176870

△圖源：QuantaMagazine

團隊關鍵貢獻來自一個化名為mxdys的神秘人

這次BB(6)的新紀錄也出自他手。

BB(6)的突破

20世紀90年代，研究者開始認真探索BB(6) 。

利戈茨基和他的父親特里在2007年找到了打破運行時間記錄的六規則圖靈機，其停機步數近3000位。

2010年，克羅皮茨找到運行時間更長的機器，步數超30000位。克羅皮茨的BB(6)紀錄保持了12年。

2022年，利戈茨基借助新硬件打破記錄，引發了與克羅皮茨的競爭，利戈茨基兩次宣布新紀錄，克羅皮茨都能在三天內刷新這個紀錄。

而龐大的數值也來到了四次冪運算。將一個數字乘n次，是指數運算，而現在的結果需要反復對一個數字進行指數運算。例如，10↑↑1只是10，但10↑↑2是10的10次方。

二人不斷突破，運行步數從10↑↑5增長到10↑↑15，而這也促使忙碌海貍數挑戰社區成立。

△圖源：QuantaMagazine

忙碌海貍數挑戰社區，最初目的是嚴格證明 BB(5)的真實值，并在2024夏天成功，關鍵貢獻來自化名mxdys的神秘人。

之后社區成員繼續探索BB(6)，凱特琳?杜塞特發現移位溢出計數器類機器，為研究者們開辟了一條嶄新的道路。

mxdys于今年6月16日宣布發現新的冠軍機器，它的運行步數達到令人咋舌的10↑↑107

這次克羅皮茨也大方地表示失去了冠軍頭銜：

“不幸的是，這次我不會表演我的三天技巧了。”

然而在僅僅一周后，mxdys又打破紀錄，新數值需用五冪運算2↑↑↑5表示，這還只是 BB(6)的下限。

什么概念呢？首先，在普通十進制記法中根本不可能寫出來。

更夸張的是，即使設法將宇宙中每個原子都刻上數字，也會在取得任何可測量的進展之前耗盡這些原子。

我們只能期待，隨著計算機技術的不斷發展和數學理論的日益完善，數學家們逐漸揭開BB(6)的神秘面紗。

正如一位海貍數愛好者Racheline所說：

“對我來說，做數學最正當的理由就是因為它有趣。它是藝術。”

[1]https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/

— 完 —