查看“︁初等序列系统”︁的源代码

<div style="word-wrap: break-word;text-wrap: pretty;color: var(--color-subtle);font-style: italic;width:Fit-content;padding:1rem 1rem 2rem 1rem;border-left:solid #00000030 5px;background-color:var(--color-surface-2)">PrSS虽然结构简单，但是却是目前已知的最强大的递归核心的基础。<br /><span style='float:right'><del>——</del>曹知秋</span></div>

'''初等序列系统 (Primative Sequence System,PrSS)''' 是一种[[Worm]]型[[序数记号]]。
==== 定义 ====

===== 标准式判定 =====
一个'''标准且合法'''的 <math>\rm PrSS</math> 是形如 <math>S=(s_{0},s_{1},s_{2},\cdots,s_{n},s_{n+1},\cdots)|n \in \mathbb{N}</math> 且满足以下所有条件的序列：

<math>\langle \text{1} \rangle\ \quad s_{0}=0.</math>

<math>\langle \text{2} \rangle\ \quad 0\leq s_{n+1}-s_{n}\leq 1.</math>

例：

<math>(0,1,1,2,2)</math>是一个合法的 <math>\rm PrSS</math> 序列.

<math>(\Omega,1,2)</math>是一个非法的 <math>\rm PrSS</math> 序列.

<math>(0,2,4,6,8)</math>是一个非法的 <math>\rm PrSS</math> 序列.
===== 结构 =====

一个'''标准的'''<math>\rm PrSS</math>由以下四个部分组成：
# 末项 <math>\mathrm{(Last\ Term)}</math>
# 坏部 <math>\mathrm{(Bad\ Part)}</math>
# 坏根 <math>\mathrm{(Bad\ Root)}</math>
# 好部 <math>\mathrm{(Good\ Part)}</math>

'''末项'''

对于最大下标为 <math>n</math> 的 <math>\rm PrSS</math> 序列 <math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})</math>，其末项 <math>L=s_{n}</math>，即

<math>S=(s_{0},s_{1},s_{2},\cdots,L).</math>

'''坏根'''

对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})|L=s_{n}</math>，若<math>k=max(0 \leq k < n|s_{k}<s_{n})</math>，那么坏根 <math>r=s_{k}</math>，即

<math>S=(s_{0},s_{1},s_{2},\cdots,r,\cdots,L).</math>

'''坏部'''

对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，坏部 <math>B=\{s_{i}|k\leq i <n\}</math>，即

<math>S=(s_{0},s_{1},s_{2},\cdots,r,B-r,L)</math>

其中 <math>B-r</math> 表示 <math>B</math> 不包含 <math>r .</math>

'''好部'''

对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，好部 <math>G=\{s_{j}|0\leq j <k\}</math>，即

<math>S=(G,r,B-r,L).</math>

对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})|L=s_{n}=0</math>，好部 <math>G=\{s_{j}|0\leq j <n\}</math>，即

<math>S=(G,0).</math>

可以注意到，根据坏根的定义，坏根<math>r</math> 有可能不存在。这将会导致不存在 坏部<math>B</math> 的 <math>\rm PrSS</math> 序列产生。例如：

* <math>(0,1,2,1,0)</math>
* <math>(0,1,0,0,0)</math>
* <math>(0,0,0,0,0)</math>

实际上，这种<math>\rm PrSS</math>序列所表示的序数为[[序数|后继序数]]，你很快就会在下文中见到它。

==== 展开 ====

所有标准的<math>\rm PrSS</math>序列都对应着一个序数。
对于一个标准的<math>\rm PrSS</math>序列 <math>S=(G,B,L)</math>，定义 <math>m,S[m] \in \mathbb{N}</math>，其展开规则如下：

若 <math>m</math> 存在，

<math>L=0</math>时，

<math>S[m]=(G,B,0)[m]=(G,B)[m]+1.</math>

<math>L\neq 0</math>时，
<math>S[m]=(G,B,L)[m]=(G,\underbrace{B,B,\cdots,B}_{m})[m].</math>

若 <math>m</math> 不存在，

<math>L=0</math>时，

<math>S=(G,B,0)=(G,B)+1.</math>

<math>L\neq 0</math>时，
<math>S</math> 是[[序数|极限序数]]，且
<math>S=sup\{(G),(G,B),(G,B,B),(G,B,B,B),\cdots\}.</math>

若 <math>L=\emptyset</math>，
<math>S[m]=S=0.</math>

显然，如果末项为 <math>0</math>，将不存在坏根；此时的 <math>B</math> 应被理解为删除 <math>S</math> 有限次末项的 <math>0</math> 后所得极限序数的坏部；如果经过有限次删除后，<math>S</math> 最终变为空序列，那么 <math>S=S[m] \in \mathbb{N}</math>

==== 形式化定义 ====
<math>\rm PrSS</math>序列可以看作是一个坍缩 / 折叠记号。

末项就是序列的结尾，

坏根就是从右往左数第一个比末项小的元素，

坏部就是坏根到末项（不包括末项）之间的序列，

好部就是除了坏部和末项外的所有东西。<ref group="footnotes">好部被称之为“好部”可能是因为展开时好部完全不用动，看起来令人舒适，因而得名”好“。</ref>



具体说来，末项非零的<math>\rm PrSS</math>是让序列末项折叠序列 <math>[\text{坏根},\text{末项})</math> 的重复。例：

<math>S=(0,1,2,{\color{red}2},3,3,3)</math>

末项：<math>L=3</math>

坏根是从右往左数第一个比3小的数，也就是标红色的2.

接下来标出坏部（下划线）：

<math>S=(0,1,2,\underline{{\color{red}2},3,3},3)</math>


接下来，好部不用管，然后将末项抛弃：

<math>S=(0,1,2,\underline{{\color{red}2},3,3})</math>

然后复制坏部：

<math>S=(0,1,2,\underline{{\color{red}2},3,3},\underline{{\color{red}2},3,3},\underline{{\color{red}2},3,3},\cdots)</math>

我们就成功地展开了一个<math>\rm PrSS</math>序列。

==== 枚举 ====

<math>()=0</math>

<math>(0)=1</math>

<math>(0,0)=2</math>

<math>(0,0,0)=3</math>

<math>(0,1)=({\color{red}0},{\color{green}0},\cdots,{\color{blue}0})=\omega</math>

<math>(0,1,0)=\omega+1</math>

<math>(0,1,0,0)=\omega+2</math>

<math>(0,1,0,1)=(0,1,{\color{red}0},{\color{green}0},\cdots,{\color{blue}0})=\omega\times 2</math>

<math>(0,1,0,1,0,1)=\omega\times 3</math>

<math>(0,1,1)=({\color{red}0,1},{\color{green}0,1},\cdots,{\color{blue}0,1})=\omega^{2}</math>

<math>(0,1,1,0)=\omega^{2}+1</math>

<math>(0,1,1,0,1)=\omega^{2}+\omega</math>

<math>(0,1,1,0,1,0)=\omega^{2}+\omega+1</math>

<math>(0,1,1,0,1,0,1)=\omega^{2}+\omega\times 2</math>

<math>(0,1,1,0,1,1)=(0,1,1,{\color{red}0,1},{\color{green}0,1},\cdots,{\color{blue}0,1})=\omega^{2}\times 2</math>

<math>(0,1,1,0,1,1,0,1,1)=\omega^{2}\times 3</math>

<math>(0,1,1,1)=({\color{red}0,1,1},{\color{green}0,1,1},\cdots,{\color{blue}0,1,1})=\omega^{3}</math>

<math>(0,1,1,1,1)=\omega^{4}</math>

<math>(0,1,2)=(0,{\color{red}1},{\color{green}1},\cdots,{\color{blue}1})=\omega^{\omega}</math>

<math>(0,1,2,0,1,2)=\omega^{\omega}\times 2</math>

<math>(0,1,2,1)=({\color{red}0,1,2},{\color{green}0,1,2},\cdots,{\color{blue}0,1,2})=\omega^{\omega+1}</math>

<math>(0,1,2,1,0,1,2)=\omega^{\omega+1}+\omega^{\omega}</math>

<math>(0,1,2,1,0,1,2,1)=\omega^{\omega+1}\times 2</math>

<math>(0,1,2,1,1)=({\color{red}0,1,2,1},{\color{green}0,1,2,1},\cdots,{\color{blue}0,1,2,1})=\omega^{\omega+2}</math>

<math>(0,1,2,1,1,1)=\omega^{\omega+3}</math>

<math>(0,1,2,1,2)=(0,1,2,{\color{red}1},{\color{green}1},\cdots,{\color{blue}1})=\omega^{\omega\times 2}</math>

<math>(0,1,2,1,2,1)=\omega^{\omega\times 2+1}</math>

<math>(0,1,2,1,2,1,2)=\omega^{\omega\times 3}</math>

<math>(0,1,2,2)=(0,{\color{red}1,2},{\color{green}1,2},\cdots,{\color{blue}1,2})=\omega^{\omega^{2}}</math>

<math>(0,1,2,2,1)=\omega^{\omega^{2}+1}</math>

<math>(0,1,2,2,1,2)=\omega^{\omega^{2}+\omega}</math>

<math>(0,1,2,2,1,2,1)=\omega^{\omega^{2}+\omega+1}</math>

<math>(0,1,2,2,1,2,1,2)=\omega^{\omega^{2}+\omega\times 2}</math>

<math>(0,1,2,2,1,2,2)=(0,1,2,2,{\color{red}1,2},{\color{green}1,2},\cdots,{\color{blue}1,2})=\omega^{\omega^{2}*2}</math>

<math>(0,1,2,2,2)=(0,{\color{red}1,2,2},{\color{green}1,2,2},\cdots,{\color{blue}1,2,2})=\omega^{\omega^{3}}</math>

<math>(0,1,2,3)=(0,1,{\color{red}2},{\color{green}2},\cdots,{\color{blue}2})=\omega^{\omega^{\omega}}</math>

<math>(0,1,2,3,2)=\omega^{\omega^{\omega+1}}</math>

<math>(0,1,2,3,2,3)=\omega^{\omega^{\omega\times 2}}</math>

<math>(0,1,2,3,3)=\omega^{\omega^{\omega^{2}}}</math>

<math>(0,1,2,3,4)=(0,1,2,{\color{red}3},{\color{green}3},\cdots,{\color{blue}3})=\omega^{\omega^{\omega^{\omega}}}</math>

<math>(0,1,2,3,4,5,...)=Limit\ of\ PrSS=\varepsilon_{0}</math>

==== 拓展 ====

<math>\rm PrSS</math>序列有两种拓展：
* 高维PrSS，如PrSS原作者所创的[[BMS]]
* 阶差PrSS，有两种形式：
** [[LPrSS]]及各种[[Hydra]]记号
** [[HPrSS]]，[[0-Y]]，[[Y序列]]等复杂阶差型记号

它们以<math>\rm PrSS</math>序列为基础，刻画了非常巨大的序数。

==== 历史 ====

在2014/08/14，Bashicu首次提出并使用Basic语言定义了PrSS.<ref>Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html</ref>

==== 脚注 ====
<references group="footnotes" />

==== 参考资料 ====