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

'''Beklemishev's Worm'''，是列夫·贝克勒米舍夫（俄语：Беклемишев Лев Дмитриевич<ref>Росси́йская акаде́мия нау́к (n.d.). Беклемишев Лев Дмитриевич. ''(EB/OL), Росси́йская акаде́мия нау́к''. Available at: https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru</ref><ref>Персоналии (n.d.). Беклемишев Лев Дмитриевич. ''(EB/OL), Персоналии''. Available at:  https://www.mathnet.ru/php/person.phtml?personid=17809</ref>）于 2002 年描述的一种结构，一个需要很长时间才能终止的单人游戏<ref>Beklemishev, L. (2006). The Worm principle. In Z. Chatzidakis, P. Koepke, & W. Pohlers (Eds.), Logic Colloquium '02 (Lecture Notes in Logic, pp. 75-95). ''Cambridge: Cambridge University Press'', [https://doi.org/10.1017/9781316755723.005/ 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>. 如果 <math>k</math> 不存在，则 <math>g=[]</math>，并且 <math>b=[a_0,a_1,\cdots,a_{n-1},a_n-1]</math>. 随后我们定义 <math>next(S,m)=g+ \underbrace{b+ b+\cdots+b}_{ m+1\text{个b} }</math>。

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

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

=== 例子 ===
第一个例子是蠕虫<math>[1]</math>：

* 初始值：<math>[1]</math>
* 第 1 步：<math>[0,0]</math>
* 第 2 步：<math>[0]</math>
* 第 3 步：<math>[]</math>

所以 <math>\mathrm{Worm}(1)=3</math>.

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

* 初始值：<math>[2]</math>
* 第 1 步：<math>[1,1]</math>
* 第 2 步：<math>[1,0,1,0,1,0]</math>
* 第 3 步：<math>[1,0,1,0,1]</math>
* 第 4 步：<math>[1,0,1,0,0,0,0,0,0]</math>
* 第10步：<math>[1,0,1]</math>
* 第11步：<math>[1,0^{13}]</math>
* 第24步：<math>[1]</math>
* 第25步：<math>[0^{26}]</math>
* 第51步：<math>[]</math>

所以 <math>\mathrm{Worm}(2)=51</math>。<ref>Koteitan (n.d.). Beklemishev's Worm Simulator in JavaScript. ''(EB/OL)''. Available at: https://koteitan.github.io/BeklemishevsWorms/</ref>

=== 展开器 ===
上述蠕虫展开例子可以通过 Koteitan 的 JavaScript 展开器展开，见 [https://koteitan.github.io/BeklemishevsWorms/ Beklemishev’s worm simulator in javascript]

=== 扩展 ===
Beklemishev's Worm 中蕴含了深刻的序数结构<ref>HypCos (2022). 这种大数有如何大？更大的大数规则是用怎样的思维构造的？[How big is this big number? What kind of thinking is used to construct the larger large number rule?]. ''(EB/OL), Zhihu''. Available at: https://www.zhihu.com/question/571363378/answer/2802103962</ref>。它的操作规则与 [[初等序列系统|PrSS]]（2013年提出）几乎完全一致，而 PrSS 又是 [[BMS]]，[[Y序列]]等一系列强大序数记号的基础。因此，我们称合法式是自然数序列的[[序数记号]]为 Worm 型记号。
== 参考资料 ==
{{默认排序:相关问题}}
[[分类:记号]]