選自quantamagazine

作者：Ben Brubaker

機器之心編譯

當(dāng)數(shù)字逃離人類的想象力：BB (6) 的故事。

現(xiàn)在給你一串?dāng)?shù)字，你能猜到一下個是多少嗎：1、6、21、107，47176870……

如果你沒頭緒，不必氣餒。因為這些數(shù)字并不是隨意湊出來的，它們就是所謂的 「忙碌海貍數(shù)」的前五項。它們構(gòu)成的數(shù)列，與理論計算機科學(xué)中最令人頭疼的問題之一緊密相關(guān)。要想弄清這些數(shù)的具體值，是一項堪稱不可攀登高峰的挑戰(zhàn)。六十多年來，這個難題不僅吸引了頂尖數(shù)學(xué)家的持續(xù)攻堅，還讓無數(shù)業(yè)余愛好者為之癡迷，形成了一種獨特的「數(shù)學(xué)文化圈」。

最近，這條探索之路上又出現(xiàn)了新的突破。忙碌海貍獵人們找到了一個全新的冠軍程序，它的運行步數(shù)之大，以至于用標(biāo)準(zhǔn)的數(shù)學(xué)符號體系根本無法完整寫出。換句話說，他們已經(jīng)抵達了 超出常規(guī)數(shù)學(xué)所能承載的境地。

在上世紀(jì)六七十年代，研究人員先后確定了前四個忙碌海貍數(shù)。而那個遠遠龐大的第五個數(shù) BB (5)，直到去年才被徹底鎖定。完成這項壯舉的，并不是某個頂尖實驗室，而是一支由業(yè)余數(shù)學(xué)愛好者組成的團隊，他們通過一個名為 「Busy Beaver Challenge」的網(wǎng)絡(luò)社區(qū)，日復(fù)一日協(xié)作攻關(guān)，最終拿下了這一難題。

至于 BB (6)，它的真實大小至今仍是一個謎。我們唯一掌握的，只是一些下界 —— 而這些下界本身就已經(jīng)大到匪夷所思。2022 年，忙碌海貍獵人們證明：BB (6) 至少大到，即使用普通十進制記號也絕無可能完整寫下。哪怕你試圖把每一個數(shù)字都刻在宇宙中每一粒原子上，還沒來得及寫出有意義的部分，原子就已經(jīng)耗盡。

「已經(jīng)遠遠超出了人類可以想象或真正掌握的范圍。」德克薩斯大學(xué)奧斯汀分校的計算機科學(xué)家 Scott Aaronson 如此感嘆。

現(xiàn)在，忙碌海貍獵人們再次刷新紀(jì)錄：那個已經(jīng)大到令人難以想象的數(shù)字，其實還要更大。最新突破來自 Busy Beaver Challenge 中一位既神秘又高產(chǎn)的貢獻者。今年 6 月，他首次為 BB (6) 推出了一個全新的下界；然而僅僅九天之后，他又把紀(jì)錄再度推高。相比之下，2022 年的下界，如今顯得幾乎不值一提。

「我一次次被震撼到。」 馬里蘭大學(xué)的計算機科學(xué)家 William Gasarch 感嘆道，「BB (6) 已經(jīng)把我們帶進了龐大數(shù)字的『平流層』。」

忙碌海貍真正難題

忙碌海貍背后真正讓大家棘手的問題是，給定一段計算機程序的代碼，你能判斷它最終會停止運行還是會一直運行下去嗎？

1936 年，傳奇邏輯學(xué)家阿蘭?圖靈就潑過冷水 —— 他證明了，這事兒根本沒法兒靠一個萬能公式解決。這就是后來赫赫有名的「停機問題」。換句話說，不管你多聰明，哪怕你能搞定一部分程序，必然會有另一些程序讓你徹底抓狂。甚至在某些情況下，不存在任何辦法可以給出答案。

圖靈為了證明這一劃時代的結(jié)論，創(chuàng)造了一種形式化的數(shù)學(xué)計算模型。在這個模型里，程序不再是抽象的符號，而被想象成一種理想化的裝置 —— 今天我們稱之為圖靈機。

每一臺圖靈機都依據(jù)一份獨特的「規(guī)則清單」，一步步地執(zhí)行計算。規(guī)則看似簡單，但數(shù)量越多，機器的行為就會變得越復(fù)雜，也就越難判斷它究竟會不會停下來。

但問題是：到底會有多難呢？

1962 年，數(shù)學(xué)家 Tibor Radó 發(fā)明了一種全新的方法來探索這個疑問，他把它稱作忙碌海貍游戲。玩法是這樣的：先挑一個規(guī)則數(shù)量 —— 記作 n。你的目標(biāo)，就是找到那臺擁有 n 條規(guī)則的圖靈機，它能在最終停機之前跑得最久。這臺機器就叫忙碌海貍，而它所堅持的步數(shù)，就定義為 忙碌海貍數(shù) BB (n)。

原則上，如果你想找出任意給定 n 的忙碌海貍，步驟也不算復(fù)雜：

列清單：把所有可能的 n 規(guī)則圖靈機都羅列出來；做模擬：用計算機程序去運行這些機器；篩掉「永動機」：很多機器會陷入無限循環(huán)，這些明顯不會停機的統(tǒng)統(tǒng)剔除；統(tǒng)計步數(shù)：記錄剩下的每臺機器在停機前走了多少步。

最后，跑得最久、堅持到最后一刻才停下的，就是你的忙碌海貍。

不過，這些步驟在實際操作中，這件事會變得非常棘手。首先，隨著規(guī)則數(shù)量的增加，可能的機器數(shù)量會迅速膨脹。要逐一分析它們幾乎是一件不可能的事情，因此必須寫專門的計算機程序來分類并剔除機器。部分機器很容易判斷：要么很快停機，要么陷入一眼就能識別的無限循環(huán)。但另一些機器卻能運行很久，卻絲毫沒有顯現(xiàn)出明顯的規(guī)律。正是這種情況，讓停機問題贏得了令人望而生畏的聲名。

規(guī)則加得越多，你就需要越強大的計算力。但僅靠蠻力遠遠不夠。有些機器在最終停機前，會運行得漫長得不可想象，逐步模擬根本不現(xiàn)實。這時，就必須祭出一些精巧的數(shù)學(xué)技巧，才能測量它們的運行時長。

「技術(shù)的進步當(dāng)然有幫助，」 軟件工程師、長期的忙碌海貍獵人 Shawn Ligocki 說道，「但幫助也僅限于此。」

一個時代的終結(jié)

在 20 世紀(jì) 90 年代到 21 世紀(jì)初，忙碌海貍獵人們逐漸把注意力轉(zhuǎn)向 BB (6) —— 因為在 BB (5) 的探索中，他們一度陷入僵局。活躍在這股浪潮中的，有 Shawn Ligocki 和他的父親 Terry，一位應(yīng)用數(shù)學(xué)家。父子倆利用勞倫斯伯克利國家實驗室的高性能計算機，在閑置時段偷偷運行自己的搜索程序，繼續(xù)追逐這場數(shù)字極限挑戰(zhàn)。

終于在 2007 年，他們發(fā)現(xiàn)了一臺刷新紀(jì)錄的六規(guī)則圖靈機。它在停機前足足跑出了近 3,000 位數(shù)字的步數(shù)。按常理來看，這已經(jīng)是一個龐大得驚人的數(shù)字。然而，它依舊算不上「無法書寫」。如果用 12 號字體排版打印，那看似無邊無際的三千位數(shù)，其實只夠鋪滿一張普通的打印紙 —— 一張薄薄的紙片，竟承載了人類當(dāng)時所能觸及的最大極限。

2022 年，Shawn Ligocki 發(fā)現(xiàn)了一臺六規(guī)則圖靈機，它在停機前的運行步數(shù)所包含的數(shù)字位數(shù)，竟然比整個宇宙中的原子數(shù)量還要多。

三年后，斯洛伐克一名計算機科學(xué)本科生 Pavel Kropitz 決定把攻克 BB (6) 當(dāng)作自己的畢業(yè)論文課題。他編寫了自己的搜索程序，并在大學(xué)實驗室的 30 臺計算機上后臺運行。一個月后，他發(fā)現(xiàn)了一臺運行時間遠超 Ligocki 父子發(fā)現(xiàn)的圖靈機 —— 在忙碌海貍獵人的術(shù)語中，這就是新的冠軍。

「我算是運氣好，因為實驗室的人已經(jīng)開始抱怨我占用 CPU 過多，所以我不得不稍微收斂一些。」Kropitz 在 Busy Beaver Challenge 的 Discord 服務(wù)器上通過私信寫道。又過了一個月，他打破了自己的紀(jì)錄，找到了一臺運行時間超過 30000 位數(shù)字的圖靈機 —— 足以寫滿大約 10 頁紙。

這臺由 Kropitz 找到的機器，保持了 BB (6) 的紀(jì)錄整整 12 年。

2022 年 5 月，Shawn Ligocki 入職新工作，手里有了強大的計算集群。他心血來潮，把多年前寫的老代碼搬到新硬件上試跑。果然，他找到了一臺新的冠軍圖靈機，打破了 Kropitz 的紀(jì)錄。這一發(fā)現(xiàn)立刻點燃了忙碌海貍社區(qū)的熱情。短短兩周內(nèi)，Ligocki 就在郵件列表上兩度宣布新的冠軍。然而每一次，Kropitz 都能在三天內(nèi)刷新他的成績。Ligocki 記得父親當(dāng)時驚嘆不已。

「他開玩笑說，感覺 Pavel 早就把 BB (6) 解出來了，」Ligocki 回憶道，「因為每當(dāng)我們宣布一個新冠軍，他就會像變魔術(shù)一樣，從口袋里掏出一個更大的。」

不過，Ligocki 和 Kropitz 后來發(fā)現(xiàn)的那兩臺機器，已經(jīng)不是多跑一點點，而是把運行時間推向了全新的層級。

要理解這種巨大的數(shù)字，我們得回到熟悉的數(shù)學(xué)操作。

加法：把一個數(shù)加 n 次，就是乘以 n。乘法：把一個數(shù)乘 n 次，就是指數(shù)運算。

那么，如果我們不斷對一個數(shù)做指數(shù)運算呢？這就定義了一種新的運算，叫做超乘（tetration），用兩個向上的箭頭↑↑表示。

超乘的增長速度快得驚人：

10↑↑1 只是 10；10↑↑2 是 10 的 10 次方，即 100 億；10↑↑3 是 10 的 100 億次方，也就是一個 1 后面跟著 100 億個零。要把所有數(shù)字寫下來，需要一摞足有 300 米高 的紙。當(dāng)來到 10↑↑4 時，情況徹底失控：這個數(shù)的位數(shù)已經(jīng)遠遠超過整個宇宙的原子數(shù)。

當(dāng) Ligocki 第二次超越 Kropitz 時，他找到了一臺六規(guī)則圖靈機，在停機前竟然跑了超過 10↑↑5 步。很快，Kropitz 就以更驚人的成果回應(yīng)：一臺能運行 10↑↑15 步的機器 —— 相當(dāng)于一座高達 15 層的 10 的冪塔。到此為止，他們已經(jīng)徹底告別了人類習(xí)慣理解的數(shù)字世界。

「那是一個時代的終結(jié)。」 Kropitz 在私信中寫道。

這種終結(jié)不止體現(xiàn)在數(shù)字的飛躍上，也體現(xiàn)在研究方式的轉(zhuǎn)變上。在此之前，忙碌海貍游戲更像是一場你追我趕的競技場，研究者們大多單打獨斗。而隨著 Busy Beaver Challenge 的建立，這場探索進入了一個全新的階段 —— 從孤軍奮戰(zhàn)走向開放協(xié)作，一個真正的群體探索時代就此開啟。

開啟新時代的挑戰(zhàn)

Busy Beaver Challenge 社區(qū)成立于 2022 年，由計算機科學(xué)研究生 Tristan Stérin 受 Aaronson 論文的啟發(fā)而發(fā)起。目標(biāo)十分明確：要嚴(yán)格證明 BB (5) 的真實值。

僅在社區(qū)成立兩年后，該社區(qū)就完成了對 BB (5) 真實值的證明。這個證明過程中深度使用了 Coq 智能證明助手。Coq 通過 Gallina 編程語言，讓用戶定義數(shù)學(xué)對象、陳述定理，并一步步構(gòu)建證明。用戶可以與 Coq 進行交互，逐步驗證每一步的正確性。Coq 還提供了多種自動化工具，幫助簡化證明過程。

2024 年 5 月 10 日，「忙碌的海貍挑戰(zhàn)」社區(qū)中一位神秘的成員發(fā)了一條消息，稱「BB (5) 的 Coq 證明已完成。」，他只留下了化名 mxdys。

消息鏈接:https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237Coq 證明鏈接：https://github.com/ccz181078/Coq-BB5

當(dāng)時在弗吉尼亞理工大學(xué)讀本科的計算機科學(xué)學(xué)生 Katelyn Doucette 正好讀到 BB (5) 被證明的消息，很快被吸引。

「我就這么被迷住了。」她說，「這真是一組無比優(yōu)美的問題。」

自從完成 BB (5) 的證明后，神秘的 mxdys 就不斷向 BB (6) 發(fā)起挑戰(zhàn)。他采用復(fù)雜的自動化方法，將幾乎所有候選圖靈機分類處理，只剩下幾千臺待定的圖靈機。

Katelyn Doucette 正在翻閱這些待定的圖靈機時，注意到其中一臺看起來很有潛力，深入分析后發(fā)現(xiàn)，這臺機器的運行時間僅次于現(xiàn)任冠軍。

更令人驚訝的是，這臺機器屬于一種被稱為「移位溢出計數(shù)器（shift overflow counters）」的類別，它的長時間運行機制與冠軍機完全不同。

「看到這些忙碌海貍機居然找到了『新技術(shù)』，真是令人興奮。」Ligocki 評價道。

既然這類新技術(shù)的相關(guān)圖靈機的最開始的幾個樣本就能做到與現(xiàn)任冠軍接近，那么在后續(xù)迭代中，采用移位溢出計數(shù)器的圖靈機中很可能出現(xiàn)打破記錄的新冠軍。

于是，Busy Beaver Challenge 的貢獻者們立刻涌向其他移位溢出計數(shù)器的分析，而 mxdys 又一次搶先一步。

6 月 16 日，他宣布發(fā)現(xiàn)了新的冠軍：一臺能運行 10↑↑107 步的圖靈機。

這樣的數(shù)字，根本不可能寫成完整的十進制數(shù)列。甚至把它寫成冪塔表達式也很奢侈—— 如果用 12 號字體把那一長串的 10↑↑↑↑… 排出來，整條公式能拉長約 40 公里。

正在度假的 Kropitz 看到了消息，他大方地接受了冠軍易主的事實，還在 Discord 上調(diào)侃道：「很遺憾，這次我沒法再來一次三天逆襲了。」

突破全新量級

但這個龐大的「新紀(jì)錄」僅僅只維持了一周，神秘的 mxdys 大神又一次刷新了自己的紀(jì)錄，帶來了一臺運行時間達到全新量級的圖靈機。

如果說上一個記錄勉強還能使用「超乘」作為數(shù)學(xué)符號來表達，那這個全新量級的新紀(jì)錄甚至必須再次引入一個全新的數(shù)學(xué)符號：五乘（pentation）。

五乘采用三個向上的箭頭「↑↑↑」表示，本質(zhì)上就是「重復(fù)做超乘」。

這臺冠軍機在停機前執(zhí)行的總步數(shù)，大于：2↑↑↑5

也就是：2↑↑(2↑↑(2↑↑(2↑↑2)))。

如果從最里面開始計算：

2↑↑2 = 42↑↑4 = 稍大于 65,000

這樣，外層就變成：2↑↑65,000 … 最終結(jié)果是一個大到完全超出想象的數(shù)，即便用最簡潔的符號表達，這個數(shù)字依然大到超出了宇宙極限。

就像 BB (5) 在 2024 年才被嚴(yán)格證明一樣，BB (6) 的數(shù)值遠沒有達到能被證明的程度。這一超越極限的新紀(jì)錄仍然只是 BB (6) 的下界 —— 真實值可能還要更高，忙碌海貍獵人們也確實無法能在短期內(nèi)得到最終答案。

一臺被命名為「Antihydra（反九頭蛇）」的六狀態(tài)圖靈機給忙碌海貍獵人們帶來了很大的麻煩。

研究者幾乎可以肯定：「反九頭蛇」永遠不會停機。但問題是，他們至今沒法證明這一點。原因也很清楚：一位代號 Racheline 的獵人展示過，判斷反九頭蛇是否停機，其實和數(shù)學(xué)中一個著名的未解難題「考拉茲猜想（Collatz conjecture）」密切相關(guān)。

從那以后，團隊又發(fā)現(xiàn)了許多具有類似特征的六狀態(tài)機器。

但是，如果要徹底解決同類的六狀態(tài)機的證明問題，可能需要在純數(shù)學(xué)領(lǐng)域取得根本性突破。

不過，對狂熱的忙碌海貍獵人來說，這一點都不是沮喪的理由。還有成千上萬臺六狀態(tài)圖靈機等待探索，每一臺都有自己獨特而精彩的行為模式。

「對我來說，做數(shù)學(xué)最正當(dāng)?shù)睦碛删褪牵核猛妗Ｋ且婚T藝術(shù)。」Racheline 在 Discord 的私信里寫道，「總會有新的東西值得去探索。」

忙碌海貍問題，和停機問題一樣，都是不可計算問題的具體體現(xiàn)，沒有一個通用算法能算出所有 BB (n) 的精確值。對于這類問題的探索，能夠不斷推動計算理論和數(shù)學(xué)邊界的拓展，這也塑造了數(shù)學(xué)與計算機科學(xué)的獨特魅力。

參考鏈接：

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

https://bbchallenge.org/1RB1RA_1RC1LB_0LD0RA_1LA0LE_0LF1LD_---0LB

https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237