初等序列系统

PrSS虽然结构简单，但是却是目前已知的最强大的递归核心的基础。
------ 曹知秋

初等序列系统（Primative Sequence System,PrSS）是一种Worm型序数记号。

定义

标准式

一个标准且合法的 $\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$ 是形如

$S=(s_0,s_1,s_2,\cdots ,s_n,s_{n+1},\cdots )|n\in \mathbb{\mathbb{N}}$ 

且满足以下所有条件的序列：

$⟨\text{1}⟩s_0=0.$

$⟨\text{2}⟩0\le s_{n+1}-s_n\le 1.$

例：

$(0,1,1,2,2)$ 是一个合法的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$.

$(\mathrm{\Omega },1,2)$ 是一个非法的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$.

$(0,2,4,6,8)$ 是一个非法的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$.

结构

一个标准的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$由以下四个部分组成：

1. 末项 $\mathrm{(}\mathrm{L}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{T}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{)}$
2. 坏部 $\mathrm{(}\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{)}$
3. 坏根 $\mathrm{(}\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{R}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{)}$
4. 好部 $\mathrm{(}\mathrm{G}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{)}$

末项

对于最大下标为 $n$ 的 $\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$ 序列 $S=(s_0,s_1,s_2,\cdots ,s_n)$，其末项 $L=s_n$，即

$S=(s_0,s_1,s_2,\cdots ,L).$

坏根

对于$S=(s_0,s_1,s_2,\cdots ,s_n)|L=s_n$，若$k=max(0\le k<n|s_k<s_n)$，那么坏根 $r=s_k$，即

$S=(s_0,s_1,s_2,\cdots ,r,\cdots ,L).$

坏部

对于$S=(s_0,s_1,s_2,\cdots ,s_k,\cdots ,s_n)|L=s_n,r=s_k$，坏部 $B=\{s_i|k\le i<n\}$，即

$S=(s_0,s_1,s_2,\cdots ,r,B-r,L)$

其中 $B-r$ 表示 $B$ 不包含 $r.$

好部

对于$S=(s_0,s_1,s_2,\cdots ,s_k,\cdots ,s_n)|L=s_n,r=s_k$，好部 $G=\{s_j|0\le j<k\}$，即

$S=(G,r,B-r,L).$

对于$S^{\prime }=(s_0,s_1,s_2,\cdots ,s_n)|L=s_n=0$，好部 $G=\{s_j|0\le j<n\}$，即

$S^{\prime }=(G,0).$

可以注意到，根据坏根的定义，坏根$r$ 有可能不存在。这将会导致不存在 坏部$B$ 的 $\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$ 序列产生。例如：

• $(0,1,2,1,0)$
• $(0,1,0,0,0)$
• $(0,0,0,0,0)$

实际上，这种$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列所表示的序数为后继序数，你很快就会在下文中见到它。

展开

由于$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$的字典序，所有标准的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$都一一对应着一个序数。 对于一个标准的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列 $S=(G,B,L)$，定义 $m,S[m]\in \mathbb{\mathbb{N}}$，其展开规则如下：

如果 $m$ 存在，

若 $L=0$，则

$S[m]=(G,B,0)[m]=(G,\mathrm{\varnothing },0)[m]=(G)[m]+1.$

若 $L\ne 0$，则

$S[m]=(G,B,L)[m]=(G,\underset{m}{\underbrace{B,B,\cdots ,B}})[m].$

如果 $m$ 不存在，

若 $L=0$，则

$S=(G,B,0)=(G,B)+1.$

若 $L\ne 0$，则

$S$ 是极限序数，且

$S=sup\{(G),(G,B),(G,B,B),(G,B,B,B),\cdots \}.$

如果 $L=\mathrm{\varnothing }$，则

$S[m]=S=0.$

显然，如果末项为 $0$，将不存在坏根；此时的 $B$ 应被理解为删除 $S$ 有限次末项的 $0$ 后所得极限序数的坏部；如果经过有限次删除后，$S$ 最终变为空序列，那么

$S=S[m]\in \mathbb{\mathbb{N}}$

形式化定义

$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列可以看作是一个坍缩 / 折叠记号。

末项就是序列的结尾，

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

坏部就是坏根到末项（不包括末项）之间的序列，可以理解为小学时学的“循环节”

好部就是除了坏部和末项外的所有东西。

具体说来，末项非零的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列的展开是让大的末项折叠了序列 $[\text{坏根},\text{末项})$ 的重复。例：

$S=(0,1,2,2,3,3,3)$

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

接下来，根据坏部的定义可以知道2,3,3是”循环节“，用上划线标出“循环节"

$S=(0,1,2,\overline{2,3,3},3)$

坏根之前的好部不用管，将末项抛弃

$S=(0,1,2,\overline{2,3,3})$

复制循环节

$S=(0,1,2,\overline{2,3,3,2,3,3,2,3,3,\cdots })$

我们就成功地展开了一个$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列。

枚举

在按照字典序对所有可能的$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列进行排序之后，我们可以用序数对这些序列逐个进行标号，每个序列都与一个序数一一对应。事实上，这种对应关系要远比相应的大数函数增长率的对应关系要更本质。

枚举过程中，会对特定的循环节标记颜色，以更清晰地体现“折叠”。

可点击按钮“展开”以查看枚举。

$()=0$

$(0)=1$

$(0,0)=2$

$(0,0,0)=3$

$(0,1)=(0,0,\cdots ,0)=\omega$

$(0,1,0)=\omega +1$

$(0,1,0,0)=\omega +2$

$(0,1,0,1)=(0,1,0,0,\cdots ,0)=\omega \times 2$

$(0,1,0,1,0,1)=\omega \times 3$

$(0,1,1)=(0,1,0,1,\cdots ,0,1)={\omega }^2$

$(0,1,1,0)={\omega }^2+1$

$(0,1,1,0,1)={\omega }^2+\omega$

$(0,1,1,0,1,0)={\omega }^2+\omega +1$

$(0,1,1,0,1,0,1)={\omega }^2+\omega \times 2$

$(0,1,1,0,1,1)=(0,1,1,0,1,0,1,\cdots ,0,1)={\omega }^2\times 2$

$(0,1,1,0,1,1,0,1,1)={\omega }^2\times 3$

$(0,1,1,1)=(0,1,1,0,1,1,\cdots ,0,1,1)={\omega }^3$

$(0,1,1,1,1)={\omega }^4$

$(0,1,2)=(0,1,1,\cdots ,1)={\omega }^{\omega }$

$(0,1,2,0,1,2)={\omega }^{\omega }\times 2$

$(0,1,2,1)=(0,1,2,0,1,2,\cdots ,0,1,2)={\omega }^{\omega +1}$

$(0,1,2,1,0,1,2)={\omega }^{\omega +1}+{\omega }^{\omega }$

$(0,1,2,1,0,1,2,1)={\omega }^{\omega +1}\times 2$

$(0,1,2,1,1)=(0,1,2,1,0,1,2,1,\cdots ,0,1,2,1)={\omega }^{\omega +2}$

$(0,1,2,1,1,1)={\omega }^{\omega +3}$

$(0,1,2,1,2)=(0,1,2,1,1,\cdots ,1)={\omega }^{\omega \times 2}$

$(0,1,2,1,2,1)={\omega }^{\omega \times 2+1}$

$(0,1,2,1,2,1,2)={\omega }^{\omega \times 3}$

$(0,1,2,2)=(0,1,2,1,2,\cdots ,1,2)={\omega }^{{\omega }^2}$

$(0,1,2,2,1)={\omega }^{{\omega }^2+1}$

$(0,1,2,2,1,2)={\omega }^{{\omega }^2+\omega }$

$(0,1,2,2,1,2,1)={\omega }^{{\omega }^2+\omega +1}$

$(0,1,2,2,1,2,1,2)={\omega }^{{\omega }^2+\omega \times 2}$

$(0,1,2,2,1,2,2)=(0,1,2,2,1,2,1,2,\cdots ,1,2)={\omega }^{{\omega }^2*2}$

$(0,1,2,2,2)=(0,1,2,2,1,2,2,\cdots ,1,2,2)={\omega }^{{\omega }^3}$

$(0,1,2,3)=(0,1,2,2,\cdots ,2)={\omega }^{{\omega }^{\omega }}$

$(0,1,2,3,2)={\omega }^{{\omega }^{\omega +1}}$

$(0,1,2,3,2,3)={\omega }^{{\omega }^{\omega \times 2}}$

$(0,1,2,3,3)={\omega }^{{\omega }^{{\omega }^2}}$

$(0,1,2,3,4)=(0,1,2,3,3,\cdots ,3)={\omega }^{{\omega }^{{\omega }^{\omega }}}$

$(0,1,2,3,4,5,...)=\mathrm{L}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}={\epsilon }_0$

因此，$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$的增长率为${\epsilon }_0$

拓展

$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列有两种拓展：

• 高维PrSS，如PrSS原作者所创的BMS
• 阶差PrSS，有两种形式：
  • LPrSS及各种Hydra记号
  • HPrSS，0-Y，Y序列等复杂阶差型记号

它们以$\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$序列为基础，刻画了非常巨大的序数。

历史

在2014/08/14，Bashicu首次提出并使用Basic语言定义了PrSS.