此條目没有列出任何参考或来源。(2020年7月23日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

在计算机科学中，忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1.

包含两个状态的忙碌的海狸游戏有下面两条规则：

1. 该图灵机包括除终止态以外的两个状态
2. 纸带初始值都是0

玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。

能赢得n个状态的忙碌的海狸游戏的图灵机，称为第n个忙碌的海狸，或者用BB-n表示(BB是英文忙碌的海狸的缩写)。BB-n，是在所有n个状态的图灵机里面，可以输出最多的1的。比如BB-2，可能通过6次状态转换输出4个1。

忙碌的海狸游戏是由匈牙利数学家拉多·蒂博爾在1962年发表的论文《On Non-Computable Functions》中提出的。

假设有一排无限房间的旅馆，每个房间里面都装了一盏灯和一个开关。最初，所有房间的灯都是关的（状态0）。一个机器人管家从其中某一个房间开始工作。进入房间后，它的行为只能是选择开灯或关灯，然后移到相邻的左边或者右边房间去。

这个机器人可以处于若干个预先设定的状态中。在不同的状态下，它会根据房间灯的开关情况，选择不同的行为和下一步的状态。

• 在“工作”态下：

1. 如果房间灯是关的，开灯，移动到左边的房间并转换到“停止”态
2. 如果房间灯是开的，关灯，移动到左边的房间并转换到“停止”态

• 在“停止”态下（这个游戏必须有一个停止态，不计算在机器人状态中）：机器人停止，游戏结束。

游戏开始后，这个“工作”态机器人进入某个房间后，开一盏灯，然后移到左边的房间并转换到“停止”态，游戏结束。我们可以验证，无论你如何设计机器人的行为(64种可能)，在只有一种状态的约束下，机器人最多只能打开一盏灯，所以${\displaystyle \mathrm{\Sigma }(1)=1}$。

• 在“惊恐”态下：

1. 如果房间灯是关的，开灯并移动到左边的房间去
2. 如果房间灯是开的，恢复到“正常”态

• 在“正常”态下：

1. 如果房间灯是开的，关灯并移动到左边的房间去
2. 其余情况，转变到“惊恐”态

• 在“停止”态下（这个游戏必须有一个停止态，不计算在两种状态中）：机器人停止，游戏结束。

对于以上两种状态的机器人，如果它初始态是“惊恐”，从它进入某一个房间开放，它便会打开房间的灯然后移到左边的房间。然后继续开灯，向左移，无限循环下去。这样的状态设定是不符合忙碌的海狸必须可以终止的条件。同理，如果它的初始态是“正常”，它也会无限向左移，并不属于忙碌的海狸。

下面我们看另外一种两个状态的机器人。

• 在“1”态下：

1. 如果房间灯是关的，开灯，移动到右边的房间，并转变到“2”态
2. 如果房间灯是开的，保持，移动到左边的房间，并转变到“2”态

• 在“2”态下：

1. 如果房间灯是关的，开灯，移动到左边的房间，并转变到“1”态
2. 如果房间灯是开的，保持，移动到左边的房间，并转变到“H”态

• 在“H”态下：机器人停止，游戏结束。

这样的状态“1”机器人，从某个房间开始，可以进行6次移动，最终打开四盏灯（左边2个房间，开始的房间，和右边的一个房间），回到最左邊的房间并停止游戏。2个状态的机器人，全部有${\displaystyle (2\times 2\times 3{)}^{2\times 2}=20736}$种行为设计，其实最多开灯的设计是4盏，所以${\displaystyle \mathrm{\Sigma }(2)=4}$。

3个状态的机器人，可以通过14次移动，最多打开6盏灯${\displaystyle \mathrm{\Sigma }(3)=6}$。

4个状态的机器人，可以通过107次移动，最多打开13盏灯，${\displaystyle \mathrm{\Sigma }(4)=13}$。

4个更多状态的机器人，目前还不能计算出忙碌的海狸的函数值，比如目前我们猜测${\displaystyle \mathrm{\Sigma }(5)⩾4098}$，但还不能确认。

忙碌的海狸函数，又称为BB函数，或者Radó Sigma函数，记做${\displaystyle \mathrm{\Sigma }(n)}$或者BB(n),是n个状态的忙碌的海狸图灵机的最大输出。这一个增长特别快的函数，是一个非常著名的不可计算函数。Radó证明了这个函数最终会超过全部的可计算函数。

${\displaystyle \mathrm{\Sigma }(n)}$还可以定义为集合${\displaystyle T=\{n_1,n_2,\cdots ,n_k\}}$中最大的数，这个集合包括了n个状态的2色图灵机全部的输出。集合${\displaystyle T}$的大小不超过${\displaystyle (4n+4{)}^{2n}}$（这是n个状态的全部图灵机数量）。

更普遍的，${\displaystyle \mathrm{\Sigma }(n,m)}$表示n个状态，m个颜色的忙碌的海狸图灵机。

Values of S(n,m)

n m	2-state	3-state	4-state	5-state	6-state	7-state
2-symbol	6	21	107	7007471768700000000♠47176870	>9000000000000000000♠7.4×1036534	> 102*1010107007187053530000000♠18705353
3-symbol	38	≥7017119112334170342♠119112334170342540	>9000000000000000000♠1.0×1014072	???	???	???
4-symbol	≥7006393296400000000♠3932964	>9000000000000000000♠5.2×1013036	???	???	???	???
5-symbol	>9000000000000000000♠1.9×10704	???	???	???	???	???
6-symbol	>9000000000000000000♠2.4×109866	???	???	???	???	???

Values of Σ(n,m)

n m	2-state	3-state	4-state	5-state	6-state	7-state
2-symbol	4	6	13	7003409800000000000♠4098?	>9000000000000000000♠3.5×1018267	> 101010107007187053530000000♠18705353
3-symbol	9	≥7008374676383000000♠374676383	>9000000000000000000♠1.3×107036	???	???	???
4-symbol	≥7003205000000000000♠2050	>9000000000000000000♠3.7×106518	???	???	???	???
5-symbol	>9000000000000000000♠1.7×10352	???	???	???	???	???
6-symbol	>9000000000000000000♠1.9×104933	???	???	???	???	???

在下面的表格中，列代表了当前的状态，行代表了当前从纸带读取的标记。表格中的每一项有三个字母，分别表示向纸带写的标记，移动的方向和下一步的新的状态。终止态用H代表。

每个图灵机都从状态A开始，纸带无限长且初始值都是0。

结果指示: (启始位置1, 结束位置1)

1-状态, 2-标记

	A
0	1RH
1	(not used)

结果: 0 010 0 (1 步, 一个 "1" )

2-状态, 2-标记

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

结果: 0 0 1 11 1 0 0 (6 步, 四个 "1")

3-状态, 2-标记

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

结果: 0 0 11 11 1 1 0 0 (14 步, 六个 "1").

4-状态, 2-标记

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

结果: 0 0 10 1 1 1 1 1 1 1 11 1 1 1 0 0 (107 步, 十三个 "1",见图)

5-状态, 2-标记 (目前最大估计)

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

结果: 4098 个"1"中间隔 8191 个"0"。 47,176,870 步。

6-状态, 2-标记 （目前最大估计）

	A	B	C	D	E	F
0	1RB	1RC	1LC	0LE	1LF	0RC
1	0LD	0RF	1LA	1RH	0RB	0RE

结果: 10 1 1 1 ... 1 1 1 ("10" 后面接着超过10↑↑15个"1")。超过10↑↑15 步。其中10↑↑15=10^10..10是以10为底数的15层迭代幂次。

• 拉約數
• 葛立恆數

• 递归论
• 計算理論
• 大整数
• 动物隐喻

• 自2020年7月缺少来源的条目
• 含有英語的條目