跳转到导航跳转以搜索停顿的二进制字母图灵机，它在磁带上写入最多的1，仅使用有限的一组状态。
非正式地说，在理论计算机科学中，忙碌的海狸游戏的目标是找到一个给定大小的终止程序，以产生尽可能多的输出。[1]。
更准确地说，忙碌的海狸游戏包括设计一台停顿的二进制字母图灵机，它只使用给定的一组状态，在磁带上写下最多的1。两国博弈的规则如下：
玩家应该构思一个转换表，目标是在磁带上输出最长的1，同时确保机器最终会停机。
第n个忙碌的海狸，BB-n或简称"；忙碌的海狸是一台图灵机，赢得了n个州的忙碌的海狸游戏。也就是说，在所有其他可能的n状态竞争图灵机中，它获得了最多数量的1。例如，BB-2图灵机在6个步骤中实现了4个1。
忙碌的海狸游戏涉及可计算性理论、停顿问题和复杂性理论。这个概念最早是由Tibor Radó在他1962年的论文“关于不可计算函数”中提出的。
Tibor Radóު年的论文中介绍的n状态忙碌海狸游戏(或BB-n游戏)涉及一类图灵机，每个成员都需要满足以下设计规格：
该机器具有n个运行状态加上停止状态，其中n是正整数，并且n个状态中的一个状态被区分为启动状态。(通常，状态由1、2、...、n标记，其中状态1为开始状态，或由A、B、C、...标记，以状态A为开始状态。)
并产生三个输出：要重写当前带单元中的符号的符号(它可以是与被重写的符号相同的符号)，
移动方向(向左或向右；即，向当前单元的左侧或右侧移动到磁带单元)，以及。
同一公式的一个更详细的版本是(符号*方向*(状态+1))(符号*状态)。
转移函数可以被视为5元组的有限表，每个形式。
"；运行"；机器包括在启动状态下启动，当前磁带单元是空白(全0)磁带的任何单元，然后重复转换功能，直到进入停止状态(如果有的话)。如果且仅当机器最终停止工作时，磁带上最后剩余的1的数量才称为机器的分数。
N状态忙碌海狸(BB-n)游戏是一场比赛，目的是寻找这样一台n状态图灵机，它具有可能的最大分数-停机后磁带上的最大数量的1。在所有n状态图灵机中获得最大可能分数的机器被称为n状态忙碌海狸，而分数仅仅是到目前为止达到的最高(可能不是最大的)的机器被称为冠军n状态机器。
Radó要求每台参加比赛的机器都要附上一份声明，说明达到停顿状态所需的确切步数，这样就可以(原则上)通过运行机器达到规定的步数来验证每一项参赛作品的分数。(如果条目仅由机器描述组成，则无法确定验证每个潜在条目的问题，因为它等同于众所周知的停止问题-没有有效的方法来确定任意机器是否最终停止。)。
忙碌的海狸函数量化忙碌的海狸在给定度量上可以达到的最高分数。这是一个不可计算的函数。此外，可以证明忙碌的海狸函数比任何可计算的函数渐近增长得更快。
定义忙碌海狸功能Σ：n→N，使得当在空白磁带上启动时，Σ(N)是上述类型的所有停止的2符号n状态图灵机中可达到的最大分数(最终在磁带上的1的最大数目)。
显然，Σ是一个定义明确的函数：对于每个n，至多有有限个如上所述的n状态图灵机，直到同构，因此至多有限次可能的运行时间。
该无限序列Σ是忙海狸函数，并且σ(M)=Σ(N)(即，达到最大分数)的任何n状态2符号图灵机M被称为忙海狸。注意，对于每个n，存在至少四个n状态忙碌海狸(因为给定任何n状态忙碌海狸，通过仅通过在暂停转换中改变移位方向来获得另一个，通过将所有方向改变移动到它们的相反方向来获得另一个(其中保持中立)，以及通过改变全部交换的忙碌海狸的停止方向来获得最终的忙碌海狸)。
Radó'；1962年的论文证明了如果f：ℕ→ℕ是任何可计算函数，则对所有足够大的n，Σ(N)>；f(N)，因此Σ不是可计算函数。
此外，这意味着无法通过一般算法来判定任意图灵机是否为忙碌的海狸。(这样的算法不可能存在，因为它的存在将允许计算Σ，这被证明是不可能的。具体地说，这样的算法可以用来构建另一个算法，该算法将如下计算Σ：对于任何给定的n，将测试有限多个n状态2符号图灵机中的每一个，直到找到n状态忙碌海狸为止；然后将模拟该忙碌海狸机器以确定其分数，根据定义Σ(N)。)。
尽管Σ(N)是一个不可计算的函数，但有一些较小的n可以获得它的值并证明它们是正确的。不难证明Σ(0)=0，Σ(1)=1，Σ(2)=4，并且更困难的是可以证明Σ(3)=6和Σ(4)=13(OEIS中的序列A028444)。尚未为n>；4的任何实例确定Σ(N)，尽管已经建立了下限(请参阅下面的已知值部分)。
2016年，Adam Yedidia和Scott Aaronson得到了Σ(N)在ZFC中不可证明的最小n的第一个(显式)上界。为此，他们构建了一个7910态[2]图灵机，其行为不能基于集合论的通常公理(具有选择公理的Zermelo-Fraenkel集合论)在合理的一致性假设(静态Ramsey性质)下得到证明。[3][4]这后来减少到1919个状态，消除了对静止Ramsey性质的依赖，[5][6]，后来又减少到748个状态。[7]。
Kolmogorov复杂度的一种变体定义如下[cf.。Boolos，Burgess&Amp；Jeffrey，2007]：数字n的复杂性是BB级图灵机在初始空白磁带上以n个连续1组成的单个块停止所需的最小状态数。Chaitin的不完全性定理的相应变体指出，在给定的自然数公理系统的上下文中，存在一个数k，使得不能证明任何特定的数具有大于k的复杂度，因此不能证明Σ(K)的具体上界(后者是因为n的复杂度大于k&34；如果证明了"；n>；Σ(K)&34；将被证明)。如引用的参考文献中所提到的，对于任何公理系统的普通数学，其为真的最小值k远远小于10↑↑10；因此，在普通数学的上下文中，Σ(10↑↑10)的值和任何上界都不能被证明。(Gödel的第一个不完全性定理由此结果得到说明：在普通数学的公理系统中，有一个形式为"；Σ(10↑↑10)=n"；的真但不可证明的句子，并且有无穷多个形式为"；Σ(10↑↑10)<；n"；的真但不可证明的句子。)
除了函数Σ之外，Radó[1962年]还为BB级图灵机引入了另一个极端函数，最大移位函数S，定义如下：
S(M)=对于En中的任何M，M在停止之前进行的移位次数，
S(N)=max{s(M)|M∈En}=任何停机的n状态2符号图灵机进行的最大移位次数。
因为这些图灵机需要在每个转换或步骤(包括到停止状态的任何转换)中都有一个移位，所以最大移位函数同时是最大步数函数。
Radó证明S不可计算的原因与Σ不可计算的原因相同--它比任何可计算函数增长得都快。他通过指出对于每个n，S(N)≥Σ(N)简单地证明了这一点。每个移位可以在磁带上写入0或1，而Σ计算写入1的移位的子集，即图灵机停止时尚未覆盖的移位；因此，S的增长速度至少与Σ一样快，事实证明，它的增长速度快于任何可计算函数。
Σ和S之间的下列联系被Lin&；Radó[1965年图灵机问题的计算机研究]用来证明Σ(3)=6：对于给定的n，如果S(N)已知，则所有n状态的图灵机(原则上)可以运行最多S(N)步，在这一点上，任何尚未停止的机器将永远不会停止。此时，通过观察磁带上出现最多1的机器(即忙碌的海狸)，可以从它们的磁带中获得Σ(N)的值。对于n=3的情况，Lin&；Radó使用的方法是猜想S(3)=21，然后模拟所有本质上不同的3状态机，最多21步。通过分析在21个步骤内没有停止的机器的行为，他们成功地证明了这些机器都不会停止，从而证明了S(3)=21的猜想，并通过刚才描述的过程确定Σ(3)=6。
与Σ和S有关的不等式包括以下(摘自[Ben-Amram等人，1996年])，这些不等式对所有n个≥[1]都有效：
S(N)≥Σ(N)S(N)≤(2 n−1)Σ(3 n+3)S(N)<；Σ(3 n+6)；{\DisplayStyle{\Begin{Align}S(N)&；\geq\sigma(N)\\S(N)&；\LEQ(2n-1)\Sigma(3n+3)\\S(N)&；<；\Sigma(3n+6)；\end{aligma}
和一个渐近改进的界(来自[Ben-Amram，Petersen，2002年])：存在一个常数c，使得对于所有n-≥~2，
S(N)≤Σ(n+⌈8 nlog2n⌉+c)。{\displaystyle S(N)\leq\Sigma\Left(n+\Left\lceil{\frac{8n}{\log_{2}n}\right\rceil+c\right)。}。
有S(N)接近Σ(N)的平方的趋势，实际上许多机器给出的S(N)小于Σ2(N)。
Σ(N)和S(N)的函数值仅在n=5的情况下是精确已知的。[4]。
目前的5个州的忙碌海狸冠军生产4098个1，使用47 176 870个步骤(由Heiner Maxen和Jürgen Buntrock在1989年发现)，但仍然有18或19台机器(可能在10岁以下，见下文)具有非常规行为，据信永远不会停止，但尚未被证明可以无限运行。斯凯莱特列出了42或43台未经验证的机器，但有24台已经经过验证。[8]其余的机器被模拟为818亿步，但没有一台停止。丹尼尔·布里格斯还证明了一些机器。[9]另一消息来源称，仍有98台机器未经验证。有一项对顽固派的分析[10]。因此，Σ(5)=4098和S(5)=47176870的可能性很大(且几乎已被证实)，但这一点仍未得到证实，(截至2018年)是否还有抵抗者也是未知的。目前，这位创纪录的6州冠军产生了超过3.515×1018267个1s(确切地说是(25*4 30341+23)/9)，使用了超过7.412×1036534个1s(由Pavel KroPitz在2010年发现)。如上所述，这些是2符号图灵机。
对6状态机的简单扩展将产生一个7状态机，它将向磁带写入超过10个10 10 10 18 705 3531，但毫无疑问还有更繁忙的7状态机。然而，其他忙碌的海狸猎人有不同的机器。
米尔顿·格林(Milton Green)在他1964年的论文“Rado‘s Sigma Function for Binary Turing Machines”中，构造了一组图灵机，证明了。
Σ(2 K)>；3↑k−2 3>；A(k−2，k−2)，{\≥Style\sigma(2k)>；3\uparrow^{k-2}3>；A(k-2，k-2)\qquad{\mbox{For}}k\geq 2，}
Σ(10)>；3↑↑↑3=3↑↑3 33=3 33.。。。3{\displaystyle\sigma(10)>；3\uparrow\uparrow\uparrow 3=3\uparrow\uparrow 3^{3^{3}}=3^{3^{.^{3}。
Σ(12)>；3↑↑↑↑3=g 1，{\DisplayStyle\sigma(12)>；3\uparrow\uparrow 3=g_{1}，}。
其中数字g1是定义格雷厄姆的数字的序列中的巨大起始值。
1964年，米尔顿·格林在1964年IEEE开关电路理论和逻辑设计研讨会上发表了忙碌海狸函数的一个下限。海纳·马克思和于尔根·邦特洛克(Jürgen Buntrock)将其描述为一个非平凡(不是原始递归)的下界。当n=8时，Σ(8)≥为3×(7×3 92-1)/2≈为8.248×1044。
Σ(2 k+1)>；3↑k−2 31>；A(k−2，k−2)，{\≥Style\sigma(2k+1)>；3\uparrow^{k-2}31>；A(k-2，k-2)\qquad{\mbox{for}}k\geq 2，}。
相比之下，Σ(6)的最佳电流(截至2018年)下限为1018267，大于格林公式给出的下限33=27(相比之下微不足道)。事实上，它远远大于下界：3↑↑3=3 33=7625597484987，这是格林关于Σ(8)的第一个下界，也远远大于第二个下界：3*(7*3 92-1)/2。
同样，Σ(7)比目前常见的下限331兆(接近618万亿)要大得多，所以第二个下限也是非常非常弱的。
假设S(N)是一个可计算函数，设evals表示一个TM，计算S(N)。给定具有n个1的磁带，它将在磁带上生成S(N)个1，然后停止。让Clean表示图灵机清洁最初写入磁带上的1序列。设DOUBLE表示一个计算函数n+n的图灵机，给定一个有n个1的磁带，它将在磁带上产生2个n个1，然后停止。让我们创建组合Double|evals|Clean，并设n 0为该机器的状态数。让create_n0表示图灵机在初始空白磁带上创建n0 1。该机器可以以平凡的方式构造为具有n0个状态(状态i写入1，向右移动磁头，并切换到状态i+1，除了停止的状态n0)。设N表示和n0+n0。
让Bad表示组合create_n0|Double|evals|Clean。请注意，这台机器有N个状态。从最初空白的磁带开始，它首先创建n个0 1的序列，然后将其加倍，产生N个1的序列。然后BADS将在磁带上产生S(N)1，最后它将清除所有1，然后停止。但清洗阶段将至少持续S(N)步，因此BADS的工作时间严格大于S(N)，这与函数S(N)的定义相矛盾。
可以用类似的方法证明Σ(N)的不可计算性。在上面的证明中，必须用EvalΣ和Clean with Increment交换机器值-一个简单的TM，搜索磁带上的第一个0并将其替换为1。
S(N)的不可计算性也可以参考空白磁带停止问题来确定。空白磁带停止问题是决定任何图灵机在空磁带上启动时是否停止的问题。空白磁带停顿问题等同于标准停带问题，因此也是不可计算的。如果S(N)是可计算的，那么我们可以简单地通过运行任意给定的具有n个状态的图灵机S(N)步来解决空白磁带停止问题；如果它仍然没有停止，那么它永远不会停止。因此，由于空白磁带停止问题是不可计算的，因此得出S(N)也一定是不可计算的。
对于任何计算模型，都存在忙碌的海狸的简单类比。例如，对具有n个状态和m个符号的图灵机的推广定义了以下广义忙碌海狸函数：
Σ(n，m)：停机前在初始空白磁带上启动的n状态m符号机可打印的最大非零数，以及。
S(n，m)：在停机前，在初始空白磁带上启动的n状态m符号机所采取的最大步数。
例如，到目前为止发现的运行时间最长的3状态3符号机在停止之前运行119 112 334 170 342 540步。运行时间最长的6状态2符号机，它具有在每一步反转磁带值的附加特性，在47 339970步之后产生61471秒。因此，S rtm(6)≥47339970和Σrtm(6)≥6147。
可以通过扩展到多于一个维度来进一步概括忙碌的海狸功能。
同样，对于给定数量的指令，我们可以将寄存器机器的Σ函数的模拟定义为停机时可以出现在任何寄存器中的最大数量。
下表列出了广义忙碌海狸问题S(n，m)和Σ(n，m)的精确值和一些已知下界。注意：列出为"；？？"；的条目从下至左和从上至左的所有条目中的最大值为边界。这些机器要么没有经过调查，要么后来被一台较小的机器超越了。
达到这些值的图灵机可以在帕斯卡尔·米歇尔的网页上找到。这些网站中的每一个还包含对图灵机的一些分析，以及对确切价值的证明的引用。
除了提出一个相当具有挑战性的数学游戏，忙碌的海狸函数还提供了一种解决纯数学问题的全新方法。对于足够大的n，给定S(N)的值，数学中的许多公开问题在理论上可以系统地解决，但在实践中却不能。
考虑任何可以通过反例在可计数的案例中反证的猜想(例如，哥德巴赫猜想)。写一个计算机程序，按顺序测试这个猜想的增值性。在哥德巴赫猜想的情况下，我们会按顺序考虑每个偶数≥4，并检验它是否是两个素数的和。假设此程序在n状态图灵机上进行模拟。如果它找到一个反例(在我们的示例中，偶数≥4不是2个素数的和)，它会暂停并通知我们。然而，如果猜测是真的，那么我们的程序将永远不会停止。(此程序只有在找到反例时才会停止。)。
现在，这个程序是由一个n状态的图灵机模拟的，所以如果我们知道S(N)，我们可以(在有限的时间内)决定它是否会停止，只需简单地运行机器那么多步。如果在S(N)步之后，机器没有停止，我们知道它永远不会停止，因此对给定的猜想没有反例(即没有不是两个素数之和的偶数)。这将证明这个猜想是正确的。
因此，S(N)的特定值(或上界)可以用来系统地解决数学中的许多公开问题(在理论上)。然而，目前关于忙碌的海狸问题的结果表明，这是不切实际的，原因有两个：
要证明忙碌的海狸函数(和m)的值是极其困难的
.