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

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

忙碌海狸函数（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-色的。

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

忙碌海狸函数

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

一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为 $B B (n)$ 或者 $Σ (n)$ .^[1]

取值

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

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


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

可得BB(2)=4.

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


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

可得BB(3)=6.

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


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

可得BB(4)=13

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


	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$ ^[6]

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

参考资料

↑ Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
↑ 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).
↑ https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE
↑ https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc

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

[2] 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)

[3] 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)

[4] 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).

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ 第5行： / 第5行： @@
 === 图灵机 ===
 图灵机，是由英国数学家艾伦・麦席森・图灵于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。
-[[文件:5327ce16801ceb4b972b43a8.webp|缩略图|图1]]
-图灵机的结构如图1所示。它由一条无限长的纸带以及一个读头构成。纸带上有无限多个顺次排列的方格，每个方格都具有一个特定的值。读头可以存储图灵机自身的'''状态'''，在纸带上移动，或者是修改纸带中某个方格的值。
+它由一条无限长的纸带以及一个读头构成。纸带上有无限多个顺次排列的方格，每个方格都具有一个特定的值。读头可以存储图灵机自身的'''状态'''，在纸带上移动，或者是修改纸带中某个方格的值。
 在起始时刻，图灵机的纸带上已经预先写好了每个格子的值，然后将图灵机的读头放到某一个给定的格子上，然后，图灵机将根据自身编码的指令集（即图灵程序）进行运动。在每个时刻，图灵机将读取读头对应的格子的值以及自身的状态，然后将这个格子的值改变为某一个值、将图灵机自身的状态改变为某一状态，并将读头移动到某个相邻的位置。特别的，图灵机具有一个特殊的状态，称为'''停机状态'''，我们将之记为H。如果图灵机运行到了停机状态，那么它将停止运动，图灵机的程序结束。
@@ 第40行： / 第40行： @@
 我们定义忙碌海狸函数如下：
-一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为<math>BB(n)</math>或者<math>\Sigma(n)</math>.
+一个能够停机的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>
 == 取值 ==
 对于BB(1),显然，它只有立刻停机一种可能。因此<math>BB(1)=1</math>
-BB(2)所对应的图灵机为：
+BB(2)所对应的图灵机为：<ref>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)</ref>
 {| class="wikitable mw-collapsible mw-collapsed"
 |+
@@ 第59行： / 第59行： @@
 |1LB
 |1RH
-|}
+|}可得BB(2)=4.
-[[文件:Busy-beaver-two-states.webp|缩略图|图2]]
+BB(3)所对应的图灵机是<ref>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)</ref>
-其输出如图2所示。BB(2)=4.
+{| class="wikitable mw-collapsible mw-collapsed"
-BB(3)所对应的图灵机是
-{| class="wikitable"
 |+
 !
@@ 第80行： / 第77行： @@
 |1RB
 |1LA
-|}
+|}可得BB(3)=6.
-[[文件:Busy-beaver-three-states.webp|缩略图|图3]]
+BB(4)所对应的图灵机是<ref>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).</ref>
-其输出如图3所示。BB(3)=6.
+{| class="wikitable mw-collapsible mw-collapsed"
-BB(4)所对应的图灵机是
-{| class="wikitable"
 |+
 !
@@ 第105行： / 第99行： @@
 |0LA
 |}
-其输出如图4所示。BB(4)=13
+可得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>
+{| class="wikitable mw-collapsible mw-collapsed"
+|+
+!
+!A
+!B
+!C
+!D
+!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>https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>
+<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>
+== 参考资料 ==