聞樂(lè) 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI

衡量圖靈機(jī)最大運(yùn)行步數(shù)的海貍數(shù)（busy beaver number）紀(jì)錄，被刷新了！

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

假如將宇宙里的每個(gè)原子都刻上數(shù)字，也無(wú)法完全容納它。

也就是說(shuō)，用咱平時(shí)熟悉的十進(jìn)制根本沒(méi)辦法完全表示，得用超復(fù)雜的五冪運(yùn)算來(lái)描述：指數(shù)套指數(shù)再套指數(shù)

△圖源：QuantaMagazine

這到底是個(gè)什么樣的神秘?cái)?shù)字呢？

研究圖靈機(jī)極限能力的數(shù)字

海貍數(shù)，專(zhuān)業(yè)點(diǎn)說(shuō)叫忙碌海貍數(shù)BB(n)。它背后藏著圖靈在1936年就證明的停機(jī)問(wèn)題：

你永遠(yuǎn)沒(méi)法用通用程序判斷一臺(tái)圖靈機(jī)到底是運(yùn)行有限步驟后就停機(jī)，還是會(huì)一直無(wú)限運(yùn)行下去。

所以找這個(gè)數(shù)，本質(zhì)是在觸碰計(jì)算機(jī)能解決問(wèn)題的邊界

圖靈機(jī)的計(jì)算方式是在無(wú)限長(zhǎng)的磁帶上讀取和寫(xiě)入0和1，磁帶劃分為很多個(gè)單元格，一個(gè)讀寫(xiě)頭一次可以操作一個(gè)單元格。

每臺(tái)圖靈機(jī)都有自己的規(guī)則，規(guī)則規(guī)定讀寫(xiě)頭在進(jìn)入新的單元格時(shí)，遇到0或1分別該進(jìn)行什么操作。

除此之外還有一個(gè)特殊的規(guī)則告訴圖靈機(jī)要停止運(yùn)行。

于是圖靈機(jī)在運(yùn)行過(guò)程中會(huì)出現(xiàn)運(yùn)行有限次就停機(jī)或者無(wú)限循環(huán)運(yùn)行兩種狀態(tài)。

1962年，數(shù)學(xué)家Tibor Radó發(fā)明了忙碌海貍游戲，通過(guò)尋找特定規(guī)則數(shù)的圖靈機(jī)在停機(jī)前運(yùn)行最長(zhǎng)時(shí)間來(lái)定義忙碌海貍數(shù)BB(n)。

例如，若選擇規(guī)則數(shù)n=5，目標(biāo)就是找到有5條規(guī)則的圖靈機(jī)中運(yùn)行時(shí)間最長(zhǎng)才停機(jī)的那個(gè)，它在停機(jī)前執(zhí)行的步數(shù)，就是BB(5)。

這就好比一群運(yùn)動(dòng)員在跑步，看誰(shuí)堅(jiān)持的時(shí)間最長(zhǎng)，這個(gè)最長(zhǎng)時(shí)間就是海貍數(shù)。

從20世紀(jì)70年代起，數(shù)學(xué)家們就踏上了尋找海貍數(shù)的漫漫長(zhǎng)路。

對(duì)于BB(1)，情況相對(duì)簡(jiǎn)單，因?yàn)閱我灰?guī)則的圖靈機(jī)實(shí)際上只有兩種可能性，要么第一步就停機(jī)，要么一直運(yùn)行下去，所以很容易就確定了BB(1)=1

到了BB(2)，難度稍有提升。此時(shí)，需要考慮超過(guò)6000個(gè)不同的圖靈機(jī)。但一個(gè)相對(duì)簡(jiǎn)單的程序足以證明BB(2)=6

而確定 BB(3) 時(shí)，挑戰(zhàn)大幅增加。因?yàn)槿?guī)則的圖靈機(jī)數(shù)量膨脹到數(shù)百萬(wàn)。1965年，研究人員經(jīng)過(guò)大量的研究和推算，在16777216個(gè)圖靈機(jī)中，找出了最多可以執(zhí)行21個(gè)計(jì)算步驟的圖靈機(jī)，即BB(3)=21

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

確定前四個(gè)海貍數(shù)就耗費(fèi)了幾十年時(shí)間，而B(niǎo)B(5)更是直到去年，才被一個(gè)業(yè)余的數(shù)學(xué)家團(tuán)隊(duì)成功攻克，確定BB(5)=47176870

△圖源：QuantaMagazine

團(tuán)隊(duì)關(guān)鍵貢獻(xiàn)來(lái)自一個(gè)化名為mxdys的神秘人

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

BB(6)的突破

20世紀(jì)90年代，研究者開(kāi)始認(rèn)真探索BB(6) 。

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

2010年，克羅皮茨找到運(yùn)行時(shí)間更長(zhǎng)的機(jī)器，步數(shù)超30000位。克羅皮茨的BB(6)紀(jì)錄保持了12年。

2022年，利戈茨基借助新硬件打破記錄，引發(fā)了與克羅皮茨的競(jìng)爭(zhēng)，利戈茨基兩次宣布新紀(jì)錄，克羅皮茨都能在三天內(nèi)刷新這個(gè)紀(jì)錄。

而龐大的數(shù)值也來(lái)到了四次冪運(yùn)算。將一個(gè)數(shù)字乘n次，是指數(shù)運(yùn)算，而現(xiàn)在的結(jié)果需要反復(fù)對(duì)一個(gè)數(shù)字進(jìn)行指數(shù)運(yùn)算。例如，10↑↑1只是10，但10↑↑2是10的10次方。

二人不斷突破，運(yùn)行步數(shù)從10↑↑5增長(zhǎng)到10↑↑15，而這也促使忙碌海貍數(shù)挑戰(zhàn)社區(qū)成立。

△圖源：QuantaMagazine

忙碌海貍數(shù)挑戰(zhàn)社區(qū)，最初目的是嚴(yán)格證明 BB(5)的真實(shí)值，并在2024夏天成功，關(guān)鍵貢獻(xiàn)來(lái)自化名mxdys的神秘人。

之后社區(qū)成員繼續(xù)探索BB(6)，凱特琳?杜塞特發(fā)現(xiàn)移位溢出計(jì)數(shù)器類(lèi)機(jī)器，為研究者們開(kāi)辟了一條嶄新的道路。

mxdys于今年6月16日宣布發(fā)現(xiàn)新的冠軍機(jī)器，它的運(yùn)行步數(shù)達(dá)到令人咋舌的10↑↑107

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

“不幸的是，這次我不會(huì)表演我的三天技巧了?！?br/>

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

什么概念呢？首先，在普通十進(jìn)制記法中根本不可能寫(xiě)出來(lái)。

更夸張的是，即使設(shè)法將宇宙中每個(gè)原子都刻上數(shù)字，也會(huì)在取得任何可測(cè)量的進(jìn)展之前耗盡這些原子。

我們只能期待，隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展和數(shù)學(xué)理論的日益完善，數(shù)學(xué)家們逐漸揭開(kāi)BB(6)的神秘面紗。

正如一位海貍數(shù)愛(ài)好者Racheline所說(shuō)：

“對(duì)我來(lái)說(shuō)，做數(shù)學(xué)最正當(dāng)?shù)睦碛删褪且驗(yàn)樗腥?。它是藝術(shù)?！?br/>

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

— 完 —