鳥數陣記號

鳥數陣記號（英語：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