|
|
本帖最后由 hbghlyj 于 2023-7-11 15:31 编辑 zh.m.wikipedia.org/zh-hans/忙碌的海狸
忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1.
包含两个状态的忙碌的海狸游戏有下面两条规则：
1. 该图灵机包括除终止态以外的两个状态
2. 纸带初始值都是0
玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。
能赢得n个状态的忙碌的海狸游戏的图灵机，称为第$n$个忙碌的海狸，或者用$BB\text-n$表示($BB$是英文忙碌的海狸的缩写)。$BB\text-n$是在所有n个状态的图灵机里面，可以输出最多的1的。比如$BB\text-2$，可能通过6次状态转换输出4个1。
忙碌的海狸游戏是由匈牙利的数学家Tibor Radó在1962年发表的论文《On Non-Computable Functions》中提出的。
1962-rado.pdf
(295.94 KB, 下载次数: 0)
无限旅馆的机器人
假设有一排无限房间的旅馆，每个房间里面都装了一盏灯和一个开关。最初，所有房间的灯都是关的（状态0）。一个机器人管家从其中某一个房间开始工作。进入房间后，它的行为只能是选择开灯或关灯，然后移到相邻的左边或者右边房间去。
这个机器人可以处于若干个预先设定的状态中。在不同的状态下，它会根据房间灯的开关情况，选择不同的行为和下一步的状态。
一个状态的机器人
在“工作”态下：
如果房间灯是关的，开灯，移动到左边的房间并转换到“停止”态
如果房间灯是开的，关灯，移动到左边的房间并转换到“停止”态
在“停止”态下（这个游戏必须有一个停止态，不计算在机器人状态中）：机器人停止，游戏结束。
游戏开始后，这个“工作”态机器人进入某个房间后，开一盏灯，然后移到左边的房间并转换到“停止”态，游戏结束。我们可以验证，无论你如何设计机器人的行为(64种可能)，在只有一种状态的约束下，机器人最多只能打开一盏灯，所以${\displaystyle \Sigma (1)=1}$。
两个状态的机器人
在“惊恐”态下：
如果房间灯是关的，开灯并移动到左边的房间去
如果房间灯是开的，恢复到“正常”态
在“正常”态下：
如果房间灯是开的，关灯并移动到左边的房间去
其余情况，转变到“惊恐”态
在“停止”态下（这个游戏必须有一个停止态，不计算在两种状态中）：机器人停止，游戏结束。
对于以上两种状态的机器人，如果它初始态是“惊恐”，从它进入某一个房间开放，它便会打开房间的灯然后移到左边的房间。然后继续开灯，向左移，无限循环下去。这样的状态设定是不符合忙碌的海狸必须可以终止的条件。同理，如果它的初始态是“正常”，它也会无限向左移，并不属于忙碌的海狸。
下面我们看另外一种两个状态的机器人。
在“1”态下：
如果房间灯是关的，开灯，移动到右边的房间，并转变到“2”态
如果房间灯是开的，保持，移动到左边的房间，并转变到“2”态
在“2”态下：
如果房间灯是关的，开灯，移动到左边的房间，并转变到“1”态
如果房间灯是开的，保持，移动到左边的房间，并转变到“H”态
在“H”态下：机器人停止，游戏结束。
这样的状态“1”机器人，从某个房间开始，可以进行6次移动，最终打开四盏灯（左边2个房间，开始的房间，和右边的一个房间），回到最左边的房间并停止游戏。2个状态的机器人，全部有${\displaystyle (2\times 2\times 3)^{2\times 2}=20736}$种行为设计，其实最多开灯的设计是4盏，所以${\displaystyle \Sigma (2)=4}$。
3个状态的机器人，可以通过14次移动，最多打开6盏灯${\displaystyle \Sigma (3)=6}$。
4个状态的机器人，可以通过107次移动，最多打开13盏灯，${\displaystyle \Sigma (4)=13}$。
4个更多状态的机器人，目前还不能计算出忙碌的海狸的函数值，比如目前我们猜测${\displaystyle \Sigma (5)\geqslant 4098}$，但还不能确认。
忙碌的海狸函数
忙碌的海狸函数，又称为BB函数，或者Radó Sigma函数，记做${\displaystyle \Sigma (n)}$或者BB(n),是$n$个状态的忙碌的海狸图灵记的最大输出。这一个增长特别快的函数，是一个非常著名的不可计算函数。Radó证明了这个函数最终会超过全部的可计算函数。
${\displaystyle \Sigma (n)}$还可以定义为集合${\displaystyle T=\{n_{1},n_{2},\cdots ,n_{k}\}}$中最大的数，这个集合包括了$n$个状态的2色图灵机全部的输出。集合$T$的大小不超过${\displaystyle (4n+4)^{2n}}$（这是n个状态的全部图灵机数量）。
更普遍的，${\displaystyle \Sigma (n,m)}$表示$n$个状态，$m$个颜色的忙碌的海狸图灵机。
oeis.org/A060843
Busy Beaver problem: a(n) = maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting.
1, 6, 21, 107 |
|
