BMS

Bashicu 矩阵系统（Bashicu Matrix System，BMS）是一个序数记号。Bashicu Hyudora 在 2018 年给出了它的定义。直至今日，BMS 依然是已经证明良序的最强的序数记号。

定义

原定义

Bashicu 最初在他的未命名的 BASIC 编程语言改版上提交了 BMS 的定义。BMS 的原定义是一个大数记号，理论的输出是一个大数。该程序并未设计为实际运行，原因在于语言修改的未定义性，同时也受限于内存与计算时间的现实约束，无法计算出这个大数的实际最终值。因此，Fish 编写了名为"Bashicu 矩阵计算器"的程序来演示预期的计算流程（该程序已得到 Bashicu 验证）。故 Bashicu 矩阵的正式定义可参考 Fish 程序的源代码。

正式定义

中文 googology 社区提到 BMS 默认是一个序数记号。以下是序数记号 BMS 的定义及说明：

首先是 BMS 合法式：BMS 的合法式是二维的自然数构成的序列，在外观上看是一个矩阵。如 $\left(\begin{array}{cccc}0& 1& 2& 1\\ 0& 1& 1& 1\\ 0& 1& 0& 1\end{array}\right)$ 就是一个 BMS 的合法式。在很多场合，这种二维的结构书写起来不是很方便，因此我们也常常把BMS从左到右、从上到下按列书写，每一列的不同行之间用逗号隔开，不同列之间用括号隔开。例如，上面的 BMS 也可以写成 $(0,0,0)(1,1,1)(2,1,0)(1,1,1)$。在很多情况下，除首列外，列末的 0 也可以省略不写，例如上面的 BMS 写为 $(0)(1,1,1)(2,1)(1,1,1)$。

理论上来说，只要是这样的式子就可以按照 BMS 的规则进行处理了。但实际操作过程中，我们还可以排除一些明显不标准的式子：

• 首列并非全 0
• 每一列并非不严格递减，即出现一列中下面的数大于上面的数
• 出现一个元素 a，它比它同行左边所有元素都大超过 1

在了解 BMS 的展开规则之前，需要先了解一些概念。

1. 第一行元素的父项：对于位于第一行的元素 a，它的父项 b 是满足以下条件的项当中，位于最右边的项：1. 同样位于第一行且在 a 的左边；2. 小于 a。这里和 PrSS 判定父项的规则是相同的。显然，0 没有父项。
2. 祖先项：一个元素自己，以及它的父项、父项的父项、父项的父项的父项……共同构成它的祖先项。
3. 其余行元素的父项：对于不位于第一行的元素 c，它的父项 d 指满足以下条件的项当中，位于最右边的项：1. 与c位于同一行且在 c 的左边；2. 小于 c；3. d 正上方的项 e 是 c 正上方的项f的祖先项。0 没有父项。
4. 坏根：最后一列位于最下方的非零元素的父项所在列，称为坏根。如果最后一列所有元素为 0，则这个 BMS 表达式无坏根。值得一提的是，末列最靠下的非零元素记作 LNZ（Lowermost Non-Zero）
5. 好部、坏部：这两个概念与 PrSS 是相似的。位于坏根左边的所有列称为好部，记作 G，G 可以为空；从坏根到倒数第二列(包括坏根、倒数第二列)的部分称为坏部，记作B。
6. 阶差向量：在一个 n 行 BMS 中，我们把末列记为 $({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_n)$，把坏根列记为 $({\beta }_1,{\beta }_2,\cdots ,{\beta }_n)$，并且我们规定 ${\alpha }_{n+1}=0$。则阶差向量$\mathrm{\Delta }=({\delta }_1,{\delta }_2,\cdots ,{\delta }_n)$按照这样的规则得到：${\delta }_i=\{\begin{array}{ll}{\alpha }_i-{\beta }_i,& {\alpha }_{i+1}\ne 0\\ 0,& {\alpha }_{i+1}=0\end{array}$。通俗的说，如果末列的第 $i+1$ 项等于0，则 ${\delta }_i=0$，否则 ${\delta }_i$ 等于末列第 i 行减去坏根列第 i 行。阶差向量记作 $\mathrm{\Delta }$。
7. $B_m$：$B_m$是 B 中每一列都加上 $\mathrm{\Delta }$ 的 m 倍所得到的新矩阵。但是有一点需要注意：如果 B 中某个元素 t 的祖先项不包含坏根中的元素，则在 $B_m$ 对应位置的元素的值依然是 t，它不加 $\mathrm{\Delta }$。

了解概念后，以下是 BMS 的展开规则：

1. 空矩阵 = 0
2. 如果表达式是非空矩阵 S，如果它没有坏根，那么 S 等于 S 去掉最后一列之后，剩余部分的后继 。
3. 否则，确定这个 BMS 表达式 S 的坏根、G、B、$\mathrm{\Delta }$，S 的基本列第 n 项$S[n]=G\sim B\sim B_1\sim B_2\sim B_3\sim \cdots \sim B_{n-1}$。其中 ~ 表示序列拼接。或者称 S 的展开式是 $G\sim B\underset{\omega }{\underbrace{\sim B_1\sim B_2\sim \cdots }}$。

BMS 的极限基本列是 $\{(0)(1),(0,0)(1,1),(0,0,0)(1,1,1),(0,0,0,0)(1,1,1,1),\cdots \}$，从这个基本列中元素开始取前驱或取基本列所能得到的表达式是 BMS 的标准式。

以下是 BMS 展开的一些实例：

例一：$(0,0,0)(1,1,1)(2,2,1)(3,2,0)(0,0,0)$

因为末列全都是 0，因此这个 BMS 没有坏根。根据规则 2，它是 $(0,0,0)(1,1,1)(2,2,1)(3,2,0)$ 的后继。

例二：$(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)$

LNZ 是末列第二行的 2。首先确定末列第 1 行元素的祖先项，即标红的部分（末列本身不染色，下同）：$(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)$。因此末列第二行的 2 的父项只能在含有标红元素的这些列中选取。于是确定 LNZ 的父项为（标绿）：$(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)$。因此确定 $(1,1,1)$ 是坏根。好部 G 是 $(0,0,0)$，坏部 B 是 $(1,1,1)(2,2,2)(3,3,3)$。计算出阶差向量 $\mathrm{\Delta }=(3,0,0)$。检查 B 中是否存在祖先项不包含坏根中元素的项（当然，我们只需要检查 $\mathrm{\Delta }$ 非零的那些行），很幸运，没有。于是我们得到展开式是 $(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,1,1)(5,2,2)(6,3,3)(7,1,1)(8,2,2)(9,3,3)\cdots$

例三：$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)(7,3,1,1)$

LNZ 是末列第四行的 1。首先确定末列第一行元素 7 的祖先项（标红）：$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)(7,3,1,1)$。在含有标红元素的列中寻找末列第二行元素 3 的祖先项（标绿）：$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)(7,3,1,1)$。在含有标绿元素的列中寻找末列第三行元素 1 的祖先项（标蓝）：$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)(7,3,1,1)$。在含有标蓝元素的列中寻找 LNZ 的父项，即首列第四行的 0。于是得到坏根是 $(0,0,0,0)$，好部 G 是空矩阵，坏部 B 是 $(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)$，计算阶差向量 $\mathrm{\Delta }=(7,3,1,0)$。检查 B 中是否存在祖先项不包含坏根中元素的项（只检查 $\mathrm{\Delta }$ 非 0 的行）得到第五列第三行的 0 祖先项不经过坏根。于是我们得到展开式是

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,2,1)(7,3,1,0)(8,4,2,1)(9,5,3,1)(10,6,2,1)(11,5,0,0)(12,4,2,1)(13,5,3,1)(14,6,2,0)(15,7,3,1)(16,8,4,1)(17,9,3,1)(18,8,0,0)(19,7,3,1)(20,8,4,1)\cdots$

展开 BMS 可以靠 Bashicu Matrix Calculator 或 Notation Explorer 辅助。

数学定义

kotetian 给出 BMS 的数学定义，但是他给出的定义是大数记号版本的。以下是根据他的定义改写的序数记号版 BMS 的定义：

$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}\mathrm{:}\mathit{S}={\mathit{S}}_0{\mathit{S}}_1\cdots {\mathit{S}}_{X-1}$

$\mathrm{V}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{:}{\mathit{S}}_x=(S_{x0},S_{x1},\cdots ,S_{x(Y-1)})$

$\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{f}{\mathit{S}}_{xy}:P_y(x)=\{\begin{array}{ll}max\{p|p<x\wedge {\mathit{S}}_{py}<{\mathit{S}}_{xy}\wedge \mathrm{\exists }a(p=(P_{y-1}{)}^a(x))\}& \text{if }y>0\\ max\{p|p<x\wedge {\mathit{S}}_{py}<{\mathit{S}}_{xy}\}& \text{if }y=0\end{array}$

$\mathrm{L}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{:}t=\max \{y|{\mathit{S}}_{(X-1)y}>0\}$

$\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{:}r=P_t(X-1)$

$\mathrm{A}\mathrm{s}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{:}{\mathrm{\Delta }}_y=\{\begin{array}{ll}{\mathit{S}}_{(X-1)y}-{\mathit{S}}_{ry}& \text{if }y<t\\ 0& \text{if }y\ge t\end{array}$

$\mathrm{A}\mathrm{s}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}\mathrm{:}{A}_{xy}=\{\begin{array}{ll}1& (\mathrm{i}\mathrm{f}\mathrm{\exists }a(r=(P_y{)}^a(r+x)))\\ 0& (\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e})\end{array}$

$\mathrm{G}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{:}\mathit{G}={\mathit{S}}_0{\mathit{S}}_1\cdots {\mathit{S}}_{r-1}$

$\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{:}{\mathit{B}}^{(a)}={\mathit{B}}_0^{(a)}{\mathit{B}}_1^{(a)}\cdots {\mathit{B}}_{X-2-r}^{(a)}$

${\mathit{B}}_x^{(a)}=(B_{x0}^{(a)},B_{x1}^{(a)},\cdots ,B_{x(Y-1)}^{(a)})$

$B_{xy}^{(a)}=S_{(r+x)y}+a{\mathrm{\Delta }}_y{A}_{xy}$

$\varnothing =0$

$\mathit{S}=\{\begin{array}{ll}{\mathit{S}}_0{\mathit{S}}_1{\mathit{S}}_2\cdots {\mathit{S}}_{X-2},& \text{if }\mathrm{\forall }y,{\mathit{S}}_{(X-1)y}=0\\ sup\{G,G{B}^{(0)},G{B}^{(0)}{B}^{(1)},G{B}^{(0)}{B}^{(1)}{B}^{(2)},\cdots \}& \text{otherwise}\end{array}$

历史

Bashicu 在2015年的时候给出了第一版 BMS 的定义，即 BM1。BM1 创建后的首个问题便是其是否必然终止。这一疑问直到 2016 年用户 KurohaKafka 在日本论坛 2ch.net 发表终止性证明才暂告段落。然而 Hyp cos 通过构造非终止序列推翻了该证明。

为此，Bashicu 发布第二版（BM2），以 BASIC 语言重新实现算法。2018年6月12日，他再次更新定义至 BM3，但当月内 Alemagno12 便发现存在不终止的例证。

2018 年 11 月 11 日，P進大好きbot 针对 PSS（即行数限制为 2 的 BMS）完成了终止性证明。

2018 年 8 月 28 日，Bubby3 确认 BM2 确实不会终止。

Bashicu 最终修正官方定义推出 BM4，此为2018 年 9 月 1 日的最新版本。该版本最终在 2023 年 7 月 12 日被 Racheline（在 googology 社区中曾用名 Yto）证明停机。

尽管 BM4 是最后官方修订版，但 googology 社区已衍生诸多非官方变体，如 BM2.2、BM2.5、BM2.6、BM3.1、BM3.1.1、BM3.2 及 PsiCubed2 版等。需注意的是，整数编号版本（1-4）均由 Bashicu 本人定义，其余版本均为他人修改。

由于 BMS 在三行之后出现提升效应造成分析上的极大困难，目前我们仍然在探索理想无提升 BMS（Idealized BMS，IBMS）的定义。BM3.3一度被认为是符合预期的 IBMS，然而目前已经发现了 BM3.3 也具有提升。

争议

test_alpha0 声称 Yto（Racheline）剽窃了他的证明。据t est_alpha0 所说，他在 2022 年 2 月 16 日在 googology wiki 上发布了关于 BMS 停机证明的文章，并在 googology discord 社区回答了相关问题，Racheline 声称他的证明不严谨，但过了一段时间，Racheline 在 ArXiv上发了证明，框架与 test_alpha0 的证明完全一致。目前尚不清楚 Racheline 的回应。

强度分析

主词条：BMS 分析，提升效应

BMS 的分析是一项浩大的工程，由于提升效应造成的困难。BMS的分析最初由Bubby3使用SAN进行，得出了$\text{lim(pDAN)}=(0,0,0)(1,1,1)(2,2,0)$，后来Yto接手了BMS的分析工作，使用稳定序数分析到了$(0,0,0)(1,1,1)(2,2,2)$。国内的YourCpper、bugit等人使用投影进行BMS分析，达到了$(0,0,0,0)(1,1,1,1)(2,2,1,1)(3,0,0,0)$以上，但这些分析是错误的。后来FENG发现并修正了两人的分析错误，最终完成了BMS与向上投影的分析工作。

这里列举出一些关键节点：

$\varnothing =0$

$(0)=1$

$(0)(0)=2$

$(0)(1)=\omega$

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

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

$(0,0)(1,1)={\epsilon }_0$

$(0,0)(1,1)(1,1)={\epsilon }_1$

$(0,0)(1,1)(2,0)={\epsilon }_{\omega }$

$(0,0)(1,1)(2,1)={\zeta }_0$

$(0,0)(1,1)(2,2)=\psi ({\mathrm{\Omega }}_2)$

$(0,0,0)(1,1,1)=\psi ({\mathrm{\Omega }}_{\omega })$

$(0,0,0)(1,1,1)(2,1,0)=\psi ({\mathrm{\Omega }}_{\omega }\times \mathrm{\Omega })$

$(0,0,0)(1,1,1)(2,1,0)(1,1,1)=\psi ({\mathrm{\Omega }}_{\omega }^2)$

$(0,0,0)(1,1,1)(2,1,1)=\psi ({\mathrm{\Omega }}_{{\omega }^2})$

$(0,0,0)(1,1,1)(2,1,1)(3,1,0)(2,0,0)=\psi (I)$

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

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

$(0,0,0)(1,1,1)(2,1,1)(3,1,1)(4,1,1)=\psi (K_{\omega })$

$(0,0,0)(1,1,1)(2,2,0)=\psi (psd.{\mathrm{\Pi }}_{\omega })$

$(0,0,0)(1,1,1)(2,2,1)=\psi ({\mathrm{\Pi }}_1(\lambda \alpha .({\mathrm{\Omega }}_{\alpha +2})-{\mathrm{\Pi }}_1))$

$(0,0,0)(1,1,1)(2,2,1)(3,0,0)=\psi (\lambda \alpha .({\mathrm{\Omega }}_{\alpha +\omega })-{\mathrm{\Pi }}_0)$

$(0,0,0)(1,1,1)(2,2,1)(3,2,1)=\psi ({\mathrm{\Pi }}_1(\lambda \alpha .(I_{\alpha +1})-{\mathrm{\Pi }}_1))$

$(0,0,0)(1,1,1)(2,2,1)(3,3,0)=\psi (\lambda \alpha .(\lambda \beta .\beta +1-{\mathrm{\Pi }}_1[\alpha +1])-{\mathrm{\Pi }}_1)$

$(0,0,0)(1,1,1)(2,2,2)=\psi (psd.\omega -\pi -{\mathrm{\Pi }}_0)=\psi ({\psi }_{\alpha }({\alpha }_{\omega }))$

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

$(0,0,0)(1,1,1)(2,2,2)(3,3,0)=\psi ({\psi }_{\alpha }({\psi }_{\beta }({\epsilon }_{{\alpha }_{\beta +1}+1})))$

$(0,0,0)(1,1,1)(2,2,2)(3,3,3)=\psi ({\beta }_{\omega })$

$(0,0,0,0)(1,1,1,1)=\psi (\omega -\text{Projection})=\psi ({\psi }_S(\sigma S\times \omega ))$

$(0,0,0,0)(1,1,1,1)(2,1,1,1)(3,1,0,0)(2,0,0,0)=\psi ((1,0)-\text{Projection})=\psi ({\psi }_S(\sigma S\times S))$

$(0,0,0,0)(1,1,1,1)(2,1,1,1)(3,1,1,1)=\psi ({\psi }_S(\sigma S\times S\times \omega ))$

$(0,0,0,0)(1,1,1,1)(2,2,0,0)=\psi ({\psi }_S(\sigma S\times S\times \omega +S_2))$

$(0,0,0,0)(1,1,1,1)(2,2,1,1)=\psi ({\psi }_S(\sigma S\times S\times \omega +{\psi }_{S_3}(\sigma S\times S\times \omega )))$

$(0,0,0,0)(1,1,1,1)(2,2,2,0)=\psi ({\psi }_S(\sigma S\times S\times \omega +S_{\omega }))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)=\psi ({\psi }_S(\sigma S\times S\times {\omega }^2))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,2,0,0)(4,3,0,0)=\psi ({\psi }_S({\epsilon }_{\sigma S+1}))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,2,2,0)=\psi ({\psi }_S(\sigma S_{\omega }))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,2,2,1)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(\sigma S_{\sigma \sigma S+1}^2+1)))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,0,0)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(\sigma \sigma S_2)))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,1,1)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(S_{\sigma \sigma S_2+1}+\sigma S_{\sigma \sigma S+1}\times (S+1)+\sigma S\times S\times \omega )))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,2,0)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(S_{\sigma \sigma S_2+1}+{\psi }_{\sigma \sigma S_2}(S_{\sigma \sigma S_2+1}+1))))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,2,1)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(S_{\sigma \sigma S_2+2}+1)))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,3,0)=\psi ({\psi }_S({\psi }_{\sigma \sigma S}(\sigma \sigma S_{\omega })))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,3,1)=\psi ({\psi }_S(\sigma \sigma S\times \omega ))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,3,1)(4,0,0,0)=\psi ({\psi }_S(\sigma \theta S\times \omega ))$

$(0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,3,1)(4,4,4,0)=\psi ({\psi }_S({\psi }_{\sigma \sigma \theta S}(\sigma \sigma \theta S_{\omega })))$

$(0,0,0,0)(1,1,1,1)(2,2,2,2)=\psi ({\psi }_X(\theta X\times \omega ))$

$(0,0,0,0,0)(1,1,1,1,1)=\psi ({\psi }_H(H^{H^{\omega }}))$

$\text{Limit}=\psi ({\psi }_H({\epsilon }_{H+1}))$

$(0,0,0,0)(1,1,1,1)$被命名为 TSSO（Trio Sequence System Ordinal，三行序列系统序数），$(0,0,0,0,0)(1,1,1,1,1)$被命名为 QSSO（Quardo Sequence System Ordinal，四行序列系统序数）。BMS 的极限在中文 googology 社区被称为 SHO（Small Hydra Ordinal），但这一命名的起源不明（SHO 最早被用来指代 ${\epsilon }_0$，后来不明不白的变成了 BMS 极限），也是非正式的，因此被部分人拒绝使用。也有人称 BMS 极限为 BMO。