Beklemishev's Worm

Beklemishev's Worm，是列夫·贝克勒米舍夫（俄语：Беклемишев Лев Дмитриевич）于 2002 年描述的一种结构，一个需要很长时间才能终止的单人游戏。它与 Kirby-Paris Hydra 密切相关。

定义

一个蠕虫是由自然数构成的序列 $S=[a_0,a_1,\cdots ,a_n]$。在 Beklemishev 命名的一个叫“蠕虫大战”的游戏中，我们的英雄Cedric面前有这样的一条蠕虫S，他的目标是击败它，即把它变成空序列。在这个游戏的第 m 轮，S 被变换为 $next(S,m)$，游戏规则如下

1. 若 $a_n=0$，则 $next(S,m)=[a_0,a_1,\cdots ,a_{n-1}]$.
2. 否则，定义 $k=ma{x}_{i<n}{a}_i<a_n$，序列的好部定义为 $g=[a_0,a_1,\cdots ,a_k]$，坏部定义为 $b=[a_{k+1},a_{k+2},\cdots ,a_{n-1},a_n-1]$. 如果 $k$ 不存在，则 $g=[]$，并且 $b=[a_0,a_1,\cdots ,a_{n-1},a_n-1]$. 随后我们定义 $next(S,m)=g+\underset{m+1\text{个b}}{\underbrace{b+b+\cdots +b}}$。

Beklemishev 证明了，无论 S 初始是怎样的蠕虫，Cedric 总是可以在有限轮之内击败它。他后续展示了这一定理在 PA 公理体系中是无法证明的。

通过这个游戏，可以构造出一个快速增长的函数 $\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{m}(n)$ 为击败蠕虫 $[n]$所需的步数。这一函数的 FGH 增长率为${\epsilon }_0$。

例子

第一个例子是蠕虫$[1]$：

• 初始值：$[1]$
• 第 1 步：$[0,0]$
• 第 2 步：$[0]$
• 第 3 步：$[]$

所以 $\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{m}(1)=3$.

接下来我们用 $0^n$ 来表示 $\underset{n}{\underbrace{0,0,\cdots ,0}}$。第二个例子是蠕虫$[2]$：

• 初始值：$[2]$
• 第 1 步：$[1,1]$
• 第 2 步：$[1,0,1,0,1,0]$
• 第 3 步：$[1,0,1,0,1]$
• 第 4 步：$[1,0,1,0,0,0,0,0,0]$
• 第10步：$[1,0,1]$
• 第11步：$[1,0^{13}]$
• 第24步：$[1]$
• 第25步：$[0^{26}]$
• 第51步：$[]$

所以 $\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{m}(2)=51$。

展开器

上述蠕虫展开例子可以通过 Koteitan 的 JavaScript 展开器展开，见 Beklemishev’s worm simulator in javascript

扩展

Beklemishev's Worm 中蕴含了深刻的序数结构。它的操作规则与 PrSS（2013年提出）几乎完全一致，而 PrSS 又是 BMS，Y序列等一系列强大序数记号的基础。因此，我们称合法式是自然数序列的序数记号为 Worm 型记号。