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\sim \underset{m+1}{\underbrace{b\sim b\sim \cdots \sim b}}$.其中~是序列连接，如$[0,3,2]\sim [1,4,5]=[0,3,2,1,4,5]$.

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

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

例子

第一个例子是蠕虫[1].

• 开始时间：[1]
• 第 1 步：[0,0]
• 第 2 步：[0]
• 第 3 步：[]

所以$Worm(1)=3$.

第二个例子是蠕虫[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,\underset{13}{\underbrace{0,0,\cdots ,0}}]$
• 第 24 步：[1]
• 步骤25：$[\underset{26}{\underbrace{0,0,\cdots ,0}}]$
• 步骤 51： []

所以$Worm(2)=51$

扩展

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