鸟数阵记号

鸟数阵记号（英语：Bird's array notation，缩写BAN，另称鸟之记号）是由克里斯·鸟所发明的大数记号。这是乔纳森·鲍尔斯所创之扩展数阵记号的扩展，并在历史和定义上与BEAF类似。

“简单”数阵

线性和多维数阵

在线性和多维数阵上，BAN和BEAF相同。

• 规则1. 如果只有1或2项，则\(\{a\} = a\), \(\{a,b\} = a^b\)（另外，\(\lbrace a \rbrace = a\)可从\(\{a,b\} = a^b\)推出，因为\(\{a\} = \{a,1\} = a^1 = a\)）（规则2的逆推）。
• 规则2. 如果尾项是1，可以将它去掉：\(\{\# 1\} = \{\#\}\)。（“#”表示数阵不变的部分）
• 规则3. 如果第2项是1，则数阵的值等于首项：\(\{a,1 \#\} = a\)。
• 规则4. 如果第3项是1：

  \(\{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 \#\}\)

• 规则5. 否则：

  \(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)

在多维数阵中，鸟使用\(a \langle c \rangle b\)这个记号，相当于鲍尔斯的\(b^c \& a\)，它的规则为：

• 规则A1. 如果\(c = 0\)，\(\textrm` a \langle 0 \rangle b = a \textrm'\)。
• 规则A2. 如果\(b = 1\)，\(\textrm` a \langle c \rangle 1 = a \textrm'\)。
• 规则A3. 否则，\(\textrm` a \langle c \rangle b \textrm' = \textrm` a \langle c - 1 \rangle b [c] a \langle c \rangle (b - 1) \textrm'\)。

主规则为：

• 规则M1. 如果只有2项，\(\{a, b\} = a^b\)。
• 规则M2. 如果\([m] < [n]\)，\(\{\# [m] 1 [n] \#\} = \{\# [n] \#\}\)。（包含上面的规则2）
• 规则M3. 如果第2项是1，\(\{a,1 \#\} = a\)。
• 规则M4. 如果第2项后有未填充分隔符，后面接着非1项：

  \(\{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) \#\}\)

• 规则M5. 如果第2项后有未填充分隔符跟一串1，后面接着非1项：

  \(\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] 1,1,\cdots,1,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,a,\cdots,a,R,c-1 \#\}\)

  其中\(R = \{a,b-1 [m_1] 1 [m_2] \cdots 1 [m_x] 1,1,\cdots,1,1,c \#\}\)

• 规则M6. 如果第2项后有一串1：

  \(\{a,b,1,1,\cdots,1,1,c \#\} = \{a,a,a,a,\cdots,a,\{a,b-1,1,1,\cdots,1,1,c-1 \#\},c-1 \#\}\)

• 规则M7. 上述规则不适用：

  \(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)

例如，{3,3 [3] 1 [2] 1,1,1,4} = {3 <2> 3 [3] 3 <1> 3 [2] 3,3,{3,2 [3] 1 [2] 1,1,1,4},3}。

鸟使用\([m]\)作为维度分隔符，相当于BEAF的\((m - 1)\)分隔符。在BEAF中，数阵的默认值为1，分隔符默认值为0，而鸟的方法解决了这个问题。

在快速增长阶层，线性和多维数阵分别对应极限序数\(\omega^\omega\)和\(\omega^{\omega^\omega}\)。

超维和嵌套数阵

接下来，可以允许分隔符变为数阵（如\([1, 1, 2]\)）。在规则M1至M7上，只要把\([m_n]\)改为\([m_n \#]\)即可，其他不变。

尖括号规则需要修改。规则A3变为A4，然后订定新的规则A3：

• 规则A3. 如果尖括号的首项是0，且后面有非1项：

  \(a \langle 0,1,1,\cdots,1,1,c \# \rangle b = a \langle b,b,b,\cdots,b,b,c-1 \# \rangle b\)

这条规则与规则M4类似。

下一步是容许分隔符内含有分隔符，由此制定嵌套数阵记号。规则A3、A4分别替换为A4、A5，然后订定新的规则A3、A4：

• 规则A3. 如果\([A] < [B]\)，\(a <\# [A] 1 [B] \#> b = a <\# [B] \#> b\)。
• 规则A4. 如果尖括号的首项是0，且后面有非1项：

  \(a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_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_n-1 \rangle b [A_n] c-1 \# \rangle b\)

A_n和B是数阵，而A_i-1跟A_i的差别，只在于首项减去1。

分隔符的层级比较

在规则A3和M2中，需要确定分隔符的层级。首先，制定数阵的嵌套层级，我们可以记为Lev(A)。例如，假设A = \(\{3,3 [1 [1 [2] 2] 2] 2\}\)，则Lev(A) = 3，因为最内层数阵[2]嵌套在[1 [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] 2\}\)，则Num(2,A) = 3。

假设我们要确定分隔符[A]和[B]哪个具有较高层级，则可以通过下列步骤：

1. 设[A₁]=[A], [A₂]=[A₁]和[B₁]=[B], [B₂]=[B₁]。
2. 如果Lev(A)>Lev(B)，则[A]>[B]，如果Lev(A)<Lev(B)，则[A]<[B]。如果Lev(A)=Lev(B)>0，则前往步骤3，否则跳到步骤6。
3. 设[A*]和[B*]是A₂和B₂中等级最高的分隔符。如果[A*]>[B*]则[A]>[B]，如果[A*]<[B*]则[A]<[B]，否则设[H]=[A*]=[B*]，然后前往步骤4。
4. 如果Num(H,A₂)>Num(H,B₂)，则[A]>[B]，如果Num(H,A₂)<Num(H,B₂)，则[A]<[B]，否则前往步骤5。
5. 在A₂和B₂中，删除最后的[H]分隔符及前面的所有项，然后回到步骤2。
6. 现在，A₂和B₂变为[a]和[b]，其中a和b是简单的数。所以，如果[a]<[b]，则[A]<[B]，如果[a]>[b]，则[A]>[B]，否则前往步骤7。
7. 在A₁和B₁中，除去最后一项和它前面的分隔符。如果A₁和B₁是空的，那么[A]=[B]，否则回到步骤2。

超嵌套数阵

反斜杠数阵

为了超越嵌套数阵记号，鸟定义了特殊的分隔符，[1 \ c]，具体定义如下：

• \(\{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 \rangle b \cdots \rangle b \backslash c-1 \rangle b \backslash c-1 \rangle b \backslash c-1 \rangle b\}\)（从中间到右边有b个b）
• \(\{a,b [A \backslash 1] 2\} = \{a,b [A] 2\}\)（A是任意数阵）

这个记号允许我们在反斜杠前套用一般数阵，如[1 [2] 2 \ 2]或[1 [1 \ 2] 2 \ 2]。反斜杠不能放在底层（外围无方括号的层级），例如{3, 3 \ 2}是不合法的。

鸟进一步将其扩展，除了单个反斜杠外，也可使用多个反斜杠，甚至是反斜杠阵。他用[A]\代表反斜杠阵A。有新的3个规则用来处理反斜杠阵：

• 规则B1. 如果反斜杠维度是0或1：
  • \(a \langle 0 \rangle\backslash b = a\)
  • \(a \langle 1 \rangle\backslash b = a \backslash a \backslash \cdots \backslash a \backslash a\)（b个a）

• 规则B2. 第一个非1项（首项不计入）前是反斜杠：
  • \(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-1} \backslash c-1 \# \rangle b\)
  • \(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\)
  • \(R_1 = b\)

• 规则B3. 否则：
  • \(a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_n]\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 b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [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\)

这个符号的限制是费佛曼-舒特序。

嵌套超嵌套数阵

2级超分隔符

现在，我们需要一个分隔符，用来表示任何级别的反斜杠嵌套。在鸟的文件“Beyond Bird's Nested Arrays I”中，他使用正斜杠来表示反斜杠的嵌套：

\(\{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\}\)（从中间到右边有b个b，而反斜杠有b-2个）

接下来，鸟指出分隔符[A]\（反斜杠阵A）可改写为\([A \neg 2]\)，因此我们能够把正斜杠写为\([1 \neg 3]\)。然而，为了更便于推广，\([1 \neg 3]\)的定义跟正斜杠有点不同，即：

\(\{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 \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}\)（从中间到右边有b+1个b，而反斜杠有b-1个）

然后，我们可以延伸\([1 \neg 3]\)到\([A \neg 3]\)，就像从反斜杠延伸到\([A \neg 2]\)。注意，反斜杠相当于\([1 \neg 2]\)分隔符。

因此，我们可以嵌套\(\neg 3\)，它的限制可以写为\([1 \neg 4]\)。不难看出这里的模式，可以由此定义\([1 \neg n]\)分隔符：

\(\{a,b [1 [1 \neg n] 2] 2\} = \{a \langle 0 [1 \neg n] \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\}\)（从中间到右边有b+1个b，而\(\neg n-1\)有b-1个）

一般来说，我们需要定义一套规则，使我们能够处理\([A \neg n]\)。我们不需要重写主规则，它们和嵌套数阵记号一样。只有尖括号规则需要改变。

• 规则A1. 尖括号的数字为0：

  \(a \langle 0 \rangle b = a\)

• 规则A2. b = 1：

  \(a \langle A \rangle 1 = a\)

• 规则A3. [A] < [B]：

  \(a \langle\# [A] 1 [B] \#\rangle b = a \langle\# [B] \#\rangle b\)

• 规则A4. 第一项是0，c前为正常分隔符（非\([1 \neg n]\)的分隔符，其中n > 1）：

  \(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\)

• 规则A5. 第一项是0，c前为反斜杠：

  \(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\)

  • \(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\) (n > 1)
  • \(R_1 = 0\)
• 规则A6. 第一项是0，c前为\([1 \neg n]\) (n > 2)：

  \(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\)

  • \(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\)
  • \(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\) (n > 1)
  • \(R_1 = 0\)
• 规则A7. 规则A1-A6不适用：

  \(a \langle c \# \rangle b = a \langle c-1 \# \rangle b [c] a \langle c \# \rangle b-1\).

这个符号的增长率达到\(\vartheta(\Omega^\omega)\)，即小凡勃伦序。

2级超分隔符数阵

我们定义\(\{a \langle 0 [1 \neg 1,2] 2 \rangle b\} = \{a \langle b [b \neg b] b \rangle b\}\)。它和\(\{a,b [1 \backslash 1, 2] 2\} = \{a \langle b \backslash b \rangle b\}\)非常相似。它的增长率为\(\vartheta(\Omega^\omega)\)。为了推广它，我们重新定义规则A2：

• 规则A2. 方括号中，如果分隔符后有1：
  • 情况1. 1是最后一项，在分隔符后：

    \(a \langle \# [ A ] 1 \rangle b = a \langle \# \rangle b\)

  • 情况2 1被夹在分隔符与\(\neg\)中：

    \(a \langle \# [ A ] 1 \neg n \rangle b = a \langle \# \neg n \rangle b\)

  • 情况3 1在\(\neg\)后：

    \(a \langle \# \neg 1 \rangle b = a \langle \# \rangle b\)

  • 接下来，如果[A]比[B]小，或者只有[B]是超分隔符：
  • 情况4 1夹在A和B中，并且最后不是\(\neg n\)：

    \(a \langle \# [ A ] 1 [ B ] \# \rangle b = a \langle \# [B] \# \rangle b\)

  • 情况5 否则：

    \(a \langle \# [ A ] 1 [ B ] \# \neg n \rangle b = a \langle \# [B] \# \neg n \rangle b\)

其中，两个#不一定相同。这个记号的极限是大凡勃伦序。

参见

• H函数
• S函数
• U函数
• BEAF
• 鸟数阵记号入门

外部链接

• Chris Bird's Super Huge Numbers