忙碌海狸函数：修订间差异

2025年7月15日 (二) 17:58的版本

忙碌海狸函数（Busy Beaver Function，又名BB函数或Radó的Σ函数）是一个不可计算的快速增长函数。它是最著名的不可计算函数，也是专业数学中出现的有史以来增长最快的函数之一。

定义

图灵机

图灵机，是由英国数学家艾伦・麦席森・图灵于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。

它由一条无限长的纸带以及一个读头构成。纸带上有无限多个顺次排列的方格，每个方格都具有一个特定的值。读头可以存储图灵机自身的状态，在纸带上移动，或者是修改纸带中某个方格的值。

在起始时刻，图灵机的纸带上已经预先写好了每个格子的值，然后将图灵机的读头放到某一个给定的格子上，然后，图灵机将根据自身编码的指令集（即图灵程序）进行运动。在每个时刻，图灵机将读取读头对应的格子的值以及自身的状态，然后将这个格子的值改变为某一个值、将图灵机自身的状态改变为某一状态，并将读头移动到某个相邻的位置。特别的，图灵机具有一个特殊的状态，称为停机状态，我们将之记为H。如果图灵机运行到了停机状态，那么它将停止运动，图灵机的程序结束。

我们可以引入一个表格来表示图灵机的程序。我们用列表示图灵机的当前状态，行表示读头对应的格子的值。每个指令都是一个有三个字符组成的字符串。第一个字符是读头把当前格子的值改变为什么值，第二个字符是读头接下来是向左移动还是向右移动，第三个字符是读头接下来把图灵机改变为哪个新的状态。

作为一个例子，我们给出一个图灵机的程序，它纸带上的取值是0或者1，它有两个状态A和B。

图灵机
	A	B
0	1RB	1LA
1	1LB	1RB

例如，左上角的1RB代表当这个图灵机在状态A之下读取到了格子上是0，那么它把格子的值改写为1，向右移动一格，并且把图灵机的状态变为B。其余指令的含义是类似的，这里不再赘述。下面我们在一个所有格子全为0的纸带上运行这个图灵机，它的初始状态是A：

000000 A $⟶$ 000100 B $⟶$ 000110 A $⟶$ 000110 B $⟶$ 001110 A $⟶$ 011110 B $⟶$ 011110 B

其中下划线代表读头所处位置，序列后的字母代表图灵机此刻所处状态。可以看出，它经过6步停机，扫过了4个格子，把4个格子的0变为了1.

如果纸带上有n种不同的值，我们称这个图灵机是n-色的。

考虑一台图灵机，如果它最终可以停下来，则称它是可停机的，反之则称它是不可停机的。判断一个图灵机能否停机是极其困难的。事实上我们有停机定理：不存在一个程序，能够判断所有程序是否能够停机。

图灵机的结构是简单的，但事实上，图灵机的计算能力是非常强大的。为了让图灵机计算函数，我们可以对其进行适当的编码。例如，如果要求开始时的输入是 $n_{1}, \dots, n_{k}$ ，则在纸带上分别用 $n_{1} + 1$ 个连续的1，……， $n_{k} + 1$ 个连续的1表示它们，数与数之间用0隔开。待图灵机结束运行之后，纸带上1的个数即为图灵机的输出。

如果一个函数可以用一个图灵机来实现，那么定义其为一个图灵可计算函数。我们有如下的定理：图灵可计算函数和递归函数等价。即，凡是递归函数，都可以被某个图灵机所实现。

忙碌海狸函数

我们定义忙碌海狸函数如下：

一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为 $B B (n)$ 或者 $Σ (n)$ .^[1]我们称这样的图灵机是“忙碌的海狸”。

取值

很难证明特定的图灵机是否恰好是一只忙碌的海狸。n状态的2色的图灵机有 $(4 n + 4)^{2 n}$ 台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至 $(2 n - 1) (4 n)^{2 n - 2}$ ^[2]，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术(适用于较小的n)和自上而下技术(适用于较大的n)。

对于自下而上技术：

运行一些可能的图灵机。
对于某个较大的限制 X，如果计算机运行超过 X 步还没停机，则假定它无限期运行并被忽略。
从我们没有忽略的机器中，找到写入次数最多的机器。

对于自上而下技术：

找到一些快速增长的函数 $f (x)$
使用图灵机模拟 $f (x)$

例如，如果我们可以在具有 100 种状态的机器上计算 Goodstein 函数，那么很可能对于相对较大的i有 $B B (100) > G (i)$

由于BB函数增长的过于快，第一种方法很快就变得不可行。因此，通常使用自上而下的技术。

请注意，对任何可计算函数，BB函数最终都会超越它，这个是显然的。而棘手的问题在于BB函数何时会超越它，如果不实际评估，这很难回答.

据信，该函数的FGH 增长率，是 Church-Kleene 序数 $ω_{1}^{C K}$ ，即所有递归序数的集合。

对于BB(1),显然，它只有立刻停机一种可能。因此 $B B (1) = 1$

BB(2)所对应的图灵机为：^[3]


	A	B
0	1RB	1LA
1	1LB	1RH

可得BB(2)=4.

BB(3)所对应的图灵机是^[4]


	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

可得BB(3)=6.

BB(4)所对应的图灵机是^[5]


	A	B	C	D
0	1RB	1LA	1RH	1RD
1	1LB	0LC	1LD	0LA

可得BB(4)=13

BB(5)所对应的图灵机是^[6]^[7]


	A	B	C	D	E
0	1RB	1RC	1RD	1LA	1RH
1	1LC	1RB	0LE	1LD	0LA

可得BB(5)=4098

对于更之后的BB函数，我们还未计算出精确值。我们有

$B B (6) \geq 2 ↑ ↑ 2 ↑ ↑ 2 ↑ ↑ 9$ ^[8]

$B B (7) \geq 2 ↑^{11} 2 ↑^{11} 3$ ^[9]

Milton Green证明了 $B B (2 n) ≫ 3 ↑^{n - 2} 3$ .^[10]BB(6)已经远远大于27，因此这个下界是很弱的。

葛立恒数是一个非常著名的大数，但它在一些较小的n就被BB(n)超越。目前最新的成果是 Daniel Nagaj证明了BB(14)>葛立恒数，该证明被Shawn Ligocki所确认。^[11]

对于一些较大的n，Wythagoras证明了 $B B (38) > f_{ω \times 2} (67)$ 、 $B B (64) > f_{ω^{2}} (4098)$ 以及 $B B (85) > f_{ε_{0}} (1907)$

Rohan Ridenour证明了BB(1015)超过了Loader数^[12]。HypCos在他的作品《大数入门》中提到BB(160)已经大于Loader数，但没有给出出处。

据信 $B B (150) > f_{S H O} (10 ↑ ↑ 15)$ ,其中SHO是BMS的极限。^[13]

传言

有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于BB(27),这实际上是错误的。正确的说法是，我们找到了一个27状态的2色图灵机^[14]，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有5372个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。

Yedidia还写了这样一个程序，它验证这样一个命题: ZF是一致（自洽）的，它有7918个状态。

趣事

曹知秋找到了以下三段话，读起来令人忍俊不禁.

无论如何，即使熟练的数学家和经验丰富的程序员尝试计算BB(3)和S(3),也没有证据表明任何已知方法能够给出答案，即使我们利用高速计算机和复杂的程序。至于BB(4)和S(4),目前的情况似乎完全没有希望。——Tibor Radó,1963.
BB(5)=4098和S(5)=47176870将永远无法得到证明。——Allen H. Brady,1990.
无论如何，我们可以绝对肯定的说，S(6)的值永远不会被证明。——BBChallenge Collaboration,2025.

事实上，我们必须知道，我们必将知道。

参考资料

↑ Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.

↑ Notes on Busy Beaver Function

↑ Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)

↑ Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)

↑ A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).

↑ H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).

↑ [July 2nd 2024] We have proved "BB(5) = 47,176,870" - News - The Busy Beaver Challenge

↑ https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE

↑ https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc

↑ Green, Milton. A lower bound RADO's sigma function for binary turing machines. Retrieved 2013-05-07.

↑ BB(16) > Graham's Number

↑ https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe

↑ https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf

↑ https://link.zhihu.com/?target=https%3A//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6

[1] Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.

[2] Notes on Busy Beaver Function

[3] Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)

[4] Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)

[5] A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).

[6] H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).

[7] [July 2nd 2024] We have proved "BB(5) = 47,176,870" - News - The Busy Beaver Challenge

[8] ttps://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE

[9] ttps://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc

[10] Green, Milton. A lower bound RADO's sigma function for binary turing machines. Retrieved 2013-05-07.

[11] BB(16) > Graham's Number

[12] ttps://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe

[13] ttps://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf

[14] ttps://link.zhihu.com/?target=https%3A//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ 第36行： / 第36行： @@
 考虑一台图灵机，如果它最终可以停下来，则称它是可停机的，反之则称它是不可停机的。判断一个图灵机能否停机是极其困难的。事实上我们有停机定理：不存在一个程序，能够判断所有程序是否能够停机。
+图灵机的结构是简单的，但事实上，图灵机的计算能力是非常强大的。为了让图灵机计算函数，我们可以对其进行适当的编码。例如，如果要求开始时的输入是<math>n_1,\cdots,n_k</math>，则在纸带上分别用<math>n_1+1</math>个连续的1，……，<math>n_k+1</math>个连续的1表示它们，数与数之间用0隔开。待图灵机结束运行之后，纸带上1的个数即为图灵机的输出。
+如果一个函数可以用一个图灵机来实现，那么定义其为一个'''图灵可计算函数'''。我们有如下的定理：图灵可计算函数和[[递归函数]]等价。即，凡是递归函数，都可以被某个图灵机所实现。
 === 忙碌海狸函数 ===
 我们定义忙碌海狸函数如下：
-一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为<math>BB(n)</math>或者<math>\Sigma(n)</math>.<ref>Rado, T. "[https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x On Non-Computable Functions.]" Bell System Technical J. 41, 877-884, May 1962.</ref>
+一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为<math>BB(n)</math>或者<math>\Sigma(n)</math>.<ref>Rado, T. "[https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x On Non-Computable Functions.]" Bell System Technical J. 41, 877-884, May 1962.</ref>我们称这样的图灵机是“忙碌的海狸”。
 == 取值 ==
+很难证明特定的图灵机是否恰好是一只忙碌的海狸。n状态的2色的图灵机有<math>(4n+4)^{2n}</math>台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至<math>(2n-1)(4n)^{2n-2}</math><ref>[https://mrob.com/pub/math/ln-notes1-4.html Notes on Busy Beaver Function]</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术(适用于较小的n)和自上而下技术(适用于较大的n)。
+对于自下而上技术：
+# 运行一些可能的图灵机。
+# 对于某个较大的限制 X，如果计算机运行超过 X 步还没停机，则假定它无限期运行并被忽略。
+# 从我们没有忽略的机器中，找到写入次数最多的机器。
+对于自上而下技术：
+# 找到一些快速增长的函数<math>f(x)</math>
+# 使用图灵机模拟<math>f(x)</math>
+例如，如果我们可以在具有 100 种状态的机器上计算 Goodstein 函数，那么很可能对于相对较大的i有<math>BB(100)>G(i)</math>
+由于BB函数增长的过于快，第一种方法很快就变得不可行。因此，通常使用自上而下的技术。
+请注意，对任何可计算函数，BB函数最终都会超越它，这个是显然的。而棘手的问题在于BB函数''何时''会超越它，如果不实际评估，这很难回答.
+据信，该函数的[[FGH]][[增长率]]，是 Church-Kleene 序数<math>\omega_1^{CK}</math>，即所有递归序数的集合。
 对于BB(1),显然，它只有立刻停机一种可能。因此<math>BB(1)=1</math>
@@ 第101行： / 第126行： @@
 可得BB(4)=13
-BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref>
+BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>
 {| class="wikitable mw-collapsible mw-collapsed"
 |+
@@ 第133行： / 第158行： @@
 <math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>
+Milton Green证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>.<ref>Green, Milton. [https://doi.ieeecomputersociety.org/10.1109/SWCT.1964.3 A lower bound RADO's sigma function for binary turing machines]. Retrieved 2013-05-07.</ref>BB(6)已经远远大于27，因此这个下界是很弱的。
+[[葛立恒数]]是一个非常著名的大数，但它在一些较小的n就被BB(n)超越。目前最新的成果是 Daniel Nagaj证明了BB(14)>葛立恒数，该证明被Shawn Ligocki所确认。<ref>[https://www.sligocki.com/2022/07/11/bb-16-graham.html BB(16) > Graham's Number]</ref>
+对于一些较大的n，Wythagoras证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math>以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>
+Rohan Ridenour证明了BB(1015)超过了[[Loader数]]<ref>https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos在他的作品《大数入门》中提到BB(160)已经大于Loader数，但没有给出出处。
+据信<math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>,其中[[SHO]]是[[Bashicu矩阵|BMS]]的极限。<ref>https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>
+== 相关函数 ==
+=== 疯狂青蛙函数S(n) ===
+Tibor Radó 引入了另一个不可计算的快速增长函数S(n)，根据n状态2色图灵机在停止前所走的最多步数来定义。有时忙碌海狸函数会被认为是最大移动步数。为避免歧义，S(n)又称为疯狂青蛙函数。
+由于图灵机运行时会左右摇摆，所以<math>S(n)\geq BB(n)</math>.一个忙碌的海狸也不一定是一个疯狂的青蛙。已经证明，疯狂青蛙函数与忙碌海狸函数具有相当的增长率。
+=== 二元忙碌海狸BB(m,n) ===
+我们定义二元忙碌海狸函数BB(m,n)为一个能够停机的m色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数。
+类似的，也可以定义二元疯狂青蛙函数。
+== 传言 ==
+有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于BB(27),这实际上是错误的。正确的说法是，我们找到了一个27状态的2色图灵机<ref>https://link.zhihu.com/?target=https%3A//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有5372个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。
+Yedidia还写了这样一个程序，它验证这样一个命题: ZF是一致（自洽）的，它有7918个状态。
+== 趣事 ==
+曹知秋找到了以下三段话，读起来令人忍俊不禁.<blockquote>无论如何，即使熟练的数学家和经验丰富的程序员尝试计算BB(3)和S(3),也没有证据表明任何已知方法能够给出答案，即使我们利用高速计算机和复杂的程序。至于BB(4)和S(4),目前的情况似乎完全没有希望。——Tibor Radó,1963.
+BB(5)=4098和S(5)=47176870将永远无法得到证明。——Allen H. Brady,1990.
+无论如何，我们可以绝对肯定的说，S(6)的值永远不会被证明。——BBChallenge Collaboration,2025.</blockquote>事实上，'''我们必须知道，我们必将知道'''。<blockquote>
 == 参考资料 ==
+<references /></blockquote>