忙碌海狸函数

忙碌海狸函数（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的纸带开始，所能够扫过的最大格子数定义为$BB(n)$或者$\mathrm{\Sigma }(n)$.

取值

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

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

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

可得BB(2)=4.

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

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

可得BB(3)=6.

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

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

可得BB(4)=13

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

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

可得BB(5)=4098

对于更之后的BB函数，我们还未计算出精确值。我们有

$BB(6)\ge 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$

$BB(7)\ge 2{\uparrow }^{11}2{\uparrow }^{11}3$