バードの配列表記

バードの配列表記（バードのはいれつひょうき）とは、クリス・バード（英:Chris Bird）によって考案された巨大数の表記法である。これはBEAFの拡張配列表記の拡張で、歴史的にも定義的にもBEAFと同族である。^[1]

線形配列

線形配列では、バードの配列表記はBEAFと同じである。

Rule 1-1.${\displaystyle \{a\}=a}$

Rule 1-2.${\displaystyle \{a,b\}=a^{b}}$

Rule 2.${\displaystyle \{\#,1\}=\{\#\}}$

Rule 3.${\displaystyle \{a,1\#\}=a}$

Rule 4.${\displaystyle \{a,b,\underbrace {1,\cdots ,1} _{d},c,\#\}=\{\underbrace {a,\cdots ,a} _{d+1},\{a,b-1,\underbrace {1,\cdots ,1} _{d},c,\#\},c-1,\#\}}$

Rule 5.${\displaystyle \{a,b,c\#\}=\{a,\{a,b-1,c,\#\},c-1\#\}}$

ただし${\displaystyle \#}$は配列の変わらない部分を指す。

線形配列では、急増加関数で${\displaystyle \{\underbrace {a,\cdots ,a} _{a}\}\approx f_{\omega ^{\omega }}(a)}$と近似される。^[2]

多次元配列

多次元配列では、配列の一部を${\displaystyle {\acute {}}a<c>b{\textrm {'}}}$と表記する。線形配列と同様、BEAFと同じである。

Rule A1.${\displaystyle {\acute {}}a<0>b{\textrm {'}}={\acute {}}a{\textrm {'}}}$

Rule A2.${\displaystyle {\acute {}}a<c>1{\textrm {'}}={\acute {}}a{\textrm {'}}}$

Rule A3.${\displaystyle {\acute {}}a<c>b{\textrm {'}}={\acute {}}a<c-1>b[c]a<c>(b-1){\textrm {'}}}$

Rule M1.${\displaystyle \{a,b\}=a^{b}}$

Rule M2.${\displaystyle \{\#[m]1[n]\#\}=\{\#[n]\#\}(m<n)}$（これは上記のRule 2も含む）

Rule M3.${\displaystyle \{a,1\#\}=a}$

Rule M4.${\displaystyle \{a,b[m_{1}]1[m_{2}]\cdots 1[m_{x}]c\#\}=\{a\langle m_{1}\rangle b[m_{1}]a\langle m_{2}\rangle b[m_{2}]\cdots a\langle m_{x}\rangle b[m_{x}](c-1)\#\}}$

Rule M5.${\displaystyle \{a,b[m_{1}]1[m_{2}]\cdots 1[m_{x}]1,1,\cdots ,1,1,c\#\}=\{a\langle m_{1}\rangle b[m_{1}]a\langle m_{2}\rangle b[m_{2}]\cdots a\langle m_{x}\rangle b[m_{x}]a,a,\cdots ,1,1,c-1\#\}}$

Rule M6.${\displaystyle \{a,b,\underbrace {1,\cdots ,1} _{d},c,\#\}=\{\underbrace {a,\cdots ,a} _{d+1},\{a,b-1,\underbrace {1,\cdots ,1} _{d},c,\#\},c-1,\#\}}$

Rule M7.${\displaystyle \{a,b,c\#\}=\{a,\{a,b-1,c,\#\},c-1\#\}}$

この配列は${\displaystyle [m]}$を次元セパレータとして用いている。

超次元配列

超次元配列では、括弧が${\displaystyle [1,1]}$のようになる。Rule M1~M7は、${\displaystyle [m_{n}]}$を${\displaystyle [m_{n}\#]}$に置き換えること以外は同じで、Rule A3はRule A5となり、新しいRule A3とRule A4が追加される。

Rule A3.${\displaystyle {\grave {}}a<\#[A]1[B]\#>b{\textrm {'}}={\grave {}}<\#[B]\#>b{\textrm {'}}(A<B)}$

Rule A4.${\displaystyle {\grave {}}a\langle 0[A_{1}]1[A_{2}]\cdots 1[A_{n}]c\#\rangle b{\textrm {'}}={\grave {}}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{\textrm {'}}}$

A_nとBは配列で、A_i-1 は A_i の最初の引数から1を引いて、残りは等しい配列である。

二つのセパレータの順序付け

Rule A3とRule M2はよく似ているため、どのセパレーターがより高いランクなのか決定する必要がある。最初に、配列が何重にネストされたかを表す関数を${\displaystyle \mathrm {Lev} (A)}$と表記する。例えば、${\displaystyle A=\{3,3[1[1[2]2]2]2\}}$とすると、${\displaystyle \mathrm {Lev} (A)=3}$となる。つまり${\displaystyle [2]}$は${\displaystyle [1[2]2]}$にネストされていて、それも${\displaystyle [1[1[2]2]2]}$にネストされている。もう一つの関数、${\displaystyle \mathrm {Num} (H,A)}$を、配列${\displaystyle A}$中のセパレータ${\displaystyle [H]}$の個数と定義する。例えば、${\displaystyle A=\{3,3[1[2]1[2]1[2]2]2]2\}}$ なら、 ${\displaystyle \mathrm {Num} (2,A)=3}$。

${\displaystyle [A]}$と${\displaystyle [B]}$のどちらが優位なのかを決定する方法は、次のように表現される。

• Step 1. ${\displaystyle [A_{1}]=[A],[A_{2}]=[A_{1}],[B_{1}]=[B],[B_{2}]=[B_{1}]}$とする。
• Step 2.もし${\displaystyle \mathrm {Lev} (A)>\mathrm {Lev} (B)}$なら、${\displaystyle [A]>[B]}$、 ${\displaystyle \mathrm {Lev} (A)<\mathrm {Lev} (B)}$なら、${\displaystyle [A]<[B]}$とする。 もし${\displaystyle {\displaystyle \mathrm {Lev} (A)=\mathrm {Lev} (B)>0}}$なら、Step 3へ、それ以外はStep 6へ。
• Step 3.${\displaystyle [A*]}$と${\displaystyle [B*]}$をそれぞれ配列${\displaystyle [A_{2}]}$と${\displaystyle [B_{2}]}$の最高位のセパレータとする。 もし${\displaystyle {\displaystyle [A*]>\displaystyle [B*]}}$なら${\displaystyle {\displaystyle [A]>\displaystyle [B]}}$、${\displaystyle {\displaystyle [A*]<\displaystyle [B*]}}$なら${\displaystyle {\displaystyle [A]<\displaystyle [B]}}$、それ以外は${\displaystyle [H]=[A*]=[B*]}$としStep 4へ。
• Step 4.もし${\displaystyle \mathrm {Num} (H,A_{2})>\mathrm {Num} (H,B_{2})}$なら、${\displaystyle [A]>[B]}$、${\displaystyle \mathrm {Num} (H,A_{2})<\mathrm {Num} (H,B_{2})}$なら、${\displaystyle [A]<[B]}$、それ以外はStep 5へ。
• Step 5. 文字列${\displaystyle A_{2}}$と${\displaystyle B_{2}}$から、${\displaystyle [H]}$のセパレータとその前の引数を削除する。
• Step 6.これまでのルールで、${\displaystyle A_{2}}$と${\displaystyle B_{2}}$は${\displaystyle [a]}$と${\displaystyle [b]}$(${\displaystyle a}$と${\displaystyle b}$は単一の整数)の形になっているはずである。 もし${\displaystyle [a]<[b]}$なら${\displaystyle [A]<[B]}$、${\displaystyle [a]>[b]}$なら${\displaystyle {\displaystyle [A]>\displaystyle [B]}}$、 それ以外はStep 7へ。
• Step 7.${\displaystyle A_{1}}$と${\displaystyle B_{1}}$の最後の引数とその前のセパレータをすべて消去する。もし${\displaystyle A_{1}}$と${\displaystyle B_{1}}$がどちらも空ならば${\displaystyle [A]=[B]}$、 それ以外はStep 2に戻る。^[2]

超ネスト配列

ネストされた超ネスト配列