查看“︁忙碌海狸函数”︁的源代码

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

=== 定义 ===

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

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

[[文件:test.png|frame|right|200px|图中展示了一个图灵机]]

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

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

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

[[文件:Busy-beaver-two-states-test.gif|frame|right|200px|二状态图灵机]]

{| class="wikitable" border="0" cellpadding="1" cellspacing="1"
! scope="col" |
! scope="col" |A
! scope="col" |B
|-
|0
|1RB
|1LA
|-
|1
|1LB
|1RB
|}

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

000<u>0</u>00 A→0001<u>0</u>0 B→000<u>1</u>10 A→00<u>0</u>110 B→0<u>0</u>1110 A→01<u>1</u>110 B→011<u>1</u>10 B

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

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

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

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

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

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

一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref name=":0">Rado, T. (1962). On Non-Computable Functions. ''Bell System Technical J'', Vol. 41, pp. 877-884. Available at  https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x</ref>我们称这样的图灵机是“忙碌的海狸”。

=== 取值 ===
很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和排除具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. (n.d.). Notes on Busy Beaver Function. ''(EB/OL), Mrob''. Available at: https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是困难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。

对于自下而上技术：

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

对于自上而下技术：

# 找到一些快速增长的函数 <math>f(x)</math>
# 使用图灵机模拟 <math>f(x)</math>

例如，如果我们可以在具有 100 种状态的机器上计算 [[Goodstein函数|Goodstein 函数]]，那么很可能对于相对较大的 i 有<math>BB(100)>G(i)</math>。

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

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

据信，该函数的 [[FGH]] [[增长率]]是 [[CKO|Church-Kleene 序数]] <math>\omega_1^{\rm CK}</math>，即所有[[序数#递归序数|递归序数]]的集合。

对于 BB(1)，显然，它只有立刻停机一种可能。因此 <math>BB(1)=1</math>。

BB(2) 所对应的图灵机为：<ref name=":0" />

{| class="wikitable" border="0" cellpadding="1" cellspacing="1"
! scope="col" |
! scope="col" |A
! scope="col" |B
|-
|0
|1RB
|1LA
|-
|1
|1LB
|1RH
|}

可得 BB(2) = 4。

[[文件:Busy-beaver-three-states-new.png|frame|right|200px|三状态图灵机]]

BB(3) 所对应的图灵机是<ref>Lin., & Rado, T. (1965). Computer Studies of Turing Machine Problems. ''Journal for the Association of Computing Machinery'', Vol. 12, No. 2, pp. 196-212.</ref>

{| class="wikitable" border="0" cellpadding="1" cellspacing="1"
! scope="col" |
! scope="col" |A
! scope="col" |B
! scope="col" |C
|-
|0
|1RB
|0RC
|1LC
|-
|1
|1RH
|1RB
|1LA
|}

可得 BB(3) = 6。

[[文件:Busy-beaver-four-states-new.png|frame|right|200px|四状态图灵机]]

BB(4) 所对应的图灵机是<ref>Brady, A. H. (1975). Solution of the non-computable "Busy Beaver" game for k=4. ''ACM Computer Science Conference'', pp. 27.</ref>

{| class="wikitable" border="0" cellpadding="1" cellspacing="1"
! scope="col" |
! scope="col" |A
! scope="col" |B
! scope="col" |C
! scope="col" |D
|-
|0
|1RB
|1LA
|1RH
|1RD
|-
|1
|1LB
|0LC
|1LD
|0LA
|}

可得 BB(4) = 13。

BB(5) 所对应的图灵机是<ref>Marxen, H., & Buntrock, J. (1990). Attacking the Busy Beaver 5 Bulletin. ''EATCS'', Vol. 40, pp. 247-251.</ref><ref>The Busy Beaver Challenge (2024). We have proved "BB(5) = 47,176,870". ''(EB/OL), The Busy Beaver Challenge''. Available at:  https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237</ref>
{| class="wikitable" border="0" cellpadding="1" cellspacing="1"
! scope="col" |
! scope="col" |A
! scope="col" |B
! scope="col" |C
! scope="col" |D
! scope="col" |E
|-
|0
|1RB
|1RC
|1RD
|1LA
|1RH
|-
|1
|1LC
|1RB
|0LE
|1LD
|0LA
|}

可得 BB(5) = 4098。

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

<math>BB(6)\geq2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9</math><ref>The Busy Beaver Challenge (n.d.). 1RB1RA 1RC--- 1LD0RF 1RA0LE 0LD1RC 1RA0RE. ''(EB/OL), The Busy Beaver Challenge''. Available at:  https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>

<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>Google Groups (n.d.). Busy Beaver Discuss - l5vKduGGKJc. ''(EB/OL)''. Available at:  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, M. (2013). A lower bound RADO's sigma function for binary turing machines. ''(n.p.)'', [[Doi:10.1109/SWCT.1964.3|doi:10.1109/SWCT.1964.3]].</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。

[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>Sligochi (2022). BB(16) > Graham's Number. ''(EB/OL)''. Available at: https://www.sligocki.com/2022/07/11/bb-16-graham.html</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>Cats Are Fully (n.d.). Metamath turing machines. ''(EB/OL), Github''. Available at: https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。

据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[BMS]] 的极限。<ref>Morphett, (n.d.). Turing machine simulator. ''(EB/OL)''. Available at: 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>(Anonymous). (n.d.). list27.txt. ''(EB/OL), Github''. Available at: https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。

Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系|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>
事实上，'''我们必须知道，我们必将知道'''。

== 参考资料 ==
<references />{{默认排序:相关问题}}
[[分类:记号]]