バードの配列表記

バードの配列表記（バードのはいれつひょうき）とは、クリス・バード（英:Chris Bird）によって考案された巨大数の表記法である。これはBEAFの拡張配列表記の拡張で、歴史的にも定義的にもBEAFと同族である。 線形配列では、バードの配列表記はBEAFと同じである。 Rule 1-1. { a } = a {\displaystyle \{a\}=a} Rule 1-2. { a , b } = a b {\displaystyle \{a,b\}=a^{b}} Rule 2. { # , 1 } = { # } {\displaystyle \{\#,1\}=\{\#\}} Rule 3. { a , 1 # } = a {\displaystyle \{a,1\#\}=a} Rule 4. { a , b , 1 , ⋯ , 1 ⏟ d , c , # } = { a , ⋯ , a ⏟ d + 1 , { a , b − 1 , 1 , ⋯ , 1 ⏟ d , c , # } , c − 1 , # } {\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. { a , b , c # } = { a , { a , b − 1 , c , # } , c − 1 # } {\displaystyle \{a,b,c\#\}=\{a,\{a,b-1,c,\#\},c-1\#\}} ただし # {\displaystyle \#} は配列の変わらない部分を指す。 線形配列では、急増加関数で { a , ⋯ , a ⏟ a } ≈ f ω ω ( a ) {\displaystyle \{\underbrace {a,\cdots ,a} _{a}\}\approx f_{\omega ^{\omega }}(a)} と近似される。 多次元配列では、配列の一部を ´ a < c > b ' {\displaystyle {\acute {}}a<c>b{\textrm {'}}} と表記する。線形配列と同様、BEAFと同じである。 Rule A1. ´ a < 0 > b ' = ´ a ' {\displaystyle {\acute {}}a<0>b{\textrm {'}}={\acute {}}a{\textrm {'}}} Rule A2. ´ a < c > 1 ' = ´ a ' {\displaystyle {\acute {}}a<c>1{\textrm {'}}={\acute {}}a{\textrm {'}}} Rule A3. ´ a < c > b ' = ´ a < c − 1 > b [ c ] a < c > ( b − 1 ) ' {\displaystyle {\acute {}}a<c>b{\textrm {'}}={\acute {}}a<c-1>b[c]a<c>(b-1){\textrm {'}}} Rule M1. { a , b } = a b {\displaystyle \{a,b\}=a^{b}} Rule M2. { # [ m ] 1 [ n ] # } = { # [ n ] # } ( m < n ) {\displaystyle \{\#[m]1[n]\#\}=\{\#[n]\#\}(m<n)} （これは上記のRule 2も含む） Rule M3. { a , 1 # } = a {\displaystyle \{a,1\#\}=a} Rule M4. { a , b [ m 1 ] 1 [ m 2 ] ⋯ 1 [ m x ] c # } = { a ⟨ m 1 ⟩ b [ m 1 ] a ⟨ m 2 ⟩ b [ m 2 ] ⋯ a ⟨ m x ⟩ b [ m x ] ( c − 1 ) # } {\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. { a , b [ m 1 ] 1 [ m 2 ] ⋯ 1 [ m x ] 1 , 1 , ⋯ , 1 , 1 , c # } = { a ⟨ m 1 ⟩ b [ m 1 ] a ⟨ m 2 ⟩ b [ m 2 ] ⋯ a ⟨ m x ⟩ b [ m x ] a , a , ⋯ , 1 , 1 , c − 1 # } {\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. { a , b , 1 , ⋯ , 1 ⏟ d , c , # } = { a , ⋯ , a ⏟ d + 1 , { a , b − 1 , 1 , ⋯ , 1 ⏟ d , c , # } , c − 1 , # } {\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. { a , b , c # } = { a , { a , b − 1 , c , # } , c − 1 # } {\displaystyle \{a,b,c\#\}=\{a,\{a,b-1,c,\#\},c-1\#\}} この配列は [ m ] {\displaystyle [m]} を次元セパレータとして用いている。 超次元配列では、括弧が [ 1 , 1 ] {\displaystyle [1,1]} のようになる。Rule M1~M7は、 [ m n ] {\displaystyle [m_{n}]} を [ m n # ] {\displaystyle [m_{n}\#]} に置き換えること以外は同じで、Rule A3はRule A5となり、新しいRule A3とRule A4が追加される。 Rule A3. ` a < # [ A ] 1 [ B ] # > b ' = ` < # [ B ] # > b ' ( A < B ) {\displaystyle {\grave {}}a<\#[A]1[B]\#>b{\textrm {'}}={\grave {}}<\#[B]\#>b{\textrm {'}}(A<B)} Rule A4. ` a ⟨ 0 [ A 1 ] 1 [ A 2 ] ⋯ 1 [ A n ] c # ⟩ b ' = ` a ⟨ b ⟨ A 1 − 1 ⟩ b [ A 1 ] b ⟨ A 2 − 1 ⟩ b [ A 2 ] ⋯ b ⟨ A n − 1 ⟩ b [ A n ] c − 1 # ⟩ b ' {\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 {'}}} AnとBは配列で、Ai-1 は Ai の最初の引数から1を引いて、残りは等しい配列である。 Rule A3とRule M2はよく似ているため、どのセパレーターがより高いランクなのか決定する必要がある。最初に、配列が何重にネストされたかを表す関数を L e v ( A ) {\displaystyle \mathrm {Lev} (A)} と表記する。例えば、 A = { 3 , 3 [ 1 [ 1 [ 2 ] 2 ] 2 ] 2 } {\displaystyle A=\{3,3[1[1[2]2]2]2\}} とすると、 L e v ( A ) = 3 {\displaystyle \mathrm {Lev} (A)=3} となる。つまり [ 2 ] {\displaystyle [2]} は [ 1 [ 2 ] 2 ] {\displaystyle [1[2]2]} にネストされていて、それも [ 1 [ 1 [ 2 ] 2 ] 2 ] {\displaystyle [1[1[2]2]2]} にネストされている。もう一つの関数、 N u m ( H , A ) {\displaystyle \mathrm {Num} (H,A)} を、配列 A {\displaystyle A} 中のセパレータ [ H ] {\displaystyle [H]} の個数と定義する。例えば、 A = { 3 , 3 [ 1 [ 2 ] 1 [ 2 ] 1 [ 2 ] 2 ] 2 ] 2 } {\displaystyle A=\{3,3[1[2]1[2]1[2]2]2]2\}} なら、 N u m ( 2 , A ) = 3 {\displaystyle \mathrm {Num} (2,A)=3} 。 [ A ] {\displaystyle [A]} と [ B ] {\displaystyle [B]} のどちらが優位なのかを決定する方法は、次のように表現される。 Step 1. [ A 1 ] = [ A ] , [ A 2 ] = [ A 1 ] , [ B 1 ] = [ B ] , [ B 2 ] = [ B 1 ] {\displaystyle [A_{1}]=[A],[A_{2}]=[A_{1}],[B_{1}]=[B],[B_{2}]=[B_{1}]} とする。 Step 2.もし L e v ( A ) > L e v ( B ) {\displaystyle \mathrm {Lev} (A)>\mathrm {Lev} (B)} なら、 [ A ] > [ B ] {\displaystyle [A]>[B]} 、 L e v ( A ) < L e v ( B ) {\displaystyle \mathrm {Lev} (A)<\mathrm {Lev} (B)} なら、 [ A ] < [ B ] {\displaystyle [A]<[B]} とする。 もし L e v ( A ) = L e v ( B ) > 0 {\displaystyle {\displaystyle \mathrm {Lev} (A)=\mathrm {Lev} (B)>0}} なら、Step 3へ、それ以外はStep 6へ。 Step 3. [ A ∗ ] {\displaystyle [A*]} と [ B ∗ ] {\displaystyle [B*]} をそれぞれ配列 [ A 2 ] {\displaystyle [A_{2}]} と [ B 2 ] {\displaystyle [B_{2}]} の最高位のセパレータとする。 もし [ A ∗ ] > [ B ∗ ] {\displaystyle {\displaystyle [A*]>\displaystyle [B*]}} なら [ A ] > [ B ] {\displaystyle {\displaystyle [A]>\displaystyle [B]}} 、 [ A ∗ ] < [ B ∗ ] {\displaystyle {\displaystyle [A*]<\displaystyle [B*]}} なら [ A ] < [ B ] {\displaystyle {\displaystyle [A]<\displaystyle [B]}} 、それ以外は [ H ] = [ A ∗ ] = [ B ∗ ] {\displaystyle [H]=[A*]=[B*]} としStep 4へ。 Step 4.もし N u m ( H , A 2 ) > N u m ( H , B 2 ) {\displaystyle \mathrm {Num} (H,A_{2})>\mathrm {Num} (H,B_{2})} なら、 [ A ] > [ B ] {\displaystyle [A]>[B]} 、 N u m ( H , A 2 ) < N u m ( H , B 2 ) {\displaystyle \mathrm {Num} (H,A_{2})<\mathrm {Num} (H,B_{2})} なら、 [ A ] < [ B ] {\displaystyle [A]<[B]} 、それ以外はStep 5へ。 Step 5. 文字列 A 2 {\displaystyle A_{2}} と B 2 {\displaystyle B_{2}} から、 [ H ] {\displaystyle [H]} のセパレータとその前の引数を削除する。 Step 6.これまでのルールで、 A 2 {\displaystyle A_{2}} と B 2 {\displaystyle B_{2}} は [ a ] {\displaystyle [a]} と [ b ] {\displaystyle [b]} ( a {\displaystyle a} と b {\displaystyle b} は単一の整数)の形になっているはずである。 もし [ a ] < [ b ] {\displaystyle [a]<[b]} なら [ A ] < [ B ] {\displaystyle [A]<[B]} 、 [ a ] > [ b ] {\displaystyle [a]>[b]} なら [ A ] > [ B ] {\displaystyle {\displaystyle [A]>\displaystyle [B]}} 、 それ以外はStep 7へ。 Step 7. A 1 {\displaystyle A_{1}} と B 1 {\displaystyle B_{1}} の最後の引数とその前のセパレータをすべて消去する。もし A 1 {\displaystyle A_{1}} と B 1 {\displaystyle B_{1}} がどちらも空ならば [ A ] = [ B ] {\displaystyle [A]=[B]} 、 それ以外はStep 2に戻る。