很难找到一款游戏，既有《黑暗之魂》的难度，又兼具康威《生命游戏》的优雅。在 1962 年的一篇论文中，匈牙利数学家蒂博尔·拉多提出了这样一款游戏，他称之为忙碌的海狸游戏 (BBG)。
玩 BBG 就是创建一个程序，在机器磁带上写入 1，磁带单元最初保存 0；1 不需要是连续的，但程序必须停止计数 1。获胜程序在停止后磁带上具有最多的 1。
我将从机器概述、其编程语言和游戏的约束开始。
BBG 机器、语言和游戏约束
想象一下一个抽象的计算机器（实际上是一台图灵机），具有以下特征
- 一个双字符字母表。一般来说，任何两个字符都可以用于图灵机；按照惯例，BBG 使用 0 和 1。
- 水平排列的磁带单元。每个单元保存来自字母表的单个字符。磁带初始化为 0，这被视为空白磁带。图灵机的磁带必须在至少一个方向（通常是右侧）上是无界的，这在计算上等同于在两个方向上都是无界的磁带。同样按照惯例，BBG 使用在两个方向上都是无界的磁带
+-+-+-+-+-+ ...|0|0|0|0|0|... +-+-+-+-+-+磁带是机器的内存。
- 一个读写标记，用于标识当前内存单元。在计算的每个步骤中，机器读取然后覆盖当前单元的内容。机器可以用 1 替换 0，用 0 替换 1，或者用相同的字符替换任一字符。单元格下方的插入符号 ^ 表示标记
+-+-+-+-+-+ ...|0|0|0|0|0|... +-+-+-+-+-+ ^标记（此处在中间单元格下方）充当机器内存的索引。图灵机只有线性访问而不是随机访问内存单元，因为它每次执行指令仅移动一个单元，向左或向右。
BBG 程序，就像任何图灵程序一样，由诸如 a0b1L 之类的指令组成，这些指令因其部分数量而被称为五元组；在 BBG 中，每个部分有一个字符。五元组的前两个字符（在本例中为 a0）表示捕获计算两个方面的条件
- 计算的当前状态，在 a0b1L 示例中为 a；BBG 使用单个字母（在我的示例中为小写字母）来标识状态
- 当前标记单元格的内容：0 或 1
条件 a0 表示“在状态 a 扫描 0”，而 h1 表示“在状态 h 扫描 1”。
五元组中的最后三个字符指定在满足条件时要采取的动作。
以下是两个示例（## 引入我的评论）
a0b1R ## in state a scanning a 0: transition to state b, write a 1, and move one cell right
p1p1L ## in state p scanning a 1: stay in state p, write a 1, and move one cell left五元组可以可视化为规则，箭头将条件与动作分开
a0-->b1R如果条件 a0 满足，则发生动作 b1R。按照惯例，a 是起始状态，因此 a0 是起始条件。前向链接规则系统（如 OPS5）使用类似的控制流机制。
总之，BBG 程序中的五元组可以以任何顺序出现，因为条件匹配决定了接下来执行哪个指令。程序中没有两个五元组应该具有相同的条件。
停机问题
BBC 程序执行直到达到停机状态——一个在任何指令的匹配条件中都不会出现的状态。考虑以下程序，它是具有两个非停机状态 a 和 b 的程序的 BBG 获胜者
# bb2 winner
a0b1R ## a0-->b1R
a1b1L ## a1-->b1L
b0a1L ## b0-->a1L
b1h1R ## b1-->b1h1R (halt state)最后一个指令 b1h1R 在动作中包含传统的停机状态 h。（可以有多个停机状态，但一个就足够了。）如果条件 b1 满足，则当指令 b1h1R 执行时，h 成为新状态。但是，程序中没有指令的条件以 h 开头，这意味着机器在状态 h 中停止。达到停机状态 h 表示程序正常终止。
对于 BBG，就像一般的图灵计算一样，程序必须停止才能完成计算。例如，此指令将在最初空白的磁带上向右无限写入 1
a0a1R ## "infinitely touring" instruction on a blank tape在状态 a 中扫描 0，机器保持在状态 a，用 1 覆盖 0，并向右移动到另一个 0；因此，指令 a0a1R 再次执行。程序中执行此指令（右侧只有 0）将永远不会停止，因此不能作为 BBG 获胜者。
在计算中，传奇般的不可解问题之一是图灵机在给定数据输入上执行给定程序时是否会停止——停机问题。因此，无法知道给定的 BBG 程序是否会停止。我的模拟器（如下介绍）在执行一百万条指令后怀疑“无限巡回”，因此退出。
从 BBG 到 BBG-N
BBG 涵盖了一系列无限大的游戏，每个游戏都有一个数字，用于标识游戏程序可以使用多少个非停机状态。例如，前面显示的示例程序是 BBG-2 游戏的获胜者，因为该程序仅限于两个非停机状态 a 和 b。（BBG-2 获胜者在最初的空白磁带上产生四个 1。）BBG-3 游戏使用三个非停机状态，而 BBG-744 游戏使用 744 个非停机状态。
总之，BBG-N 获胜者在给定 N 个非停机状态并从空白磁带开始的情况下，产生最多的 1。获胜者必须停止。证明竞争者赢得 BBG-N 游戏并非易事。目前，BBG-1 到 BBG-4 游戏已有经过验证的获胜者，但非停机状态超过四个的游戏则没有。例如，BBG-5 游戏只有一个最佳竞争者。在模拟器上运行一些 BBG 获胜者和 BBG-5 最佳竞争者应该详细说明计算，并强调获胜和竞争程序的巧妙之处。
模拟器上的 BBG-N 示例
我将从微不足道的 BBG-1 游戏的获胜者开始
# bb1 winner
a0h1R ## a is the single non-halting state这是模拟器的磁带开始时的样子，计算从起始状态 a 开始扫描 0
Current state: a
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^程序的单个指令转换到停机状态 h，写入 1，并将单元格向右移动一位
Current state: h
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^因此，获胜者在一个步骤中使用一个非停机状态产生一个 1。没有 BBG-1 程序可以做得更好。等效的 BBG-1 程序可能会在写入 1 后向左而不是向右移动，但一个 1 的获胜总数将保持不变。
更有趣的 BBG-2 游戏的获胜者是这个程序（如前所示），它有两个非停机状态 a 和 b
# bb2 winner
a0b1R ## a0-->b1R
a1b1L ## a1-->b1L
b0a1L ## b0-->a1L
b1h1R ## b1-->h1R (halt state)该程序在六个步骤中产生四个 1
Current state: h
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^让我们详细检查 BBG-3 获胜者
# bb3 winner
a0b1R
a1h1R # (halt state)
b0c0R
b1b1R
c0c1L
c1a1L该程序在 14 个步骤中产生六个 1，并具有三个非停机状态：a、b 和 c。来自模拟器的跟踪阐明了计算的工作原理，特别是它如何循环。
像往常一样，磁带最初是空白的。标记位于中间，机器处于起始状态 a 并扫描 0。条件 a0 匹配的指令是第一个，a0b1R。此指令转换到状态 b，写入 1，并将单元格向右移动一位
Current state: b
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^现在的条件是 b0，它标识指令 b0c0R。因此，机器转换到状态 c，写入 0，并将单元格向右移动一位
Current state: c
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^新条件是 c0，c0c1L 作为匹配指令。因此，机器用 1 覆盖当前扫描的 0，保持状态 c，并将单元格向左移动一位
Current state: c
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^条件保持 c0，匹配指令保持 c0c1L；因此，动作在另外两个之间写入另一个 1。状态保持不变，但向左移动将标记放在 1 而不是 0 上。因此，条件变为 c1，匹配指令变为 c1a1L。此指令的动作将标记移动到最左边 1 的左侧紧邻的 0 单元格，并将 a 作为新状态
Current state: a
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^现在条件是 a0，就像计算开始时一样——程序实际上是在循环。完整指令是 a0b1R，它将机器转换为状态 b，在其他三个的左侧写入第四个 1，然后向右移动。机器通过指令 b1b1R 不断向右移动（并用 1 覆盖 1），直到遇到右侧的第一个 0
Current state: b
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^在状态 b 中扫描 0，机器再次执行指令 b0c0R，从而转换到状态 c，用 0 覆盖 0，并向右移动到另一个空白单元格
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^在状态 c 中扫描 0，机器现在连续执行指令 c0c1L 两次，以生成具有六个连续 1 的磁带。此外，机器已转换为状态 a
Current state: a
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^此时，匹配指令 a1h1R 将机器转换为停机状态 h，并将单元格向右移动一位。最终磁带配置因此为
Current state: h
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^BBG-3 获胜者在 14 个步骤中产生六个 1。
我们如何确定这些获胜者名副其实？有严格的数学证明表明，获胜的 BBG-1、BBG-2、BBG-3 和 BBG-4 程序是无法超越的。BBG 的创建者曾经认为不可能证明 BBG-4 的获胜者，但最终，BBG-4 获胜者的证明。这是经过验证的 BBG-4 获胜者
# bb4 winner
a0b1R
a1b1L
b0a1L
b1c0L
c0h1R # (halt state)
c1d1L
d0d1R
d1a0R该程序需要 107 个步骤来产生 13 个 1，这些 1 不是连续的
Current state: h
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...|0|0|0|0|0|1|0|1|1|1|1|1|1|1|1|1|1|1|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
^对于 BBG-5 及更高版本的游戏，存在最佳竞争者，而不是经过验证的获胜者。任何能够证明 BBG-5 获胜者的人都将获得长久的声誉（但可能不是财富）。作为参考，这是 BBG-5 的最佳竞争者
# bb5 best contender
a0b1R
a1c1L
b0c1R
b1b1R
c0d1R
c1e0L
d0a1L
d1d1L
e0h1R # (halt state)
e1a0L如下所示，该程序在惊人的 47,176,870 个步骤中生成 4,098 个非连续的 1，这令人震惊地提醒人们 BBG-N 游戏对于 N>4 来说有多么困难。BBG-5 是否有可能有更好的竞争者，甚至证明该程序赢得 BBG-5？迄今为止，这些问题仍然悬而未决，专家们预计它们将继续如此。
运行模拟器
图灵程序（用 C 语言编写）通过通用性来模拟单磁带通用图灵机 (UTM)：模拟器可以玩 BBG 游戏，也可以执行数学运算，例如对以一元表示的值进行乘法和求幂，给定适当的程序作为输入。UTM 模拟器呈现磁带，就好像它在两个方向上都是无界的一样。当然，任何 UTM 模拟器不可避免的缺点是磁带大小有限；抽象的 UTM 具有无界内存，这是一个模拟器无法捕获的神奇功能。
模拟器以及迄今为止讨论的 BBG 程序可从我的网站获得。作为参考，这是模拟器的 C 源代码
.Turing machine simulator
=========================
-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxQuintuples 128 /* expand as needed */
#define QuintupleLen 5
#define MaxBuffer 128
#define MaxTape 33 /* expand as needed: 1 line of display */
#define MaxSteps 1000000 /* assume 'infinite looping' thereafter */
#define Blank '0' /* 2-character alphabet: 0 and 1 */
#define StartState 'a'
#define TapeBorder "+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
#define CellSide '|'
#define Ellipsis "..."
#define CellLen 2
enum { NewState = 2, NewSymbol = 3, Direction = 4 };
char quintuples[MaxQuintuples][QuintupleLen + 1]; /* array of strings */
unsigned qlen = 0; /* number of entries from input file */
unsigned displayFlag = 1; /* 2nd command-line arg turns this off */
char tape[MaxTape];
unsigned currentCell = MaxTape / 2; /* tape middle */
char currentState = StartState;
unsigned instructionsExecuted = 0;
void die(const char* msg) {
puts(msg);
exit(EXIT_FAILURE);
}
void print_cell(unsigned ind) {
putchar(CellSide);
putchar(tape[ind]);
}
void pause() {
puts("Hit RETURN to continue...");
getchar();
}
void display_tape() {
printf("\nCurrent state: %c\n", currentState);
printf(" %s\n", TapeBorder);
printf("%s", Ellipsis);
unsigned i;
for (i = 0; i < MaxTape; i++) print_cell(i);
printf("%c%s\n %s\n", CellSide, Ellipsis, TapeBorder);
i = (CellLen * currentCell) + 2;
printf("%*s%c\n", i, "", '^');
pause();
}
int comp(const void* e1, const void* e2) { /* qsort and bsearch callback */
const char* s1 = (char*) e1;
const char* s2 = (char*) e2;
return strncmp(s1, s2, 2); /* < 0 = s1 < s2; 0 = s1 == s2; > 0 = s1 > s2 */
}
void read_program(const char* file) {
FILE* infile = fopen(file, "r");
char buff[MaxBuffer + 1];
if (NULL == infile) {
sprintf(buff, "Can't open program file %s", file);
die(buff);
}
while (fgets(buff, MaxBuffer, infile)) { /* read until end-of-file */
if ('#' == buff[0]) continue; /* ignore comments */
if (strlen(buff) < QuintupleLen) continue; /* ignore faulty lines */
strncpy(quintuples[qlen], buff, QuintupleLen);
qlen++;
}
fclose(infile);
qsort(quintuples, qlen, sizeof(quintuples[0]), comp); /* sort for easy access */
memset(tape, Blank, MaxTape); /* blank out the tape */
}
void report() {
/* Show instructions. */
printf("%i instructions:\n", qlen);
unsigned i, count = 0;
for (i = 0; i < qlen; i++) puts(quintuples[i]);
for (i = 0; i < MaxTape; i++) if ('1' == tape[i]) count++;
printf("Total 1s on tape: %8i\n", count);
printf("Instructions executed: %8i\n", instructionsExecuted);
}
void check_for_errors(const char* action) {
if (0 == (currentCell - 1) && 'L' == action[Direction]) die("Can't move left...");
if (currentCell >= MaxTape - 1 && 'R' == action[Direction]) die("Can't move right...");
if (instructionsExecuted >= MaxSteps) die("Seems to be infinitely touring...");
}
void run_simulation() {
while (1) {
if (displayFlag) display_tape();
/* Get the action for the current key. */
char key[3];
sprintf(key, "%c%c", currentState, tape[currentCell - 1]);
char* action = bsearch(key, quintuples, qlen, sizeof(quintuples[0]), comp);
if (NULL == action) break; /* no match == normal termination */
check_for_errors(action);
/* Update system. */
currentState = action[NewState];
tape[currentCell - 1] = action[NewSymbol];
if ('L' == action[Direction]) currentCell--; /* move left */
else currentCell++; /* move right */
instructionsExecuted++; /* update step counter */
}
}
int main(int argc, char* argv[]) {
if (argc < 2) die("Usage: turing <program file>");
if (argc > 2 && 0 == strcmp(argv[2], "off")) displayFlag = 0;
read_program(argv[1]);
run_simulation();
report();
return 0;
}代码非常简单，大约有 130 行。以下是控制流程的摘要
- 图灵程序从输入文件（作为命令行参数给出）读取，该文件包含五元组（每行一个），如 BBG-N 示例中所示。
- 然后，模拟器循环直到发生以下条件之一
- 如果输入程序达到停机状态，则模拟器在报告程序的指令、产生的 1 的数量以及执行此操作所需的步骤数后正常退出。
- 如果计算尝试从最左边的单元格向左移动或从最右边的单元格向右移动，则模拟器会显示错误消息退出。磁带对于计算来说不够大。
- 如果计算达到 MaxSteps（当前设置为一百万），则模拟器会因怀疑“无限巡回”而终止。
模拟器期望将包含 BBG-N 或其他程序的文件名作为命令行参数。以 % 作为命令行提示符，此命令在先前引入的 bb4.prog 文件上运行模拟器
% ./turing bb4.prog默认情况下，模拟器在每个指令执行后显示磁带并暂停。但是，可以从命令行关闭显示
% ./turing bb5.prog off 这会生成一份关于 BBG-5 最佳竞争者的报告，该竞争者在停止之前需要超过 4700 万步
10 instructions:
a0b1R
a1c1L
b0c1R
b1b1R
c0d1R
c1e0L
d0a1L
d1d1L
e0h1R
e1a0L
Total 1s on tape: 4098
Instructions executed: 47176870程序文件应以换行符终止每行，包括最后一行；否则，模拟器可能无法读取该行。模拟器忽略注释（以 # 开头）和空行。为了回顾，这是 bb4.prog 输入文件
# bb4 winner
a0b1R
a1b1L
b0a1L
b1c0L
c0h1R # (halt state)
c1d1L
d0d1R
d1a0R在图灵源文件的顶部是各种宏（在 C 中，#define 指令），它们指定大小。这些特别值得关注
#define MaxQuintuples 128 /* expand as needed */
#define MaxTape 33 /* expand as needed */
#define MaxSteps 1000000 /* assume 'infinite touring' thereafter */可以根据需要增加指定的大小，但即使是最好的 BBG-5 竞争者也只有 10 条指令。BBG-5 等竞争者的磁带必须非常大，并且该竞争者需要超过 4700 万步才能完成计算。这些设置就足够了
#define MaxTape 100000000 /* 100M */
#define MaxSteps 100000000 /* 100M */BBG-5 和其他最佳竞争者应使用 off 标志运行，因为模拟器目前在一行上显示 MaxTape 单元格。
总结
BBG 应该吸引休闲问题解决者，尤其是程序员。编写 BBG 程序就是在抽象计算机——图灵机——的机器语言中工作，图灵机定义了可计算的含义。入门的一种方法是从头开始编写 BBG-2 和 BBG-3 获胜者。这些练习有助于揭示在真正艰巨的挑战（如 BBG-4 获胜者和 BBG-5 最佳竞争者）中使用的编程模式。
另一个入门练习是编写一个程序，该程序首先将磁带初始化为两个数字值（以一元形式），中间用 0 分隔
+-+-+-+-+-+-+-+-+
...|0|1|1|0|1|1|1|0|... ## two and three in unary
+-+-+-+-+-+-+-+-+
^然后，该程序计算例如以一元形式表示的乘积。其他算术示例比比皆是。
BBG 也持续受到逻辑学、数学和计算机科学理论家的关注。有关它们的简要历史和概述，请参阅最慢的计算机程序如何阐明数学的基本限制。
评论已关闭。