忙碌的海狸

在理论计算机科学中，忙碌的海狸游戏旨在找到一个给定大小的终止程序，以产生尽可能多的输出。 由于无限循环产生无限输出的程序很容易想到，因此此类程序被排除在游戏之外。

更准确地说，忙碌的海狸游戏包括设计一个带有字母表 {0,1} 的停机图灵机，它只使用一组给定的状态在磁带上写入最多的 1。 2态博弈的规则如下：

• 除了停止状态之外，机器还必须有两个状态，并且
• 磁带最初只包含 0。

玩家应该设想一个转换表，目标是磁带上最长的 1 输出，同时确保机器最终会停止。

第 n 个忙碌的海狸，BB-n 或简单的忙碌的海狸是赢得 n 状态忙碌海狸游戏的图灵机。 也就是说，它在所有其他可能的 n 态竞争图灵机中获得最多的 1。 例如，BB-2 图灵机在六个步骤中实现了四个 1。

确定任意图灵机是否是忙碌的海狸是不可确定的。 这对可计算性理论、停机问题和复杂性理论都有影响。 这个概念首先由 Tibor Radó 在他 1962 年的论文 On Non-Computable Functions 中提出。

在 Tibor Radó 1962 年的论文中介绍的 n-state busy beaver game（或 BB-n game）涉及一类图灵机，其中每个成员都需要满足以下设计规范：

• 机器有n个运行状态加上一个Halt状态，其中n是一个正整数，n个状态中的一个被区分为起始状态。 （通常，状态标记为 1、2、...、n，以状态 1 为起始状态，或标记为 A、B、C、...，以状态 A 为起始状态。）</li >
• 该机器使用单个双向无限（或无界）磁带。
• 磁带字母表为{0, 1}，其中0为空白符号。
• 机器的转换函数有两个输入：

• 当前的非暂停状态，
• 当前磁带单元格中的符号，

并产生三个输出：

• 用于覆盖当前磁带单元中符号的符号（它可能与被覆盖的符号相同），
• 移动方向（向左或向右；即，将磁带单元格移动到当前单元格左侧或右侧的一个位置），以及
• 要转换到的状态（可能是暂停状态）。

因此有 (4n + 4)2n 个 n 状态图灵机满足这个定义，因为公式的一般形式是 (symbols × directions × (states + 1))(symbols × states)。转换函数可以看作是 五元组的有限表，每个形式（当前状态，当前符号，要写入的符号，移位方向，下一状态）。

运行机器包括从起始状态开始，当前磁带单元是空白（全 0）磁带的任何单元，然后迭代转换函数直到进入暂停状态（如果有的话）。 当且仅当机器最终停止运行时，最后留在磁带上的 1 的数量称为机器的分数。

n-state busy beaver (BB-n) 游戏是一场比赛，目的是寻找这样一个 n-state 图灵机，其得分最高——停止后磁带上 1 的数量最多。 在所有 n 状态图灵机中获得xxx可能得分的机器称为 n 状态忙碌海狸，而得分仅为迄今为止最高（可能不是xxx可能）的机器称为冠军 n 状态 机器。

Radó 要求每台参加比赛的机器都附有一份声明，说明达到暂停状态所需的确切步数，从而允许（原则上）通过运行指定数量的机器来验证每个条目的分数 步骤。 （如果条目只包含机器描述，那么验证每个潜在条目的问题是不可判定的，因为它等同于众所周知的停机问题——没有有效的方法来确定任意一台机器最终是否停机。）

busy beaver 函数量化 Busy Beaver 在给定度量上可获得的xxx分数。 这是一个不可计算的函数。 此外，可以证明繁忙的海狸函数比任何可计算函数渐进地增长得更快。

繁忙的海狸函数 Σ : N → N {\displaystyle \Sigma :\mathbb {N} \to \mathbb {N} } 被定义为使得 Σ(n) 是可达到的xxx分数（ 当在空白磁带上启动时，上述类型的所有停止的 2 符号 n 态图灵机中最终出现在磁带上的xxx 1s 数。