★加星zzllrr小樂公眾號數(shù)學科普不迷路！

最近《量子雜志》計算機科學專欄作家Ben Brubaker撰文探討了忙碌海貍游戲與數(shù)學中一個著名的開放性問題——科拉茨猜想（Collat??z猜想，即3n+1猜想）之間的聯(lián)系。

一只勇敢忙碌的海貍，正與可怕的反九頭蛇正面交鋒。插畫由才華橫溢的Nico Roper繪制。

作者：Ben Brubaker（量子雜志計算機科學專欄作家）2025-10-22

譯者：zzllrr小樂（數(shù)學科普公眾號）2025-10-28

2024年夏天，我報道了一個在線社區(qū) https://bbchallenge.org ， 該社區(qū)確定了一個名為BB(5)的數(shù)字的精確值 https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ ——這是50年來在理論計算機科學領域一個古老問題（被稱為“忙碌海貍游戲”）上取得的首個重大突破。BB(5)，現(xiàn)在已知為47176870，是所謂的“忙碌海貍數(shù)”中的第五個，該數(shù)衡量的是簡單計算機程序能夠完成的最復雜計算的復雜度。（該團隊最近發(fā)表了一篇論文，詳細描述了他們的研究結果 http://arxiv.org/abs/2509.12337 。）

這項獨特的研究工作的下一步是確定第六個忙碌海貍數(shù) BB(6)，目前已經(jīng)取得了一些顯著進展——幾個月前我寫了一篇后續(xù)文章 https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/ 。但忙碌海貍研究人員并不指望能很快確定 BB(6) 的真正值。這是因為要做到這一點，他們需要理解一個名為“Antihydra”（反九頭蛇）的程序的行為，這個程序類似于數(shù)學中一個長期懸而未決的問題——科拉茨（Collat??z）猜想（即3n+1猜想）。 （請不要將反九頭蛇與假九頭蛇 https://goblinpunch.blogspot.com/2014/09/false-hydra.html 混淆，后者是 D&D 博主 Arnold Kemp 構思的一種非?？崆曳浅？膳碌墓治?。）

一位分享了我第一個忙碌海貍故事的 Twitter 用戶更簡潔地總結了這種情況：

需要注意的是：“編碼 Collat??z 猜想”并不完全正確，我們稍后會看到。

我的兩篇故事都只是非常簡短地提到了“反九頭蛇”屏障。在這篇博文中，我將更詳細地探討它：反九頭蛇究竟是什么？什么是“科拉茨猜想”？它們之間有何關聯(lián)？以及它們?yōu)楹稳绱肆钊送罚?/p>

忙碌海貍的基礎知識

如果你還沒讀過我寫的兩篇《量子雜志》上關于“忙碌海貍”游戲的故事，建議你先讀讀，因為這兩篇故事都很有趣！接下來我會回顧一下“忙碌海貍”游戲的玩法，以便大家能夠理解。

我上面寫道，忙碌海貍數(shù)“衡量的是簡單計算機程序所能完成的最瘋狂計算的復雜性”。為了更準確地定義它們，我們首先需要一個數(shù)學框架來衡量計算機程序本身的復雜性，以確定哪些程序是“簡單的”。然后，我們需要一種方法來量化計算的復雜性——計算機程序所做的事情——這樣我們才能識別出最瘋狂的程序。

在“忙碌海貍”游戲中，計算機程序由一種名為圖靈機的假想設備來表示，這些設備通過在被劃分為多個單元的無限磁帶上讀寫 0 和 1，以離散的步驟進行計算。每臺圖靈機的行為都受一套獨特的規(guī)則控制。任何你能用普通計算機程序完成的事情，原則上都能用一套合適的圖靈機規(guī)則來完成。（在忙碌海貍文獻中，這些規(guī)則被稱為“狀態(tài)”。） “原則上”在這句話中承擔了大量工作——即使你設法獲得了必要的無限磁帶，用圖靈機進行計算也會極其低效。但從理論上講，圖靈機比更實用的編程語言更容易分析。

讓我們更詳細地解析一下圖靈機的工作原理。在每一步中，圖靈機都會參考其中一條規(guī)則并編輯磁帶上的一個單元格。每條規(guī)則有兩種情況：如果當前單元格包含 0 該怎么辦？如果當前單元格包含 1 該怎么辦？“該怎么辦”在這里指的是在當前單元格中寫入什么、下一步要朝哪個方向移動以及下一步要參考哪條規(guī)則。其中一條規(guī)則的一種情況打破了這種模式：它告訴圖靈機“停止”，即停止運行。但這條指令本身的存在并不能保證圖靈機會停止——機器可能永遠不會停止。

量子雜志的視覺設計師 Kristina Armitage 將所有這些內(nèi)容封裝在一張精美的信息圖中。 （在我的第一篇忙碌海貍故事中，你還會看到圖靈機運行的動畫。 https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ ）

圖源： Kristina Armitage / Quanta Magazine 的“忙碌的海貍獵人得出的數(shù)字超越了普通數(shù)學”

圖靈機所擁有的規(guī)則數(shù)量將作為我們衡量程序復雜度的標準。這種選擇讓我們能夠將關于簡單計算機程序能夠完成的最復雜任務的模糊問題，替換為一系列關于不同復雜程度的具體問題，這些問題對應不同的忙碌海貍數(shù)。你可以通過回答“單規(guī)則圖靈機能夠完成的最復雜計算是什么？”這個問題來了解 BB(1)的值。同樣，BB(2)衡量雙規(guī)則圖靈機能夠完成的最復雜計算，依此類推。

要回答這些問題，我們需要一個精確的定義，來解釋是什么使得一個計算比另一個計算更復雜。一個自然的衡量標準是圖靈機完成計算需要多少步?！巴瓿伞焙苤匾颗_永不停止的圖靈機都會運行無限多步，但這實際上不是一個公平的比較。圖靈機在停止之前（以及它是否停止）所執(zhí)行的步數(shù)可能取決于磁帶上 0 和 1 的初始模式。對于忙碌海貍游戲，我們總是從所謂的“空白磁帶”開始，磁帶的每個單元都是 0。

現(xiàn)在，我們已經(jīng)掌握了正式定義忙碌海貍數(shù)的所有必要信息。我們以 BB(6) 為例：它是所有六規(guī)則圖靈機中，從空白磁帶啟動時最長的有限運行時間。原則上，找到這個數(shù)字很簡單。首先，列出所有可能的六規(guī)則圖靈機。接下來，將它們分為兩類：一類是最終會在空白磁帶上運行時停止的機器，另一類是永遠運行的機器。剔除所有不停機的機器。最后，測量每臺停機機器在停止前需要執(zhí)行多少步。最大的數(shù)字是 BB(6)。

該計劃的問題在于第二步，即根據(jù)圖靈機是否停止，將其分成兩組。事實證明，判斷一臺圖靈機是否會停止，這可以說是一個極其困難的問題。如果你無法判斷一臺給定的機器是否會停止，那么你就無法確定你的停止圖靈機列表是否完整，也就無法確定是否找到了運行時間最長的機器！截至本文撰寫時，研究人員已將絕大多數(shù)六規(guī)則機器分為停止型或非停止型。但仍有 1618 臺“未停止”機器的命運未知。

反九頭蛇（Antihydra）就是這些“頑固分子”之一。為了確定 BB(6)的值，研究人員必須首先確定反九頭蛇是否會停止運行，而這似乎超出了任何已知數(shù)學方法的范疇。為了理解其中的原因，我們需要退一步思考：“這些圖靈機到底在做什么？”

進階

你可能會反對這一點，認為我們已經(jīng)確切地知道這些圖靈機在做什么：每臺圖靈機只是遵循特定的規(guī)則序列，在磁帶上邊走邊寫 0 和 1。但這種“低級”描述有點像說“當我按下這些按鈕時，我的袖珍計算器會按照特定的模式打開和關閉晶體管”。這很可能是真的，但像“當我按下這些按鈕時，我的袖珍計算器會將 3 和 4 相乘”這樣的“高級”描述通常更有用。

無法保證任何給定的圖靈機的行為都能接受這種簡單的高級描述。（此外，在很多情況下，低級描述就足夠了。例如，證明圖靈機停止運行最簡單的方法就是逐步模擬它，直到它停止運行。當這種情況發(fā)生時，你不需要深入了解它停止的原因：只需記錄它的運行時間，然后繼續(xù)下一步即可。） 但請記住，圖靈機可以執(zhí)行所有可能的計算 - 這意味著至少有一些圖靈機必須執(zhí)行具有人類可以理解的高級描述的程序。

實際上，迄今為止，忙碌海貍的研究人員研究過的最著名的五規(guī)則和六規(guī)則圖靈機都具有相對簡單的高級描述 - 其中包括最終停止的運行時間最長的五規(guī)則和六規(guī)則機器、最復雜的非停止五規(guī)則機器，以及像 Antihydra（反九頭蛇）這樣的頑固分子。（這是一個經(jīng)驗觀察，而非不證自明的真理。事實上，一些研究人員曾預計，運行時間最長的圖靈機將是缺乏任何高級描述的“意大利面條式代碼”機器！ https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html ）

讓我們看一個具體的例子。第五個忙碌海貍在停止前運行了 47176870 步，遵循以下低級規(guī)則：

圖源：忙碌海貍大挑戰(zhàn)?！啊北硎尽巴Ｖ埂薄?https://bbchallenge.org/story

1993年，數(shù)學家帕斯卡·米歇爾（Pascal Michel）證明這些規(guī)則等同于一個簡單的高級程序 http://link.springer.com/10.1007/BF01409968 ：

1. 設 x=0 。

2. 將 x 除以 3 并檢查余數(shù)。

   如果余數(shù)為 0，則計算 (5x+18)/3 。結果就是新的x值。

   如果余數(shù)為 1，則計算 (5x+22)/3 。結果就是新的x值。

   如果余數(shù)為 2，則停止。

3. 如果尚未停止，請返回步驟 2 并插入新的x值 。

一旦你有了這樣的高級描述，你就可以使用它來確定機器是否會停止 - 如果會，那么它到底需要多少步。（像這樣的高級程序中的每一步都對應著許多獨立的圖靈機步驟。每當你證明高級描述和低級描述之間的等價性時，你都會得到一些公式，可以用來計算每個高級步驟需要多長時間。我不會談論如何實際證明這些等價性。） 在這種情況下，高級程序只是重復插入新的 x 值，直到找到一個除以 3 余 2 的值。三分之一的數(shù)字具有該性質，因此你可能會猜測程序將需要或多或少三次嘗試才能找到一個。如果從隨機值 x 開始，你會發(fā)現(xiàn)三次迭代確實是典型的。但事實證明，如果從 x=0 開始，該程序將重復第二步 15 次，才能找到余數(shù)為 2 的數(shù)字！忙碌海貍研究人員經(jīng)常喜歡將他們研究的圖靈機擬人化，想象這些機器正在積極地嘗試盡可能長時間地運行。采用這種觀點，我們可以說這臺圖靈機非常幸運。

第五只忙碌的海貍只是“Collat??z 類”圖靈機家族的一員，其高級行為具有以下一般形式：

1. 將 x 設置為某個起始值（可能是 0 也可能不是）。

2. 用 x 除以一個固定數(shù) N 。余數(shù)告訴你該用什么公式來得到新的值 x 。

3. 檢查是否滿足特定的停止條件。

   如果沒有，則返回步驟 2，并使用新值 x 。

   （正如我們在上面的例子中看到的，停止條件可以簡單到“余數(shù)具有特定值”。下面我們將看到一些具有不同停止條件的例子。）

類 Collat??z 圖靈機家族包括停機機和非停機機。它的名字來源于數(shù)學家 Lothar Collat??z（洛塔爾·科拉茨，1910 - 1990）于1937年設計的一種生成數(shù)字序列的程序：

1. 為 x 選擇一個起始值。

2. 檢查 x 是偶數(shù)還是奇數(shù)。

   如果是偶數(shù)，則計算 x/2 。結果就是新的 x 值。

   如果是奇數(shù)，則計算 3x+1 。結果就是新的 x 值。

3. 檢查是否滿足 x=1 。如果不是，則返回步驟 2。

這看起來與我們對 Collat??z 類機器高級行為的一般描述非常相似，以 x=1 作為停止條件。 （“檢查 x 是偶數(shù)還是奇數(shù)”其實就是“用 x 除以 2 并檢查余數(shù)”的另一種說法。嚴格來說，我們不必指定序列在 x=1 時停止。但如果在 x=1 之后繼續(xù)應用規(guī)則，序列就會進入無限循環(huán)：1 > 4 > 2 > 1，依此類推。）

嘗試從任意初始整數(shù)值 x 迭代這些規(guī)則 https://collatz-graph.vercel.app ——我愿意打賭，無論你選多少數(shù)字，你最終都會得到 1。Collat??z猜想 https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/ 斷言，對于每個正整數(shù)，無論??多大，都會發(fā)生這種情況。人們已經(jīng)對所有至少 20億萬億（！）以內(nèi)的整數(shù)進行了實證檢驗，沒有發(fā)現(xiàn)任何反例，這有力地暗示該猜想是正確的。但沒有人知道如何嚴格證明它。

神秘動物學

讓我們退一步來看。在這篇文章的開頭，我指出了科拉茨猜想和“反九頭蛇”之間的聯(lián)系：沒有人知道如何證明科拉茨猜想，這就是為什么研究人員不知道如何最終確定“反九頭蛇”是否會停止運行。但現(xiàn)在，我把科拉茨猜想與第五個“忙碌海貍”聯(lián)系起來，后者是一臺已被證明會停止運行的機器。這到底是怎么回事？

這個看似難題的解決方案是：對于忙碌海貍游戲，我們只關心圖靈機從特定磁帶配置（即空白磁帶）開始運行時是否會停止。這意味著我們只關心相應的類 Collat??z 序列是否會因單個輸入而停止。而 Collat??z猜想則詢問是否最終對每個輸入都命中 x=1 。很容易證明 Collat??z 序列最終對任何一個輸入都命中 x=1 ，就像很容易證明第五個忙碌海貍會停止一樣（一旦你建立了其低級規(guī)則和高級類 Collat??z 程序之間的等價關系）。事實上，忙碌海貍獵人海納·馬克森 (Heiner Marxen) 和尤爾根·邦特羅克 (Jürgen Buntrock) 率先通過直接模擬證明了第五只忙碌海貍會停止行動（盡管他們使用了一些技巧來加快速度）。米歇爾只是在事后才識別出它的高級行為。

我們可以輕松構建 Collat??z 問題的變體，即使對于單個輸入，它也很難解決。我們需要做的就是將奇數(shù)的 3x+1 規(guī)則更改為 5x+1 。在這種情況下，從某些輸入（例如 x=7 ）開始的軌跡看起來會發(fā)散，永遠不會達到 1，也不會陷入循環(huán)。但研究人員還無法證明這些軌跡中的任何一個會發(fā)散。這里面存在著內(nèi)在的不對稱性。如果你想證明一個序列最終會在某個地方結束，你總是可以使用蠻力，至少在原則上是這樣。但如果你想證明一個序列永不終止，即使是單個輸入也可能很難。

現(xiàn)在，我們終于準備好對抗恐怖的“反九頭蛇”（Antihydra https://wiki.bbchallenge.org/wiki/Antihydra ）了。它遵循以下高級規(guī)則：

1. 設置 x=8 。

   （這看起來似乎有點奇怪，因為在“忙碌海貍”游戲中，我們應該從空白磁帶開始。但在這里仍然如此——只是 Antihydra（反九頭蛇） 在開始迭代這個序列之前，花了一段時間在磁帶上進行操作，而所有這些操作的最終效果是將起始值設置為 8。）

2. 檢查 x 是偶數(shù)還是奇數(shù)。

   如果是偶數(shù)，計算 3x/2 。結果就是新的 x 值。將你應用此偶數(shù)規(guī)則的次數(shù)加一。

   如果是奇數(shù)，計算 (3x?1)/2 。結果就是新的 x 值。將你應用此奇數(shù)規(guī)則的次數(shù)加一。

3. 檢查“奇數(shù)”計數(shù)是否是“偶數(shù)”計數(shù)的兩倍以上。

   如果是，則停止。

   如果不是，則返回步驟 2。

這是一組非常奇特的規(guī)則。公式 3x/2 和 (3x?1)/2 似乎并沒有系統(tǒng)地偏向奇數(shù)或偶數(shù)，所以你可能會認為，反復迭代它們就像反復拋硬幣并記錄正面和反面出現(xiàn)的次數(shù)一樣。在拋硬幣的初期，正面出現(xiàn)的次數(shù)很可能是反面出現(xiàn)的次數(shù)的兩倍以上。但如果這種情況沒有立即發(fā)生，那么隨著拋硬幣時間的延長，這種可能性就會越來越小。

研究人員現(xiàn)在已經(jīng)模擬了 Antihydra 的行為超過 2700 億步，正如預期的那樣，“偶數(shù)”和“奇數(shù)”的計數(shù)非常接近相等——遠沒有達到停機條件所要求的極端不平衡程度。因此，Antihydra 永不停機的可能性似乎非常大。但沒有人知道如何證明這一點！數(shù)學家約翰·康威 (John Conway，1937 - 2020) 為這種情況創(chuàng)造了一個令人愉快的術語“probviously”（（probabilistic + obvious + ly）——在這種情況下，感興趣的具體問題很難解決，但對類似問題的“典型”行為進行概率推理使得答案變得顯而易見。

反九頭蛇的行為在性質上與 Collat??z 猜想的 5x+1 版本相似，我們尚不清楚如何證明任何單一軌跡都會發(fā)散。我想強調(diào)的是，就研究人員所知，這兩個問題之間并沒有更精確的數(shù)學聯(lián)系：解決了其中一個問題，并不會自動解決另一個問題。但這兩個問題看似困難，原因卻非常相似。如果有人真的成功證明 Collat??z 猜想，那么證明中使用的數(shù)學技巧很可能對解決反九頭蛇問題大有裨益（反之亦然）。

實際上，Antihydra 只是眾多具有類似 Collat??z 行為的、可能不停機的圖靈機之一。當這些機器首次在標準“忙碌海貍”游戲的變體中被發(fā)現(xiàn)時，忙碌海貍獵人 Shawn Ligocki 將這些機器稱為“神秘生物”（cryptids https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html ）。 這些變體除了 0 和 1 之外還使用額外的磁帶符號。例如，忙碌海貍游戲的 BB(3,3) https://wiki.bbchallenge.org/wiki/BB(3,3) 版本研究了具有三個規(guī)則的圖靈機的行為，這些規(guī)則可以讀寫三個符號：0、1 和 2。

一只神秘生物，被弗恩 (Fern) 的朋友、忙碌海貍大挑戰(zhàn)discord 服務器成員勞倫 (Lauren) 描繪成洛夫克拉夫特式（Lovecraftian）的海貍。

最早被發(fā)現(xiàn)的兩種神秘生物分別名為“大腳怪”（https://wiki.bbchallenge.org/wiki/Bigfoot )和“九頭蛇”（https://wiki.bbchallenge.org/wiki/Hydra “反九頭蛇”因與“九頭蛇”在數(shù)學上的聯(lián)系而得名）；研究人員如今已發(fā)現(xiàn)如此之多的神秘生物，以至于不再有必要為每一種生物單獨命名。所有這些神秘生物的存在意味著，在研究人員開發(fā)出新的數(shù)學工具來解決類似 Collat??z 問題之前，BB(5) 以上的忙碌海貍數(shù)仍將遙不可及。據(jù)說，傳奇數(shù)學家保羅·埃爾德什（Paul Erd?s，1913 - 1996）曾說過：“數(shù)學可能還沒有準備好應對此類問題?！?/p>

但這并不意味著忙碌海貍獵人應該放棄。在所謂的“神秘動物生態(tài)學”領域，仍有許多問題有待探索。神秘動物有多少個亞種？它們之間以及與科拉茨猜想之外的其他數(shù)學未解問題之間有何關聯(lián)？ https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ 自忙碌海貍狩獵開始以來，狂熱的獵人就不斷遇到令人驚訝的圖靈機新行為，而且這種模式絲毫沒有減弱的跡象。

今年八月，我去了密歇根州上半島的塔夸梅農(nóng)瀑布，這里似乎是大腳怪目擊事件的熱點地區(qū)。幸運的是，我沒有遇到任何神秘生物，但我確實對一些比較友好的小動物有了些了解。驚喜的發(fā)現(xiàn)可能無處不在！

參考資料

https://benbrubaker.com/why-busy-beaver-hunters-fear-the-antihydra/

https://bbchallenge.org

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

http://arxiv.org/abs/2509.12337

http://link.springer.com/10.1007/BF01409968

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

https://goblinpunch.blogspot.com/2014/09/false-hydra.html

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/

https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/

https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html

https://collatz-graph.vercel.app

https://wiki.bbchallenge.org/wiki/Antihydra

https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html

https://wiki.bbchallenge.org/wiki/BB(3,3)

https://wiki.bbchallenge.org/wiki/Bigfoot

https://wiki.bbchallenge.org/wiki/Hydra

小樂數(shù)學科普近期文章

出版社和作家自薦通道

小樂數(shù)學科普薦書

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

加星★

數(shù)學科普不迷路！