iBLP

记号简介

无限基本Laver图案(Infinite Basic Laver Pattern)是由test_alpha0的记号Basic Laver Pattren改造而来。IBLP目前尚不理想，还存在许多的坏图案，test_alpha0规定其极限表达式为(1,0)1(2,1,0)1(3,2,1,0)2(4,3,2)1(5,4,3,2)2(6,5,4)1。尽管如此，IBLP仍然被认为是目前最强的记号。本页面介绍的规则对应NE上的DEN2。

定义

定义1 （IBLP）

一个IBLP是一个四元组 $A = (n, (A_{1}, \dots, A_{n}), (l_{1}, \dots, l_{n}), (M_{1}, \dots, M_{n}))$ ，

其中：

$(1) n \in ℕ$ 。

$(2)$ 对每个 $i \in {1, \dots, n}$ ， $A_{i}$ 是严格递增的非负整数序列，满足 $l e n (A_{i}) \geq 2 且 \max (A_{i}) = i$ 。

$(3)$ 对每个 $i \in {1, \dots, n}$ ，步长 $l_{i} \in ℕ$ 。

$(4)$ 对每个 $i \in {1, \dots, n}$ ，标记集合 $M_{i} \subseteq A_{i}$

约定所有编号从 1 开始； $A_{i} [k]$ 表示第 k 个元素， $A_{i} [- j] = A_{i} [l e n (A_{i}) - j + 1]$ 表示倒数第 j 个元素。

定义2 （长行、中等行、短行）

行 $i$ 称为长行若 $l e n (A_{i}) > 2 l_{i}$ ，称为中等行若 $l e n (A_{i}) = 2 l_{i}$ ，称为短行若 $l e n (A_{i}) < 2 l_{i}$ 。

定义3 （零图案、后继图案、极限图案）

若 n = 0，称 A 为零图案。若 $n > 0 且 l e n (A_{n}) = 2 且 \min (A_{n}) = 0$ ，称 A 为后继图案。否则称 A 为极限图案。

定义4 （行比较键）

令 $A_{i} = (A_{1} < a_{2} < \dots < a_{m}) 且 L = l_{i}$ 。定义保留序列

$K_{i} = {\begin{cases} (a_{1}, a_{2}, \dots, a_{m}), & L \leq 1; \\ (a_{1}, a_{L + 1}, a_{L + 2}, \dots, a_{m}), & 2 \leq L \leq m; \\ (a_{1}, a_{2}, \dots, a_{m}), & L \geq 2 且 m < L . \end{cases}$

定义行键为 $\overset{\leftarrow}{K_{i}}$ （即 $K_{i}$ 逆序，从大到小）。

定义5 （IBLP的大小比较）

给定两个 IBLP $A 、 B$ ，从 $i = 1$ 起逐行比较其

行键 $\overset{\leftarrow}{K_{i} (A)} 与 \overset{\leftarrow}{K_{i} (B)}$ 的字典序；第一处不同决定大小。若前 $\min (n_{a}, n_{b})$ 行都相等，则行数较小者更小。

定义6 （一行的根 $p (i)$ ）

对 $i \in {1, \dots, n}$ ，定义 $p (i) = A_{i} [- (l_{i} + 1)]$ .

定义7 （传递序列 $t r_{i} (j)$ ）

固定行 i。若 $j = A_{i} [k] (1 \leq k \leq l e n (A_{i})) 且 k \geq l_{i}$ ，定义阈值 $θ = A_{i} [k - l_{i}]$ 。令 $t_{0} = j$ ，并在 $t_{m} > θ 且 p (t_{m}) 有定义$ 时令 $t_{m + 1} = p (t_{m})$ 。若存在最小 $m > 0$ 使 $t_{m} = θ$ ，则定义 $t r_{i} (j) = (t_{0}, t_{1}, \dots, t_{m})$ ，否则称 $t r_{i} (j)$ 无定义。若 $k \leq l_{i}$ ，亦称无定义。

定义8 （部分函数 $f_{A}$ ）

设 A 非零且有至少1行。令 $a_{1} = A_{n} [1] = \min (A_{n}) ， L = l_{n} ， p = p (n) = A_{n} [- (L + 1)]$ 。定义部分函数 $f_{A} : ℕ ⇀ ℕ$ ：

$(1)$ 若 $x < a_{1}$ ，则 $f_{A} (x) = x$ ；

$(2)$ 若 $x = A_{n} [k] 且 x < p 且 k + L \leq l e n (A_{n})$ ，则 $f_{A} (x) = A_{n} [k + L]$ ；

$(3)$ 若 $x \geq p$ ，则 $f_{A} (x) = x + n - p$ ；

$(4)$ 其余情形 $f_{A} (x)$ 无定义。

定义9 （copy 的行与步长）

设 A 行数为 $n \geq 1$ ，令 $p = p (n)$ 。若 copy 过程中出现 $f_{A} (x)$ 无定义，则 $c o p y (A)$ 无定义。否则定义 $A^{'} = c o p y (A)$ 行数为 $n^{'} = 2 n - p$ ，满足：

$(1)$ 对 $1 \leq i \leq n - 1 ： {A_{i}}^{'} = A_{i} ， {l_{i}}^{'} = l_{i} ， {M_{i}}^{'} = M_{i}$ ；

$(2)$ 对每个 $i \in {1, \dots, n - p + 1}$ ，令源行 $σ = p + i - 1$ ，目标行 $τ = n - 1 + i$ i，定义 ${A_{τ}}^{'} = s o r t ({f_{A} (x) | x \in A_{σ}}) ， {l_{τ}}^{'} = l_{σ}$ ，要求 $\forall x \in A_{σ} ， f_{A} (x) 有定义$ 。

定义10 （copy的标记过滤）

延续上一定义。对目标行 $τ$ 中元素 $x \in {A_{τ}}^{'}$ ，令

$y \in A_{σ}$ 为其唯一来源（即 $f_{A} (y) = x$ ）。则 $x \in {M_{τ}}^{'}$ 当且仅当：

$y \in M_{σ}$ ，并且满足下列之一：

$t r_{σ} (y)$ 有定义且 $t r_{σ} (y) [- 2] \geq p$ ；
令 $y_{0}$ 为 $t r_{σ} (y)$ 中首次出现的 $< p$ 的元素（等价于“最大的

$< p$ 的元素”）。要么 $y_{0} < a_{1}$ ；要么存在 k 使 $y_{0} = A_{n} [k] 且 k + L \leq l e n (A_{n}) 且 A_{n} [k + L] \in M_{n}$ ，并且若 x 在 ${A_{τ}}^{'}$ 中的位置为 q（从 1 开始），则当 $q + 1 - l_{σ} \geq 1$ 时需满足 ${A_{τ}}^{'} [q + 1 - l_{σ}] \leq a_{1} .$

定义11 （E(A,0)）

若 A 非零且 n ≥ 1，则 E(A, 0) 为删除最后一行后的图案（行数变为 n − 1，其余行、步长、标记保持不变）。

定义12 （E(A, m)的copy阶段 (m≥1)）

设A是极限图案。令 $A^{(0)} = A$ 。若第一次 $c o p y (A^{(0)})$ 无定义，则称 A 为坏图案并定义 $E (A, m) = E (A, 0)$ 。否则定义

$A^{(1)} = c o p y (A^{(0)}), A^{(2)} = c o p y (A^{(1)}), \dots, A^{(m)} = c o p y (A^{(m - 1)})$ ,

并令 $B = E (A^{(m)}, 0)$

接下来对B做补全，初始行号 $r = n$ （这里 n 为原始 A 的行数）。补全过程允许使用临时记录映射 $R e c$ （行号 $\mapsto$ 有限序列），结束后丢弃。

定义13 （标记补全）

固定当前行 r。令 $ℬ = {b \in M_{r} | b \in A_{r}}$ 并按升序枚举其元素 $b_{1} < b_{2} < \dots < b_{k}$ （该集合在本轮开始时冻结，新产生标记不加入本轮）。对每个 $b_{i}$ 依次：

$(1)$ 若 $t r_{i} (b_{i})$ 无定义则跳过；

$(2)$ 令 $t = t r_{r} (b_{i}) [- 2]$ 。若 $R e c (t)$ 不存在或为空则跳过，否则记 $s = R e c (t)$ ；

$(3)$ 若对所有 $j = 3, 4, \dots, l e n (t r_{r} (b_{i}))$ 都有 $t r_{r} (b_{i}) [- j + 1] + 1 \in A_{t r_{r} (b_{i}) [- j]}$ ，那么把s 及 $b_{i} + 1, b_{i} + 2, \dots, b_{i} + l e n (s)$ 加入 $A_{r}$ ，并重新排序去重使

之严格递增。更新标记：s 中元素不标记， $b_{i} + 1, b_{i} + 2, \dots, b_{i} + l e n (s)$ 全标

记，其余标记保留（按上述规则修正）。更新步长： $l_{r} = l_{r} + l e n (s)$ 。

定义14 （原生补全）

固定当前行 r。若 $A_{r}$ 为长行，则原生补全不执行并返回 0。否则令 $p_{r} = p (r) = A_{r} [- (l_{r} + 1)] ， a = A_{r} [- l_{r}]$ .

构造序列 s：令 $u_{0} = a$ ，并在 $A_{u_{m}} [- 2]$ 存在且 $> p_{r}$ 时令 $u_{m + 1} = A_{u_{m}} [- 2]$ 并把 $u_{m + 1}$ 追加到 s，直至无法继续。令 $t = l e n (s)$ 。若 $t = 0$ 返回 0；若 $t > 0$ ，令 $R e c (r) = s$ 并继续：

$(1)$ 在 r 后插入 t 行，使原本行号 $> r$ 的行号整体加 t；

$(2)$ 仅对原本行号 $> r$ 的那些行，在其中把所有 $> r$ 的元素加 t，并同步

标记集合，步长不变；

$(3)$ 令旧行及旧步长为 $A_{r}^{o l d}, l_{r}^{o l d}$ 。将旧行替换为 t + 1 行：

$A_{r + t} = s o r t (A_{r}^{o l d} \cup s \cup {r + 1, r + 2, \dots, r + t}) ， l_{r + t} = l_{r}^{o l d} + t$ .

标记规则：除s和r+t外均标记。

$(4)$ 对 $i = t, t - 1, \dots, 1$ ，由 $A_{r + i}$ 构造 $A_{r + i - 1}$ ：删除元素 $r + i$ ，并删除元素 $A_{r + i} [- l_{r + i}]$ ，去除 $r + i - 1$ 的标记，并令 $l_{r + i - 1} = l_{r + i} - 1$ 。

$(5)$ 中等行例外：若 $i = t$ 且 $A_{r}^{o l d}$ 为中等行，则在构造 $A_{r + i - 1}$ 时不删除 $A_{r + i} [- l_{r + i}]$ 且不减步长（令 $l_{r + i - 1} = l_{r + i}$ ），但仍删除 $r + i$ 并去除 $r + i - 1$ 的标记。

原生补全返回t。

定义15 （补全主循环(用于 E(A, m))）

令初始 $r = n$ （n 为原始 A 的行数）。当 r 不超过当前 B 的行数时循环：先对行 r 执行标记补全，再执行原生补全得到 t，然后更新 $r = r + t + 1$ 。当 r 越界时补全结束，丢弃 $R e c$ ，所得 B 即为 $E (A, m)$ 。