為什么“忙碌海貍”獵人害怕“反九頭蛇”——忙碌海貍游戲與科拉茨猜想的聯(lián)系

★加星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年來在理論計算機科學領(lǐng)域一個古老問題（被稱為“忙碌海貍游戲”）上取得的首個重大突破。BB(5)，現(xiàn)在已知為47176870，是所謂的“忙碌海貍數(shù)”中的第五個，該數(shù)衡量的是簡單計算機程序能夠完成的最復雜計算的復雜度。（該團隊最近發(fā)表了一篇論文，詳細描述了他們的研究結(jié)果 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 構(gòu)思的一種非常酷且非常可怕的怪物。）

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

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

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

忙碌海貍的基礎(chǔ)知識

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

我上面寫道，忙碌海貍數(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ù)量將作為我們衡量程序復雜度的標準。這種選擇讓我們能夠?qū)㈥P(guān)于簡單計算機程序能夠完成的最復雜任務的模糊問題，替換為一系列關(guān)于不同復雜程度的具體問題，這些問題對應不同的忙碌海貍數(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。但這種“低級”描述有點像說“當我按下這些按鈕時，我的袖珍計算器會按照特定的模式打開和關(guān)閉晶體管”。這很可能是真的，但像“當我按下這些按鈕時，我的袖珍計算器會將 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 。結(jié)果就是新的x值。

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

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

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

一旦你有了這樣的高級描述，你就可以使用它來確定機器是否會停止 - 如果會，那么它到底需要多少步。（像這樣的高級程序中的每一步都對應著許多獨立的圖靈機步驟。每當你證明高級描述和低級描述之間的等價性時，你都會得到一些公式，可以用來計算每個高級步驟需要多長時間。我不會談論如何實際證明這些等價性。） 在這種情況下，高級程序只是重復插入新的 x 值，直到找到一個除以 3 余 2 的值。三分之一的數(shù)字具有該性質(zhì)，因此你可能會猜測程序?qū)⑿枰蚨嗷蛏偃螄L試才能找到一個。如果從隨機值 x 開始，你會發(fā)現(xiàn)三次迭代確實是典型的。但事實證明，如果從 x=0 開始，該程序?qū)⒅貜偷诙?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 。結(jié)果就是新的 x 值。

   如果是奇數(shù)，則計算 3x+1 。結(jié)果就是新的 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)系起來，后者是一臺已被證明會停止運行的機器。這到底是怎么回事？

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

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

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

1. 設置 x=8 。

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

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

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

   如果是奇數(shù)，計算 (3x?1)/2 。結(jié)果就是新的 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)造了一個令人愉快的術(shù)語“probviously”（（probabilistic + obvious + ly）——在這種情況下，感興趣的具體問題很難解決，但對類似問題的“典型”行為進行概率推理使得答案變得顯而易見。

反九頭蛇的行為在性質(zhì)上與 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ù)學可能還沒有準備好應對此類問題。”

但這并不意味著忙碌海貍獵人應該放棄。在所謂的“神秘動物生態(tài)學”領(lǐng)域，仍有許多問題有待探索。神秘動物有多少個亞種？它們之間以及與科拉茨猜想之外的其他數(shù)學未解問題之間有何關(guān)聯(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ù)學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

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

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

加星★

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