查看“︁Beklemishev's Worm”︁的源代码

Beklemishev's Worm是列夫·贝克勒米舍夫（俄语：Беклемишев Лев Дмитриевич<ref>[https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru]</ref><ref>https://googology.fandom.com/wiki/Beklemishev%27s_worms#cite_ref-2</ref>）在2002年描述的一种结构，它是一个单人游戏，需要很长时间才能终止<ref>Beklemishev， L. （2006）.蠕虫原理。在Z. Chatzidakis， P. Koepke， & W. Pohlers （编辑）， 逻辑座谈会'02 （逻辑学讲义，第75-95页）。剑桥：剑桥大学出版社. doi：10.1017/9781316755723.005</ref>。它与 [[Kirby-Paris Hydra]]密切相关。

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

# 若<math>a_n=0</math>,则<math>next(S,m)=[a_0,a_1,\cdots,a_{n-1}]</math>.
# 否则，定义<math>k=max_{i<n} a_i<a_n</math>,序列的好部定义为<math>g=[a_0,a_1,\cdots,a_k]</math>，坏部定义为<math>b=[a_{k+1},a_{k+2},\cdots,a_{n-1},a_n-1]</math>.如果k不存在，则定义g为空列表，并且<math>b=[a_0,a_1,\cdots,a_{n-1},a_n-1]</math>。随后我们定义<math>next(S,m)=g\sim \underbrace{b\sim b\sim\cdots\sim b}_{ m+1 }</math>.其中~是序列连接，如<math>[0,3,2]\sim[1,4,5]=[0,3,2,1,4,5]</math>.

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

通过这个游戏，可以构造出一个快速增长的函数<math>Worm(n)</math>为击败蠕虫[n]所需的步数。这一函数的FGH增长率为<math>\varepsilon_0</math>。

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

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

所以<math>Worm(1)=3</math>.

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

所以<math>Worm(2)=51</math><ref>[https://googology.fandom.com/wiki/Beklemishev%27s_worms#cite_ref-3]</ref>

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

== 参考资料 ==
[[分类:记号]]