Beklemishev's Worm：修订间差异

2025年7月8日 (二) 06:08的版本

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

定义

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

若 $a_{n} = 0$ ，则 $n e x t (S, m) = [a_{0}, a_{1}, \dots, a_{n - 1}]$ .
否则，定义 $k = m a x_{i < n} a_{i} < a_{n}$ ，序列的好部定义为 $g = [a_{0}, a_{1}, \dots, a_{k}]$ ，坏部定义为 $b = [a_{k + 1}, a_{k + 2}, \dots, a_{n - 1}, a_{n} - 1]$ . 如果 $k$ 不存在，则 $g = []$ ，并且 $b = [a_{0}, a_{1}, \dots, a_{n - 1}, a_{n} - 1]$ . 随后我们定义

$n e x t (S, m) = g + \underset{m + 1 个b}{\underset{⏟}{b + b + \dots + b}}$ .

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

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

例子

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

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

所以 $W o r m (1) = 3$ .

接下来我们用 $0^{n}$ 来表示 $\underset{n}{\underset{⏟}{0, 0, \dots, 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步： $[]$

所以 $W o r m (2) = 51$ .^[4]

展开器

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

扩展

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

参考资料

↑ https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru
↑ https://www.mathnet.ru/php/person.phtml?personid=17809
↑ 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. doi:10.1017/9781316755723.005
↑ https://koteitan.github.io/BeklemishevsWorms/
↑ HYPCOS. 这种大数有如何大？更大的大数规则是用怎样的思维构造的？[EB/OL]. 2022. https://www.zhihu.com/question/571363378/answer/2802103962.

[1] ttps://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru

[2] ttps://www.mathnet.ru/php/person.phtml?personid=17809

[3] 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. doi:10.1017/9781316755723.005

[4] ttps://koteitan.github.io/BeklemishevsWorms/

[5] HYPCOS. 这种大数有如何大？更大的大数规则是用怎样的思维构造的？[EB/OL]. 2022. https://www.zhihu.com/question/571363378/answer/2802103962.

[1]

[2]

[3]

[4]

[5]

@@ 第1行： / 第1行： @@
-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]]密切相关。
+'''Beklemishev's Worm'''，是列夫·贝克勒米舍夫（俄语：Беклемишев Лев Дмитриевич<ref>https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru</ref><ref>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>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>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>.
+# 否则，定义 <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>. 随后我们定义<br /><br /><math>next(S,m)=g+ \underbrace{b+ b+\cdots+b}_{ m+1\text{个b} }</math>.
-Beklemishev证明了，无论S初始是怎样的蠕虫，Cedric总是可以在有限轮之内击败它。他后续展示了这一定理在[[皮亚诺公理体系|PA]]中是无法证明的。
-通过这个游戏，可以构造出一个快速增长的函数<math>Worm(n)</math>为击败蠕虫[n]所需的步数。这一函数的FGH增长率为<math>\varepsilon_0</math>。
+Beklemishev证明了，无论S初始是怎样的蠕虫，Cedric总是可以在有限轮之内击败它。他后续展示了这一定理在[[Peano公理体系|PA公理体系]]中是无法证明的。
+通过这个游戏，可以构造出一个快速增长的函数 <math>\mathrm{Worm}(n)</math> 为击败蠕虫<math>[n]</math>所需的步数。这一函数的FGH增长率为<math>\varepsilon_{0}</math>.
 == 例子 ==
-第一个例子是蠕虫[1].
+第一个例子是蠕虫<math>[1]</math>：
-* 开始时间：[1]
+* 初始值：<math>[1]</math>
-* 第 1 步：[0,0]
+* 第 1 步：<math>[0,0]</math>
-* 第 2 步：[0]
+* 第 2 步：<math>[0]</math>
-* 第 3 步：[]
+* 第 3 步：<math>[]</math>
-所以<math>Worm(1)=3</math>.
+所以 <math>\mathrm{Worm}(1)=3</math>.
-第二个例子是蠕虫[2]
+接下来我们用 <math>0^{n}</math> 来表示 <math>\underbrace{0,0,\cdots,0}_{n}</math>。第二个例子是蠕虫<math>[2]</math>：
-* 开始时间：[2]
+* 初始值：<math>[2]</math>
-* 步骤1： [1,1]
+* 第 1 步：<math>[1,1]</math>
-* 第 2 步：[1,0,1,0,1,0]
+* 第 2 步：<math>[1,0,1,0,1,0]</math>
-* 第 3 步：[1,0,1,0,1]
+* 第 3 步：<math>[1,0,1,0,1]</math>
-* 第 4 步：[1,0,1,0,0,0,0,0,0]
+* 第 4 步：<math>[1,0,1,0,0,0,0,0,0]</math>
-* 第10步：[1,0,1]
+* 第10步：<math>[1,0,1]</math>
-* 第11步：<math>[1,\underbrace{0,0,\cdots,0}_{13}]</math>
+* 第11步：<math>[1,0^{13}]</math>
-* 第 24 步：[1]
+* 第24步：<math>[1]</math>
-* 步骤25：<math>[\underbrace{0,0,\cdots,0}_{26}]</math>
+* 第25步：<math>[0^{26}]</math>
-* 步骤 51： []
+* 第51步：<math>[]</math>
-所以<math>Worm(2)=51</math><ref>[https://googology.fandom.com/wiki/Beklemishev%27s_worms#cite_ref-3]</ref>
+所以 <math>\mathrm{Worm}(2)=51</math>.<ref>https://koteitan.github.io/BeklemishevsWorms/</ref>
+== 展开器 ==
+上述蠕虫展开例子可以通过Koteitan的JavaScript展开器展开，见[https://koteitan.github.io/BeklemishevsWorms/ Beklemishev’s worm simulator in javascript]
 == 扩展 ==
-Beklemishev's Worm中蕴含了深刻的序数结构。它的操作规则与[[初等序列系统|PrSS]]（2013年提出）几乎完全一致，而PrSS又是[[BMS]]，[[Y序列]]等一系列记号的基础。因此，我们称合法式是自然数序列的[[序数记号]]为Worm型记号。
+Beklemishev's Worm中蕴含了深刻的序数结构<ref>HYPCOS. 这种大数有如何大？更大的大数规则是用怎样的思维构造的？[EB/OL]. 2022. https://www.zhihu.com/question/571363378/answer/2802103962.</ref>。它的操作规则与[[初等序列系统|PrSS]]（2013年提出）几乎完全一致，而PrSS又是[[BMS]]，[[Y序列]]等一系列强大序数记号的基础。因此，我们称合法式是自然数序列的[[序数记号]]为Worm型记号。
 == 参考资料 ==
 [[分类:记号]]