查看“︁BAN”︁的源代码

'''Bird 数组表示法'''（Bird's Array Notation,BAN）是由 Chris Bird 发明的一种大数记号。它是 [[BEAF]] 的扩展，无论是在历史上还是在定义上都类似于 BEAF，但与 BEAF 略有不同，使其更加“简单”。

== 定义 ==

=== “简单”数阵 ===

==== 线性和多维数阵 ====

* '''规则 1'''. 若有一或两个元素，则有 <math>\{a\} = a,\{a,b\} = a^b</math>
* '''规则 2'''. 若最后一个元素为 1，则可将其去掉：<math>\{\# 1\} = \{\#\}</math>
* '''规则 3'''. 若第二个元素为 1，则该数阵的值即为第一个元素：<math>\{a,1 \#\} = a</math>
* '''规则 4'''. 若第三个元素为 1：
<math>\{a,b,1,1,\cdots,1,1,c \#\} = \{a,a,a,a,\cdots,a,\{a,b-1,1,1,\cdots,1,1,c \#\},c-1 \#\}</math>
* '''规则 5'''. 其他情况：
<math>\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}</math>

对于多维数阵，Bird 使用 <math>a \langle c \rangle b</math>，它与 BEAF 的 <math>b^c \& a</math> 等价。这些字符串写在引号内，且有其特定的规则：

* '''规则 A1'''. 若 <math>c = 0</math>，则有 <math>a \langle 0 \rangle b = a</math>
* '''规则 A2'''. 若 <math>b = 1</math>，则有 <math>a \langle c \rangle 1 = a</math>
* '''规则 A3'''. 其他情况，<math>a \langle c \rangle b = a \langle c - 1 \rangle b [c] a \langle c \rangle (b - 1)</math>

主要规则如下：

* '''规则 M1'''. 若只有两个元素，则 <math>\{a, b\} = a^b</math>
* '''规则 M2'''. 若 <math>m<n</math>，则有 <math>\{\# [m] 1 [n] \#*\} = \{\# [n] \#*\}</math>（另外，<math>\{\# [a] 1\} = \{\#\}</math>）
* '''规则 M3'''. 若第二个元素为 1，则有 <math>\{a,1 \#\} = a</math>
* '''规则 M4'''. 若 <math>m_1 \geq 2</math> 且 <math>m_1 \geq \cdots \geq m_x</math>，则有
<math>\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] c \#\} = \{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] (c-1) \#\}</math>
* '''规则 M5'''. 若 <math>m_1 \geq \cdots \geq m_x \geq 2</math>，则有
<math>\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] 1,c \#\} = \{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] \{a,b-1 [m_1] 1 [m_2] \cdots 1 [m_x] 1,c \#\},c-1 \#\}</math>
* '''规则 M6'''. 若规则 M1-M5 均不适用，则 <math>\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}</math>

Bird 使用 <math>[m]</math> 作为维度分隔符；在 BEAF 中，它相当于一个 <math>(m-1)</math>。

==== 超维及嵌套数阵 ====
接下来，括号分隔符变为数阵（如 <math>[1, 1, 2]</math>）。除将 <math>[m_n]</math> 替换为 <math>[m_n \#]</math> 外，规则 M1 至 M6 保持不变。

尖括号规则需要一些修改。规则 A3 变为 A4，并新增规则 A3：

* '''规则 A3'''. 若尖括号中的第一个元素为零，且其后存在非零元素：
<math>a \langle 0,1,1,\cdots,1,1,c \# \rangle b = a \langle b,b,b,\cdots,b,b,c-1 \# \rangle b</math>

此规则在视觉上与规则 M4 相似。

下一步是允许在数阵内出现字符串，从而定义嵌套数阵表示法。规则 A3 变为 A4，规则 A4 变为 A5。然后我们新增一条 A3 规则并对 A4 进行推广：

* '''规则 A3'''. 若 <math>[A] < [B]</math>，则有 <math>a \langle\# [A] 1 [B] \#^*\rangle b = a \langle\# [B] \#^*\rangle b</math>
* '''规则 A4'''. 若尖括号中的第一个元素为零，且其后存在非零元素：
<math>a \langle 0 [x_1 \#_1] 1 [x_2 \#_2] \cdots 1 [x_n \#_n] c \# \rangle b = a \langle b \langle x_1-1 \#_1 \rangle b [x_1 \#_1] b \langle x_2-1 \#_2 \rangle b [x_2 \#_2] \cdots b \langle x_n-1 \#_n \rangle b [x_n \#_n] c-1 \# \rangle b</math>

A<sub>n</sub> 和 B 为数阵，且除第一个元素减一外，A<sub>i</sub>-1 与 A<sub>i</sub> 完全相同。

==== 两个分隔符的排序算法 ====
对于规则 A3 和 M2，确定哪个分隔符的层级更高十分重要。首先，将相互嵌套的数阵数量定义为数阵的嵌套层级。我们可以用 Lev(A) 表示。例如，若 A = {3,3[1[1[2]2]2]2}，则 Lev(A) = 3，因为 [2] 嵌套在 [1[2]2] 中，而[1[2]2]又嵌套在 [1[1[2]2]2] 中，最后 [1[1[2]2]2] 嵌套在主数阵中。非正式地说，Lev(A) 是我们需要说“嵌套”的次数，才能从最内层数阵说到主数阵。另一个函数 Num(H,A) 定义为数阵 A 中分隔符 [H] 的数量，例如，若 A = {3,3[1[2]1[2]1[2]2]2}，则 Num(2,A) = 3。

假设我们想要确定哪个分隔符的层级更高，[A] 还是 [B]。正式描述如下：

# 为进一步说明，设 [A<sub>1</sub>]=[A]，[A<sub>2</sub>]=[A<sub>1</sub>]，[B<sub>1</sub>]=[B]，[B<sub>2</sub>]=[B<sub>1</sub>]。
# 若 Lev(A)>Lev(B)，则得出 [A]>[B]；若 Lev(A)<Lev(B)，则 [A]<[B]。若 Lev(A)=Lev(B)>0，则进入步骤 3，否则进入步骤 6。
# 设 [A<sup>*</sup>] 和 [B<sup>*</sup>] 分别为数阵 A<sub>2</sub> 和 B<sub>2</sub> 中的最高层级分隔符。若 [A<sup>*</sup>]>[B<sup>*</sup>]，则 [A]>[B]；若 [A<sup>*</sup>]<[B<sup>*</sup>]，则 [A]<[B]；否则取 [H]=[A<sup>*</sup>]=[B<sup>*</sup>] 并进入步骤 4。
# 若 Num(H,A<sub>2</sub>)>Num(H,B<sub>2</sub>)，则 [A]>[B]；若 Num(A)>Num(B)，若 Num(H,A<sub>2</sub>)<Num(H,B<sub>2</sub>)，则 [A]<[B]；否则进入步骤 5。
# 在字符串 A<sub>2</sub> 和 B<sub>2</sub> 中，删除 [H] 分隔符并移除其之前的所有元素。
# 根据上述所有规则，字符串 A<sub>2</sub> 和 B<sub>2</sub> 必须为 [a] 和 [b] 的形式，其中 a 和 b 为单个数字。因此，若 a<b，则 [A]<[B]；若 a>b，则 [A]>[B]；否则进入步骤 7。
# 在字符串 A<sub>1</sub> 和 B<sub>1</sub> 中删除最后一个元素及其前的分隔符。若 A<sub>1</sub> 和 B<sub>1</sub> 为空，则得出 [A]=[B]；否则返回步骤 2。

=== 超嵌套数阵：反斜杠数阵 ===
为了突破嵌套数组表示法（Nested Array Notation）的局限，Bird 定义了一个特殊分隔符 [1\c]，具体定义如下：

* <math>\{a,b [1 \backslash c \#] 2\} = \{a \langle 0 \backslash c \# \rangle b\} = \{a \langle b \langle b \langle b \langle \cdots b \langle b \backslash c-1 \# \rangle b \backslash c-1 \# \cdots \rangle b \backslash c-1 \# \rangle b \backslash c-1 \# \rangle b \backslash c-1 \# \rangle b\}</math>（从中心向右有 b 个 b）
* <math>\{a,b [A \backslash 1] 2\} = \{a,b [A] 2\}</math>（若 A 为任意数阵）

这种表示法使我们能够构造出在反斜杠前带有数组的表达式，如 [1[2]2\2] 或 [1[1\2]2\2]。若将反斜杠置于基础层级（即不至少用一对方括号括起来），如{3,3\2}，则属于非法形式。

Bird 进一步扩展了该表示法，使其不仅能处理单一反斜杠的数组，还能处理包含多个反斜杠甚至反斜杠数组的情况。他用 [A]\ 来表示反斜杠周围的数阵 A。处理反斜杠数组时，有 3 条新规则：

* '''规则 B1'''. 反斜杠维度层级为 0 或 1：
** <math>a \langle 0 \rangle\backslash b = a</math>
** <math>a \langle 1 \rangle\backslash b = a \backslash a \backslash \cdots \backslash a \backslash a</math>（b 个 a）
* '''规则 B2'''. 反斜杠尖括号中的首项不为 0：
<math>a \langle c \# \rangle\backslash b = a \langle c-1 \# \rangle\backslash b [c \#]\backslash a \langle c-1 \# \rangle b \cdots [c \#]\backslash a \langle c-1 \# \rangle b</math>（b 个 <math>a \langle c-1 \# \rangle b</math>）
* '''规则 B3'''. 首个非零项位于单个反斜杠之前：
** <math>a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_n]\backslash 1 \backslash c \# \rangle b = a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_b \backslash c-1 \# \rangle b</math>
** <math>R_n = b \langle b \langle A_1' \rangle b [A_1]\backslash b \langle A_2' \rangle b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_{n-1} \backslash c-1 \# \rangle b</math>
** <math>R_1 = 0</math>
* '''规则 B4'''. 其他情况：
<math>a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_m]\backslash 1 [B_1] 1 [B_2] \cdots 1 [B_n] c \# \rangle b = a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash [A_2]\backslash \cdots b \langle A_n' \rangle\backslash [A_n]\backslash b \langle B_1' \rangle b [B_1] b \langle B_2' \rangle b [B_2] \cdots b \langle B_n' \rangle b [B_n] c-1 \# \rangle b</math>

=== 嵌套超嵌套数阵 ===

==== 2-超分离器 ====
目前，我们需要一种分隔符，其能力要强于嵌套反斜杠数阵的任何嵌套层级。在 Bird 的文章 Beyond Bird's Nested Arrays I 的结尾部分，Bird 提议使用正斜杠作为分隔符，具体如下：

<math>\{a,b [1 / 2] 2\} = \{a \langle 0 / 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}</math>（从中心向右有 b 个 b，则会导致添加 b-2 个反斜杠）

接下来，Bird 指出，分隔符 [A]\（即反斜杠数阵 A）可以重写为 <math>[A \neg 2]</math>，这使我们能够将正斜杠重写为 <math>[1 \neg 3]</math>。然而，为了进一步的目的，以下述方式定义 <math>[1 \neg 3]</math> 会更有用：

<math>\{a,b [1 [1 \neg 3] 2] 2\} = \{a \langle 0 [1 \neg 3] 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}</math>（从中心向右有 b+1 个 b，则会导致添加 b-1 个反斜杠）

然后，我们可以像处理反斜杠和 <math>[1 A \neg 3]</math> 那样，以相同的方式围绕 <math>[1 \neg 3]</math> 构建数组 <math>[A \neg 3]</math>。注意，反斜杠是 <math>[1 \neg 2]</math> 分隔符。

因此，我们可以创建嵌套数组，在它后添加 <math>\neg 3</math>，而所有这些的极限将是 <math>[1 \neg 4]</math>。要看出一般模式并定义 <math>[1 \neg n]</math> 分隔符并不难：

<math>\{a,b [1 [1 \neg n] 2] 2\} = \{a \langle 0 [1 \neg n] 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \neg n-1\rangle b \neg n-1\rangle b \cdots b \neg n-1\rangle b \neg n-1\rangle b \rangle b\}</math>（从中心向右有 b+1 个 b，<math>\neg n-1</math> 出现 b-1 次）

一般来说，我们需要定义一套规则，以便能够处理 <math>[A \neg n]</math>。我们无需重写主要规则（Main Rules），因为从嵌套数组表示法开始，这些规则将保持不变。只有尖括号规则（Angle Bracket Rules）会发生变化。

* '''规则 A1'''. 尖括号内的数字为 0：<math>a \langle 0 \rangle b = a</math>
* '''规则 A2'''. b=1：<math>a \langle A \rangle 1 = a</math>
* '''规则 A3'''. [A]<[B]：<math>a \langle\# [A] 1 [B] \#\rangle b = a \langle\# [B] \#\rangle b</math>
* '''规则 A4'''. 首项为 0，且在普通分隔符（非 <math>[1 \neg n]</math> 形式，其中 n>1）后紧跟着 c：
<math>a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] c \# \rangle b = a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] c-1 \# \rangle b</math>
* '''规则 A5'''. 首项为0，且在反斜杠后紧跟着 c：
** <math>a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 \backslash c \# \rangle b = a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_b \rangle b \backslash c-1 \# \rangle b</math>
** <math>R_n = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{n-1} \rangle b \backslash c-1 \# \rangle b</math>（n>1）
** <math>R_1 = 0</math>
* '''规则 A6'''. 首项为 0，且在 <math>[1 \neg n]</math> 后紧跟着 c（n>2）：
** <math>a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 [1 \neg n] c \# \rangle b = a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R \rangle b [1 \neg n] c-1 \# \rangle b</math>
** <math>R = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] R_b [1 \neg n] c-1 \# \rangle b</math>
** <math>R_n = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{b-1} \rangle b [1 \neg n] c-1 \# \neg n-1 \rangle b</math>
** <math>R_1 = 0</math>
* '''规则 A7'''. 若规则 A1-A6 均不适用，则 <math>a \langle c \# \rangle b = a \langle c-1 \# \rangle b [c \#] a \langle c \# \rangle b-1</math>

==== 2 超分隔符数组 ====
我们定义 <math>a \langle 0 [1 \neg 1,2] 2 \rangle b = a \langle b [b \neg b] b \rangle b</math>。

* '''规则 A1'''. 基础规则：
** <math>a \langle 0 \rangle b = a</math>
** <math>a \langle 0 \neg \# \rangle b = a</math>
* '''规则 A2'''. b=1：<math>a \langle A \rangle 1 = a</math>
* '''规则 A3'''. 移除尾随的 1 和更低的分隔符：
** <math>a \langle \# 1 \rangle b = a \langle \# \rangle b</math>
** <math>a \langle \# [A] 1 [B] \#^* \rangle b = a \langle \# [B] \#^* \rangle b</math>（当 [A]<[B]）

=== 嵌套超嵌套数阵表示法 ===

==== 尖括号规则 （BNA3） ====

==== 分层超嵌套数阵表示法（第 2 部分） ====

==== Bird 的分层超嵌套数阵表示法——尖括号规则 ====

=== 分层超嵌套数阵表示法 ===

==== Bird 的嵌套分层超嵌套数组表示法——尖括号规则 ====