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

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

== 定义 ==

=== 图灵机 ===
图灵机，是由英国数学家艾伦・麦席森・图灵于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。
[[文件:5327ce16801ceb4b972b43a8.webp|缩略图|图1]]
图灵机的结构如图1所示。它由一条无限长的纸带以及一个读头构成。纸带上有无限多个顺次排列的方格，每个方格都具有一个特定的值。读头可以存储图灵机自身的'''状态'''，在纸带上移动，或者是修改纸带中某个方格的值。

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

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

作为一个例子，我们给出一个图灵机的程序，它纸带上的取值是0或者1，它有两个状态A和B。
{| class="wikitable"
|+图灵机
!
!A
!B
|-
|0
|1RB
|1LA
|-
|1
|1LB
|1RB
|}
例如，左上角的1RB代表当这个图灵机在状态A之下读取到了格子上是0，那么它把格子的值改写为1，向右移动一格，并且把图灵机的状态变为B。其余指令的含义是类似的，这里不再赘述。下面我们在一个所有格子全为0的纸带上运行这个图灵机，它的初始状态是A：

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

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

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

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

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

一个能够停机的2色，n状态图灵机，从全0的纸带开始，所能够扫过的最大格子数定义为<math>BB(n)</math>或者<math>\Sigma(n)</math>.

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

BB(2)所对应的图灵机为：
{| class="wikitable mw-collapsible mw-collapsed"
|+
!
!A
!B
|-
|0
|1RB
|1LA
|-
|1
|1LB
|1RH
|}
[[文件:Busy-beaver-two-states.webp|缩略图|图2]]
其输出如图2所示。BB(2)=4.

BB(3)所对应的图灵机是
{| class="wikitable"
|+
!
!A
!B
!C
|-
|0
|1RB
|0RC
|1LC
|-
|1
|1RH
|1RB
|1LA
|}
[[文件:Busy-beaver-three-states.webp|缩略图|图3]]
其输出如图3所示。BB(3)=6.

BB(4)所对应的图灵机是
{| class="wikitable"
|+
!
!A
!B
!C
!D
|-
|0
|1RB
|1LA
|1RH
|1RD
|-
|1
|1LB
|0LC
|1LD
|0LA
|}
其输出如图4所示。BB(4)=13