Beklemishev's Worm：修订间差异

2025年8月20日 (三) 16:14的最新版本

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 型记号。

参考资料

↑ Росси́йская акаде́мия нау́к (n.d.). Беклемишев Лев Дмитриевич. (EB/OL), Росси́йская акаде́мия нау́к. Available at: https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru
↑ Персоналии (n.d.). Беклемишев Лев Дмитриевич. (EB/OL), Персоналии. Available at: 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.
↑ Koteitan (n.d.). Beklemishev's Worm Simulator in JavaScript. (EB/OL). Available at: https://koteitan.github.io/BeklemishevsWorms/
↑ 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

[1] Росси́йская акаде́мия нау́к (n.d.). Беклемишев Лев Дмитриевич. (EB/OL), Росси́йская акаде́мия нау́к. Available at: https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru

[2] Персоналии (n.d.). Беклемишев Лев Дмитриевич. (EB/OL), Персоналии. Available at: https://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] Koteitan (n.d.). Beklemishev's Worm Simulator in JavaScript. (EB/OL). Available at: https://koteitan.github.io/BeklemishevsWorms/

[5] 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

[1]

[2]

[3]

[4]

[5]

@@ 第1行： / 第1行： @@
-'''Beklemishev's Worm'''，是列夫·贝克勒米舍夫（俄语：Беклемишев Лев Дмитриевич<ref>Росси́йская акаде́мия нау́к. Беклемишев Лев Дмитриевич. ''(EB/OL), Росси́йская акаде́мия нау́к''.  https://www.ras.ru/win/db/show_per.asp?P=.id-5721.ln-ru</ref><ref>Персоналии. Беклемишев Лев Дмитриевич. ''(EB/OL), Персоналии''. 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]] 密切相关。
+'''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]] 密切相关。
 === 定义 ===
@@ 第5行： / 第5行： @@
 # 若 <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>. 随后我们定义<br /><br /><math>next(S,m)=g+ \underbrace{b+ b+\cdots+b}_{ m+1\text{个b} }</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 公理体系]]中是无法证明的。
@@ 第36行： / 第34行： @@
 * 第51步：<math>[]</math>
-所以 <math>\mathrm{Worm}(2)=51</math>。<ref>Koteitan. Beklemishev's Worm Simulator in JavaScript. ''(EB/OL)''. https://koteitan.github.io/BeklemishevsWorms/</ref>
+所以 <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>
 === 展开器 ===
@@ 第42行： / 第40行： @@
 === 扩展 ===
-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)''. https://www.zhihu.com/question/571363378/answer/2802103962</ref>。它的操作规则与 [[初等序列系统|PrSS]]（2013年提出）几乎完全一致，而 PrSS 又是 [[BMS]]，[[Y序列]]等一系列强大序数记号的基础。因此，我们称合法式是自然数序列的[[序数记号]]为 Worm 型记号。
+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 型记号。
 == 参考资料 ==
+{{默认排序:相关问题}}
 [[分类:记号]]