バードの配列表記

​​

バードの配列表記
型	ハイパー次元
基本関数	ハイパー演算子

バードの配列表記とは、Chris Birdによって考案された巨大数論的表記法である 。これはJonathan Bowersの拡張配列表記の拡張で、歴史面からみても定義面からみてもBEAFと同族である。

「単純な」配列

線形および多次元配列

線形および多次元配列では、バードの配列表記はBEAFと同じである。

• Rule 1. 引数が1つか2つなら、\(\{a\} = a\), \(\{a,b\} = a^b\) (ところで、 \(\lbrace a \rbrace = a\) は \(\{a\} = \{a,1\} = a^1 = a\) として証明される。) (Rule 2の逆).
• Rule 2. もし最後の引数が1なら、それは削除できる: \(\{\# 1\} = \{\#\}\). (#記号は配列中の変わらない部分を表す。)
• Rule 3. もし2番目の引数が1なら、その値は最初の引数となる: \(\{a,1 \#\} = a\).
• Rule 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 \#\}\)

• Rule 5. それ以外は:

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

多次元配列では、Birdは\(\textrm` a \langle c \rangle b \textrm'\)を使った。これはBowersの\(b^c \& a\)と等価である。この文字列は引用記号中に書かれており、これらのルールを持つ:

• Rule A1. もし \(c = 0\)なら、 \(\textrm` a \langle 0 \rangle b = a \textrm'\)
• Rule A2. もし \(b = 1\)なら、 \(\textrm` a \langle c \rangle 1 = a \textrm'\)
• Rule A3. それ以外は、 \(\textrm` a \langle c \rangle b \textrm' = \textrm` a \langle c - 1 \rangle b [c] a \langle c \rangle (b - 1) \textrm'\)

そしてメインの規則は:

• Rule M1.もし引数が2つだけなら、 \(\{a, b\} = a^b\)
• Rule M2. もし \([m] < [n]\)ながら、 \(\{\# [m] 1 [n] \#\} = \{\# [n] \#\}\) (上のRule 2も含む)
• Rule M3. もし2番目の引数が 1なら、\(\{a,1 \#\} = a\)
• Rule M4. ゼロでない引数が満たされていないセパレータのすぐ後にあるなら:

  \(\{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. ゼロでない引数が満たされていないセパレータの後にあり、かつそれらの間に1のみの列があるなら:

  \(\{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. もし引数に複数の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 \#\}\)

• Rule M7. それ以外は:

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

例えば、{3,3 [3] 1 [2] 1,1,1,4} = {3 <3> 3 [3] 3 <2> 3 [2] 3,3,{3,2 [3] 1 [2] 1,1,1,4},3}

Birdは\([m]\)を次元セパレータとして用いている。Bowersの表記では\((m - 1)\)のセパレータとなる。これは、BEAFでは配列は1がデフォルトなのにセパレータは0がデフォルトになっている、という小さな問題を解決するためである。

急増加関数では、線形と多次元配列はそれぞれ\(\omega^\omega\) と \(\omega^{\omega^\omega}\)の極限を持つ。

超次元でネストされた配列

次に、かっこのセパレータが\([1, 1, 2]\)のような配列となる。Rule M1～M7は\([m_n]\) を \([m_n \#]\)と置き換えること以外は同じである。

山かっこに関するルールは修正が必要である。Rule A3はA4となり、新しいRule A3が追加される:

• Rule A3. もし各括弧中の最初の引数が0で、その後にゼロでない引数が存在したら:

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

これはRule M4ととても似ている。 次に文字列を配列中に含めることを許可し、ネストされた配列表記法を定義する。Rule A3をA4とし、A4をA5とする。新しいRule A3を追加し、A4を一般化する。

• Rule A3. もし \([A] < [B]\)なら、 \(\textrm` a <\# [A] 1 [B] \#> b \textrm' = \textrm` a <\# [B] \#> b \textrm'\)
• Rule A4.もし各括弧中の最初の引数が0で、その後にゼロでない引数が存在したら :

  \(\textrm` a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_n] c \# \rangle b \textrm' = \textrm` 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とM2に対して、どのセパレーターがより高いランクなのか決定する必要がある。最初に、配列が何重にネストされたかを表す関数をLev(A)と表記する。A=\(\{3,3[1[1[2]2]2]2\}\)とすると、Lev(A)=3となる。つまり[2]は[1[2]2]にネストされていて、それも[1[1[2]2]2]にネストされている。もう一つの関数、Num(H,A)を、配列A中のセパレータ[H]の個数と定義する。A = \(\{3,3[1[2]1[2]1[2]2]2]2\}\)なら、 Num(2,A) = 3。

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

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

超ネスト配列

逆斜線配列

ネスト配列表記の先に進むために、Bird は特殊なセパレータ[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}は、間違っている。

Birdはの表記法を逆斜線1つだけではなく、2つ以上、さらには逆斜線配列にも適用できるようにした。彼は[A]\を逆斜線配列Aとした。新しい規則を次のように定義した。

• Rule 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'\) (with b a's)

• Rule B2. 最初のゼロでない引数が逆斜線に先立っているなら:
  • \('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'\)

• Rule 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 [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\)

この表記の限界はフェファーマン・シュッテの順序数まで達する。

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

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個の逆斜線が挟まれる)

つぎに、Birdは[A]\を\([A \neg 2]\)と書き換え、前斜線を\([1 \neg 3]\)と書き換えることができるとした。だが、（この他の用途を考えると）\([1 \neg 3]\) を次のように定義する方がもっと使いやすい。

\(\{a,b [1 [1 \neg 3] 2] 2\} = \{a \langle 0 [1 \neg 3] \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \rangle\backslash b \cdots b \rangle b \rangle b \rangle b\}\) (中心から右にb+1個のb、そしてb-1この逆斜線が挟まれる)

そして、 \([A \neg 3]\) を \([1 \neg 3]\) と同様に \([1 A \neg 3]\)とする。 逆斜線は\([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、b-1個の\(\neg n-1\)が挟まれる)

一般化するため、 \([A \neg n]\)の定義を作らないといけない。 メインの規則は変える必要はなく、 山かっこ表記の規則は変える必要がある。

• Rule A1. 山括弧中の数字が0なら:

  \(\textrm`a \langle 0 \rangle b\textrm' = \textrm`a\textrm'\)

• Rule A2. b = 1なら:

  \(\textrm`a \langle A \rangle 1\textrm' = \textrm`a\textrm'\)

• Rule A3. [A] < [B]なら:

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

• Rule A4. 最初の引数が0でcが \([1 \neg n]\(n>1)の形で表されない通常のセパレータのすぐ後にあるなら:

  \(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] c \# \rangle b\textrm' = \textrm`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\textrm'\)

• Rule A5.最初の引数が0でcが逆斜線のすぐあとにあるなら:

  \(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 \backslash c \# \rangle b\textrm' = \textrm`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\textrm'\)

  • \(R_n = \textrm`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\textrm'\) (n>1)
  • \(R_1 = \textrm`0\textrm'\)
• Rule A6. もし最初の引数が0で c が\([1 \neg n]\) (n > 2)のすぐ後にあるなら:

  \(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 [1 \neg n] c \# \rangle b\textrm' = \textrm`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\textrm'\)

  • \(R = \textrm`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\textrm'\)
  • \(R_n = \textrm`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\textrm'\) (n>1)
  • \(R_1 = \textrm`0\textrm'\)
• Rule A7. それ以外は:

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

この表記の強さは \(\theta(\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\}\)とよくにている。これは\(\theta(\Omega^\omega)\)再帰関数である。これを一般化するために、Rule A2を定義し直す。

• Rule A2. 角括弧中に、セパレータのすぐ後に1がある時、
  • Case 1. 1は最後にあり、セパレータの後。

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

  • Case 2 1はセパレータと\(\neg\)に挟まれている。

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

  • Case 3 1は\(\neg\)のすぐ後。

    \(\textrm`a \langle \# \neg 1 \rangle b\textrm' = \textrm`a \langle \# \rangle b\textrm'\)

  • 次に、[A]と[B]を、[A]を[B]より低位、または[B]のみがハイパーセパレータという組とする。
  • Case 4 1はAとBに挟まれており、最後に\(\neg n\) の形の物はない。

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

  • Case 5 その他。

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

ここで、二つの#は同じとは限らない。これらの列の極限は大ヴェブレン順序数に達する。

関連項目

• H関数
• S関数
• U関数