配列表記

配列表記の規則は次の通りである。

• 1つ組の場合は${\displaystyle \{a\}=a}$、2つ組の場合は${\displaystyle \{a,b\}=a^{b}}$となる。
• 最後の数字が1の時はこれを落とせる。${\displaystyle \{a,b,c,...,y,z,1\}=\{a,b,c,...,y,z\}}$
• 2番目の数字が1の時はそれ以降を全て落とせる。${\displaystyle \{a,1,b,c,...,y,z\}=\{a\}=a}$

ここまではチェーン表記と同じだが、ここからが異なり、これが効率良く爆発させることができる要因となっている。

• 3番目の数字が1の時であるが、チェーン表記のようにそれ以降を全て落とすのではなく、式で表すと次のようになる。
  • ${\displaystyle \{a,b,1,...(n{\text{個 の 1}})...,1,c,...,y,z\}=\{a,a,...(n+1{\text{個 の }}a)...,a,\{a,b-1,1,...(n{\text{個 の 1}})...,1,c,...,y,z\},c-1,...,y,z\}}$
  • つまり、2番目の要素は先頭の要素に置き換わり、3番目以降に連続する1のうち最も右側のもの以外は全て先頭の要素に置き換わり、その最も右側のものは元の配列表記の2番目の要素を1引いた配列に置き換わり、その次の要素の値が1減るという、複雑な規則で変形する。
  • これは4番目以降の数字を減らす唯一のルールである。
• 上のいずれでもない時、次のように変形する。
  • ${\displaystyle \{a,b,c,...,y,z\}=\{a,\{a,b-1,c,...,y,z\},c-1,...,y,z\}}$　つまり、2番目の要素に元の配列の2番目の要素を1引いた配列を入れ、3番目の要素から1を引く。
  • チェーン表記が右側から変形していくのに対し、こちらは左側から変形していく。
  • なお、4番目以降の数字が1の時も、こちらの変形を適用する。

3つ組の配列表記は、3つ組チェーンと一致し、したがってクヌースの矢印表記とも一致するという性質がある。すなわち式で書くと${\displaystyle \{a,b,c\}=a\rightarrow b\rightarrow c=a\uparrow ^{c}b}$となる。

4つ組以上の配列表記によって巨大数を記述する場合は、先頭の要素は3以上とする必要がある。なぜなら、先頭が1であれば、その値は1となり、4つ組以上の配列表記で先頭の要素が2であれば、その値は2番目の要素が1でない限り必ず4になってしまうからである。後者の詳細は次の通りである：

{2,b,c,d,…,z}

＝{2,{2,b-1,c,d,…, z},c-1,d,…,z}

＝…

＝{2,X,1,d,…,z} (Xはある数)

＝{2,2,{2,X-1,1,d,…,z},d-1,…,z}

＝{2,2,Y,d-1,…,z} (内側の配列をYと置く)

＝{2,{2,1,Y,d-1,…,z},Y-1,d-1,…,z}

＝{2,2,Y-1,d-1,…,z}

＝{2,2,Y-2,d-1,…,z}

＝{2,2,1,d-1,…,z}

＝{2,2,1,1,…,z}

＝{2,2,1,1,…,1}

＝{2,2}

＝4

つまり、3番目の要素が1まで落ちた直後に2番目の要素が2になってしまい、そうすると3番目の要素が減っても値が変わらないため3番目の要素が1にまで落ちる。更に4番目、5番目の要素と1まで落ちていき、最終的には4となる。

非拡張配列表記では、数の大きさを評価するための重要度は、最も重要なのが変数の数であり、その次に重要なのが最も右側の変数の値で、左側に行くほど重要度が下がっていく。

非拡張配列表記は、多変数アッカーマン関数と同じくらいの強さである。

この配列表記にも拡張表記が考案されており、その最終形態には2種類あり、1つはBEAF(ただし2021年現在、定義が数学的に意味を持つように定式化されているのはテトレーション配列まで)、もう1つはクリス・バードが開発したバードの配列表記と呼ばれるものである。

この配列表記は急増加関数で${\displaystyle \{x,...,x\}\approx f_{\omega ^{\omega }}(x)}$と近似できる。