新智元報(bào)道

編輯：元宇

【新智元導(dǎo)讀】1936年，艾倫·圖靈提出了著名的「停機(jī)問題」。1962年，數(shù)學(xué)家Tibor Radó用「忙碌的海貍游戲」來探索這一問題。60多年來，無數(shù)專業(yè)與業(yè)余數(shù)學(xué)家都加入了這一場(chǎng)史詩級(jí)的追獵之中，新紀(jì)錄不斷誕生，最近找到的數(shù)字，足以撐爆宇宙，讓數(shù)學(xué)圈集體破防。

在大約60多年前，有一位數(shù)學(xué)家，發(fā)明了一個(gè)后來風(fēng)靡全球數(shù)學(xué)圈的游戲：尋找忙碌海貍。

這個(gè)游戲，就是要在固定狀態(tài)數(shù)n的前提下，找到那只在停機(jī)前跑得最久的圖靈機(jī)，它就像忙碌的海貍一樣，不停地折騰。

所以，這個(gè)游戲就正式定名——忙碌的海貍。

當(dāng)狀態(tài)數(shù)n很小時(shí)，步數(shù)就比較容易搞清。

即便是這樣，當(dāng)?shù)?只海貍BB(4)在1983年被確認(rèn)時(shí)，這個(gè)游戲已經(jīng)持續(xù)了20年。

隨后的第五只海貍，即BB(5)，一直到去年，才被最終確定下來。

距離第4只海貍的確認(rèn)，又過去了42年。

由于在「捕獲」BB（5）的過程中，Coq證明助手發(fā)揮了重要作用。

所以，當(dāng)找到第五只海貍時(shí)，著名的數(shù)學(xué)家陶哲軒還特意表示：這再一次體現(xiàn)了數(shù)學(xué)工具對(duì)于數(shù)學(xué)研究的作用多么重要。

BB（1）=1

BB（2）=6

BB（3）=21

BB（4）=107

BB（5）=47176870

BB（6）=？

直到現(xiàn)在，仍舊沒人知道BB(6)有多大。

一直到2022年，「忙碌的海貍數(shù)」挑戰(zhàn)者們確定，BB(6)的數(shù)值，至少大到從物理上，已不可能用標(biāo)準(zhǔn)的十進(jìn)制表示法寫出。

假如你可以使用原子計(jì)數(shù)，就算你把所有原子都用完了，BB(6)仍是遙不可及。

若要描述BB（6）以及之后的冠軍機(jī)，可能要用「一頁紙宇宙」來形容。

區(qū)區(qū)一頁紙規(guī)則，就能推演「宇宙級(jí)」的數(shù)字，輕松碾壓大多數(shù)著名巨數(shù)（費(fèi)舍爾數(shù)、Ackermann 等）。

「它遠(yuǎn)遠(yuǎn)超出了我們所能想象或企及的任何事物」，德克薩斯大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家Scott Aaronson說。

這種極小演繹出極大的爆炸性張力，正是「忙碌海貍」的魅力所在。

這也是它在過去60多年間，能吸引全球無數(shù)專業(yè)及業(yè)余數(shù)學(xué)家狂熱追隨的原因所在。

海貍陷阱

「忙碌的海貍數(shù)」，與理論計(jì)算機(jī)科學(xué)中一個(gè)最「臭名昭著」的難題緊密相連。

這個(gè)難題，就是計(jì)算機(jī)科學(xué)中的一個(gè)經(jīng)典問題——「停機(jī)問題」(halting problem)：

給定一個(gè)計(jì)算機(jī)程序的代碼，你能否判斷它最終會(huì)停止，還是會(huì)永遠(yuǎn)運(yùn)行下去？

1936年，艾倫·圖靈提出并證明了「停機(jī)問題」的不可解性，即不存在一個(gè)通用的算法或程序能回答這個(gè)問題。

艾倫·圖靈

艾倫·圖靈通過發(fā)明一種形式化的計(jì)算數(shù)學(xué)模型，證明了這一開創(chuàng)性成果，其中的程序由一種假設(shè)性的設(shè)備來表示，如今被稱為「圖靈機(jī)」。

每臺(tái)圖靈機(jī)，就好比一個(gè)「照規(guī)則辦事的小機(jī)器人」，它有一張「規(guī)則清單」來指導(dǎo)行動(dòng)。

規(guī)則越少，圖靈機(jī)的行為就越簡(jiǎn)單，很容易就能判斷它會(huì)不會(huì)停機(jī)。

隨著規(guī)則變多，預(yù)測(cè)圖靈機(jī)行為結(jié)果的難度就會(huì)急劇上升，甚至變得不可判定。

1962年，數(shù)學(xué)家Tibor Radó用「忙碌的海貍游戲」來探索這個(gè)問題。

他的玩法是：首先選擇一個(gè)特定的規(guī)則數(shù)量，稱之為n。你的目標(biāo)是找到一臺(tái)擁有n條規(guī)則、且在最終停機(jī)前運(yùn)行時(shí)間最長(zhǎng)的圖靈機(jī)。

這臺(tái)機(jī)器就被稱為「忙碌的海貍」，而相應(yīng)的「忙碌的海貍數(shù)」BB(n)，就是它運(yùn)行的步數(shù)。

原則上，要找到任何給定n的「忙碌的海貍」，你只需做幾件事：

• 首先，列出所有可能的n規(guī)則圖靈機(jī)。

• 接著，用一個(gè)計(jì)算機(jī)程序模擬運(yùn)行每一臺(tái)機(jī)器。尋找機(jī)器永不停機(jī)的跡象——例如，許多機(jī)器會(huì)陷入無限循環(huán)。

• 然后，剔除所有永不停機(jī)的機(jī)器。

• 最后，記錄下其他每一臺(tái)機(jī)器在停機(jī)前運(yùn)行了多少步。

其中運(yùn)行時(shí)間最長(zhǎng)的那臺(tái)，就是你要找的「忙碌的海貍」。

但在實(shí)踐中，這通常會(huì)變得異常棘手。

首先，隨著每條新規(guī)則的增加，可能的機(jī)器數(shù)量將爆炸式增長(zhǎng)。逐一分析它們是毫無希望的，這時(shí)你需要編寫一個(gè)定制的計(jì)算機(jī)程序來分類并篩選機(jī)器。

有些機(jī)器很容易分類，因?yàn)樗鼈円春芸焱C(jī)，要么陷入易于識(shí)別的無限循環(huán)，但另一些機(jī)器卻很難識(shí)別，它們會(huì)運(yùn)行很長(zhǎng)時(shí)間，卻不顯示任何明顯的模式。

「停機(jī)問題」的「恐怖」之名，在這些擅長(zhǎng)「隱藏」的機(jī)器身上得到了淋漓盡致的體現(xiàn)。

有些機(jī)器在停機(jī)前運(yùn)行的時(shí)間之長(zhǎng)，讓逐步模擬它們已無可能，這時(shí)需要運(yùn)用巧妙的數(shù)學(xué)技巧來估量它們的運(yùn)行時(shí)間。

但也只能幫到這里了。

一個(gè)時(shí)代的終結(jié)

上世紀(jì)90年代到21世紀(jì)初，就在對(duì)BB(5)的搜尋陷入僵局時(shí)，「忙碌的海貍數(shù)」追隨者們，又開始遠(yuǎn)征BB(6)。

Shawn Ligocki和他的父親Terry，就是這些挑戰(zhàn)者中的一員。

Shawn Ligocki博客主頁

Terry是一位應(yīng)用數(shù)學(xué)家，他利用勞倫斯伯克利國(guó)家實(shí)驗(yàn)室強(qiáng)大計(jì)算機(jī)的閑暇時(shí)間，來運(yùn)行他們的搜索程序。

2007年，他們發(fā)現(xiàn)了一臺(tái)擁有六條規(guī)則的圖靈機(jī)，打破了當(dāng)時(shí)的最長(zhǎng)運(yùn)行時(shí)間記錄，它在停機(jī)前運(yùn)行的步數(shù)接近3000位。

如果用12號(hào)字體，這3000個(gè)數(shù)字大約能寫滿一頁紙。

三年后，一個(gè)名為Pavel Kropitz的斯洛伐克計(jì)算機(jī)科學(xué)本科生，決定將搜尋BB(6)作為他的畢業(yè)設(shè)計(jì)項(xiàng)目。

他編寫了自己的搜索程序，并將其設(shè)置在一個(gè)大學(xué)實(shí)驗(yàn)室的30臺(tái)計(jì)算機(jī)網(wǎng)絡(luò)上在后臺(tái)運(yùn)行。

一個(gè)月后，他發(fā)現(xiàn)了一臺(tái)打破Shawn Ligocki父子記錄的圖靈機(jī)，用「忙碌的海貍追尋者」的行話來說，這是一位新的「冠軍」。

僅僅一個(gè)月后，這位幸運(yùn)的獵手，便用一臺(tái)運(yùn)行時(shí)間超過30000位數(shù)的機(jī)器打破了自己的記錄——這個(gè)數(shù)字足以寫滿大約10頁紙。

Kropitz保持了BB(6)記錄長(zhǎng)達(dá)12年。

當(dāng)然，Shawn Ligocki也不甘示弱。

他在2022年5月開始了一份新工作，這讓他有條件接觸到強(qiáng)大的計(jì)算機(jī)集群，果然又捕獲到新的「冠軍」，打破了Kropitz的記錄。

2022年，Shawn Ligocki發(fā)現(xiàn)了一臺(tái)六規(guī)則圖靈機(jī)，其運(yùn)行時(shí)間的位數(shù)超過了宇宙中的原子總數(shù)。

兩周之內(nèi)，Ligocki又接連兩次兩次宣布了新的冠軍。

有意思的是，每當(dāng)Ligocki宣布新的冠軍，Kropitz都會(huì)在三天內(nèi)將記錄刷新。

Ligocki和Kropitz發(fā)現(xiàn)的最后兩臺(tái)機(jī)器，其運(yùn)行時(shí)間已達(dá)到了一個(gè)全新的量級(jí)。

如此龐大的數(shù)字，要借助「迭代冪次」(tetration)來計(jì)算。

如果將n個(gè)相同的數(shù)相加，就是乘以n；如果將n個(gè)相同的數(shù)相乘，就是冪運(yùn)算。

如果對(duì)冪運(yùn)算進(jìn)一步拓展，它表示對(duì)一個(gè)數(shù)進(jìn)行多次冪運(yùn)算，也就是「迭代冪次」(tetration)，用兩個(gè)向上的箭頭(↑↑)表示。

10↑↑1就是普通的10。

但10↑↑2是10的10次方，即100億。

而10↑↑3則是10的100億次方：一個(gè)1后面跟著100億個(gè)零。

要寫下這個(gè)數(shù)字，需要一疊高達(dá)一千英尺的紙，大約100層樓那么高。

到了10↑↑4，你就跨越了一個(gè)象征性的門檻，問題不再是紙夠不夠用——這個(gè)數(shù)字的位數(shù)已經(jīng)遠(yuǎn)遠(yuǎn)超過了宇宙中的原子總數(shù)。

一幅描繪大數(shù)如何表示的圖表

當(dāng)Ligocki第二次打破Kropitz的記錄時(shí)，他所用的是一臺(tái)六規(guī)則圖靈機(jī)，其運(yùn)行步數(shù)超過了10↑↑5。

Kropitz則用一臺(tái)運(yùn)行步數(shù)為10↑↑15的機(jī)器予以回?fù)簟@是一個(gè)由10構(gòu)成的、高達(dá)15層的「冪塔」。

這已經(jīng)遠(yuǎn)遠(yuǎn)超越了我們熟悉的數(shù)字世界。

「一個(gè)時(shí)代就此終結(jié)」，Kropitz嘆道。

瘋狂的新境界

在那之后，「忙碌的海貍游戲」開始從單打獨(dú)斗變成了聯(lián)合作戰(zhàn)——「忙碌海貍挑戰(zhàn)」社區(qū)成立，開啟了一個(gè)協(xié)作的新時(shí)代。

這個(gè)社區(qū)，是一位名叫Tristan Stérin的研究生，在2022年發(fā)起的一個(gè)名叫「忙碌海貍挑戰(zhàn)」的在線協(xié)作項(xiàng)目，聚合了來自全球各地的數(shù)學(xué)「發(fā)燒友」，他們中的大多數(shù)都沒有傳統(tǒng)的學(xué)術(shù)資格。

「忙碌海貍挑戰(zhàn)」社區(qū)發(fā)起者Tristan Stérin

「忙碌海貍挑戰(zhàn)」社區(qū)地址https://bbchallenge.org/

「忙碌海貍挑戰(zhàn)」社區(qū)的明確目標(biāo)，是嚴(yán)格證明BB(5)的真實(shí)值。

去年7月，這個(gè)社區(qū)的志愿者們利用Coq證明助手確認(rèn)了BB（5）。

今年6月，一位來自該社區(qū)中最神秘大神證明了BB(6)的一個(gè)新下限，并在短短九天后再次刷新了紀(jì)錄。

數(shù)學(xué)家們一次次被震驚。

馬里蘭大學(xué)的計(jì)算機(jī)科學(xué)家William Gasarch驚呼：

「BB(6)正把我們帶入龐大數(shù)字的平流層?！?/p>

2024年夏天，一位化名「mxdys」的神秘新人做出了關(guān)鍵貢獻(xiàn)，吸引了弗吉尼亞理工大學(xué)的計(jì)算機(jī)科學(xué)本科生Katelyn Doucette。

她很快也加入了「忙碌的海貍挑戰(zhàn)」社區(qū)，從此也成了搜尋BB(6)的活躍分子。

她在mxdys分類的幾千臺(tái)BB(6)「頑固」機(jī)器列表中，發(fā)現(xiàn)了一個(gè)「異類」，它的運(yùn)行時(shí)間僅次于Kropitz的衛(wèi)冕冠軍。

它一個(gè)的重要特別之處在于：它屬于一類被稱為「移位溢出計(jì)數(shù)器」(shift overflow counters)的機(jī)器。

采用與Kropitz衛(wèi)冕冠軍截然不同的機(jī)制來實(shí)現(xiàn)超長(zhǎng)運(yùn)行時(shí)間。

「移位溢出計(jì)數(shù)器」的出現(xiàn)并非孤例，這讓Shawn Ligocki興奮不已，他推測(cè)此類機(jī)器的數(shù)量要遠(yuǎn)超他們的想象。

于是，「移位溢出計(jì)數(shù)器」很快成了研究者們的「新寵」。

mxdys搶先一步，在6月16日，他宣布發(fā)現(xiàn)了一位新的冠軍，它在10↑↑107步后停機(jī)。

也就是說，其運(yùn)行時(shí)間是一個(gè)由10構(gòu)成、高達(dá)1000萬層的「冪塔」。

當(dāng)我們談?wù)摗?0構(gòu)成的冪塔」時(shí)，它實(shí)際上指的是多次將10作為底數(shù)進(jìn)行指數(shù)運(yùn)算。

要把這個(gè)數(shù)字，寫成一長(zhǎng)串?dāng)?shù)字已絕無可能，即使將它寫成一個(gè)冪塔也變得非常困難：如果用12號(hào)字體，這一行10的連乘將延伸約25英里（40公里），接近洛杉磯到好萊塢的距離。

這一消息，直接將Kropitz拉下王座，他坦然接受了冠軍頭銜的失落，并表示自己將無法再表演「三天反殺」的絕技了。

超越「最大之大」

但不出意外，這項(xiàng)新紀(jì)錄并未持續(xù)多久。

一周后，mxdys用另一臺(tái)機(jī)器再次刷新了它，而這臺(tái)機(jī)器的運(yùn)行時(shí)間，再一次有了質(zhì)的突破。

如果要以最簡(jiǎn)潔的形式寫下它，需要引入一個(gè)近乎「荒謬」的數(shù)學(xué)運(yùn)算——「五級(jí)運(yùn)算」(pentation)，它是重復(fù)的迭代冪次，要用三個(gè)向上的箭頭(↑↑↑)表示。

它與迭代冪次的關(guān)系，就如同迭代冪次與冪運(yùn)算的關(guān)系。

mxdys的新冠軍在停機(jī)前運(yùn)行的總步數(shù)超過了2↑↑↑5，即2↑↑(2↑↑(2↑↑(2↑↑2)))。

要展開這個(gè)表達(dá)式，你需要從最內(nèi)層的括號(hào)向外計(jì)算：2↑↑2是4，而2↑↑4略超65,000。這樣你就剩下2↑↑(2↑↑65,000)，使得最終那個(gè)由2構(gòu)成的堆棧的高度，本身就是一個(gè)大到無法想象的數(shù)字。

不要說寫一個(gè)延伸數(shù)英里或數(shù)百萬秒差距的冪塔了，就連這種更緊湊的表示法，也已無法容納于宇宙之中。

這是一個(gè)要撐爆宇宙的數(shù)字了！

一幅描繪一臺(tái)最近發(fā)現(xiàn)的圖靈機(jī)所遵循的六條規(guī)則的圖表

這個(gè)新結(jié)果，仍然只是BB(6)的一個(gè)下限——真實(shí)值可能還要高得多。

「忙碌的海貍數(shù)」追尋者們，預(yù)計(jì)短期內(nèi)不會(huì)有確切答案。

如果想要取得新的突破，可能就需要在純數(shù)學(xué)領(lǐng)域取得概念性的突破。

但這并不意味著這些「忙碌的海貍數(shù)」的追隨者們，就無事可做了。仍有數(shù)千臺(tái)六規(guī)則圖靈機(jī)等待被探索，每一臺(tái)都展現(xiàn)著其獨(dú)特的豐富行為。

Racheline說，「做數(shù)學(xué)最正當(dāng)?shù)睦碛删褪撬苡腥?，它是一門藝術(shù)?！?/p>

只要有了興趣，你就永遠(yuǎn)都會(huì)有新的事情可做。

參考資料：

https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/%20%20

https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/