BEAF入門

主要記事: BEAF

BEAF (Bowers Exploding Array Function) は、Jonathan Bowersが考案した巨大数を生み出す関数です。この入門記事では、この関数を直感的に理解できるように、少しずつ紹介します。

矢印表記

BEAFについて理解する前に、拡張演算子の本質を理解する必要があります。矢印表記はドナルド・クヌースが考案した演算子です。

\(a\uparrow b = a^b\).

\(a\uparrow\uparrow b = \underbrace{a\uparrow a\uparrow\ldots\uparrow a\uparrow a}_b = \underbrace{a^{a^{a^{.^{.^.}}}}}_b\). 巨大数研究者は、これをテトレーションと言う。矢印は右から左へと順番に計算をする。

\(a\uparrow\uparrow\uparrow b = \underbrace{a\uparrow\uparrow a\uparrow\uparrow\ldots\uparrow\uparrow a\uparrow\uparrow a}_b\). ペンテーションとも言う。

一般的に、

\(a\uparrow^n b = \underbrace{a\uparrow^{n-1} a\uparrow^{n-1}\ldots\uparrow^{n-1} a\uparrow^{n-1} a}_b\).

ここで、いくつかの計算例を示します。

\(3\uparrow 4 = 3^4 = 81\) (3 to the power of 4)

\(2\uparrow\uparrow 4 = 2\uparrow 2\uparrow 2\uparrow 2 = 2\uparrow 2\uparrow 4 = 2\uparrow 16 = 65536\) (2 tetrated to 4))

\(4\uparrow\uparrow 4 = 2361022671...5261392896\); about \(8.0723\cdot 10^{153}\) digits (4 tetrated to 4)

\(3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow 3\uparrow\uparrow 3 = 3\uparrow\uparrow 3^{3^3} = 3\uparrow\uparrow 7625597484987\) (3 pentated to 3)

演算子表記

Jonathan Bowersは、矢印表記を一般化した演算子表記を開発しました。

\(a\ \{n\}\ b = a\uparrow^n b\)

i.e.: \(a\ \{1\}\ b = a^b\)

and \(a\ \{n\}\ b = \underbrace{a\ \{n - 1\}\ a\ \{n - 1\}\ \ldots\ \{n - 1\}\ a\ \{n - 1\}\ a}_b\)

たとえば、 \(3\ \{4\}\ 5 = 3\uparrow\uparrow\uparrow\uparrow 5\) となります。

この形の演算子表記は、矢印表記を短く書き換えたに過ぎません。しかし、Bowersはnをかこむ括弧を1重から2重へと増やすことで、さらに拡張しました。

\(a\ \{\{1\}\}\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a}_b\}\ a\ldots\}\ a\}\ a\)

Bowers は、これをaのb重膨張 (a expanded to b) と呼びました。ここで、bは一番外を含んだ括弧の重複数で、(aの数 + 1) / 2 です。（情報科学者の方へ：膨張は原始帰納ではありません。あらかじめ計算された回数のループでは、プログラムできないからです。）

たとえば、このように計算されます。

\(3\ \{\{1\}\}\ 3 = 3\ \{3\ \{3\}\ 3\}\ 3 = 3\ \{3\ \{2\}\ 7625597484987\}\ 3\)

nを1から2に変えると、多重膨張になります。

\(a\ \{\{2\}\}\ b = \underbrace{a\ \{\{1\}\}\ a\ \{\{1\}\}\ \ldots\ \{\{1\}\}\ a\ \{\{1\}\}\ a}_b\)

さらにnを大きくすると、このようになります。

\(a\ \{\{3\}\}\ b = \underbrace{a\ \{\{2\}\}\ a\ \{\{2\}\}\ \ldots\ \{\{2\}\}\ a\ \{\{2\}\}\ a}_b\) (冪膨張)

\(a\ \{\{4\}\}\ b = \underbrace{a\ \{\{3\}\}\ a\ \{\{3\}\}\ \ldots\ \{\{3\}\}\ a\ \{\{3\}\}\ a}_b\) (膨張テトレーション)

膨張ペンテーション, 膨張ヘキセーション、と続きます。

これらの演算子はすべて右から左へと計算する演算子で、ハイパー演算子と同様に計算ができます。

括弧を2重から3重にすると、爆発になります。

\(a\ \{\{\{1\}\}\}\ b = \underbrace{a\ \{\{a\ \{\{\ldots a\ \{\{a\}\}\ a\ldots\}\}\ a\}\}\ a}_b\)

\(a\ \{\{\{2\}\}\}\ b = \underbrace{a\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ \ldots\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ a}_b\) (多重爆発)

\(a\ \{\{\{3\}\}\}\ b = \underbrace{a\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ \ldots\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ a}_b\) (冪爆発)

\(a\ \{\{\{4\}\}\}\ b = \underbrace{a\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ \ldots\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ a}_b\) (爆発テトレーション)

爆発ペンテーション、爆発ヘキセーション、と続きます。

括弧が4重になると爆轟（ばくごう） (多重爆轟、冪爆轟、爆轟ペンテーション)、5つになるとペントネーション (多重ペントネーション、冪ペントネーション、ペントノテトレーション)となり、ヘキソネーション、ヘプトネーションと続きます。

演算子表記には、4つの変数があります。

\(a\ \{1\}\ b = a^b\)

\(a\ \{1\}^d\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a\}^{d - 1}\ a\ldots\}^{d - 1}\ a\}^{d - 1}\ a}_b\)

\(a\ \{c\}^d\ b = \underbrace{a\ \{c - 1\}^d\ a\ \{c - 1\}^d\ \ldots\ \{c - 1\}^d\ a\ \{c - 1\}^d\ a}_b\)

ここで、上付文字の dは、cに何重の括弧がついているかを示します。たとえば、 \(\{\ldots\}^4\) は \(\{\{\{\{\ldots\}\}\}\}\) を表しています。この表記は Jonathan Bowers は使いませんでした。

巨大数研究者のChris Birdは、この4変数表記はチェーン表記と同じ程度の関数の増加速度となることを証明しました。ところが、まだBEAFの表面をちょっとひっかいた程度に過ぎません！

線形配列表記

演算子表記では、だんだん書ききれなくなってきました。より簡単に書くために、\(a\ \{c\}^d\ b\) を \(\{a, b, c, d\}\) と書き換えます。すなわち、

• \(\{a, b, 1, 1\} = a^b\)
• \(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\) if \(d > 1\)
• \(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\) if \(c > 1\)

1がデフォルトであると考えて、配列の最後が1だけであれば切り落とすことができます。たとえば、 \(\{a, b, 1, 1\}\) は \(\{a, b\} = a^b\) となります。

2番目と3番目のルールを再帰的な性質によって簡略化することができます。

\(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\)

\(= \{a, a, \underbrace{\{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}}_{b - 1}, d - 1\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\)

\(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\)

\(= \{a, \underbrace{\{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}}_{b - 1}, c - 1, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\)

しかし、この書き換えは問題があることに気がつくことでしょう。帰納的規則を定めましたが、初期条件が定められていないため、いずれの式も\(b\)が永遠に減りつづけてしまいます。そこで、\(b\)が1に到達したときの規則を定めます。

\(\{a, 1, c, d\} = a\)

このステップは、BEAFの定義で非常に重要です。分からなければ、紙で計算をしてみて下さい。

5変数以上

ここまでの規則をまとめます。

• \(\{a, b, 1, 1\} = \{a, b\} = a^b\)
• \(\{a, 1, c, d\} = a\)
• \(\{a, b, 1, d\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\), \(b,d > 1\)
• \(\{a, b, c, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\), \(b,c > 1\)

簡約化の新しい方法によって、最後の2つの式にかすかに規則性が見えてきました。この規則性に基づいて、5つ目の引数を追加します。

• \(\{a, b\} = a^b\)
• \(\{a, 1, c, d, e\} = a\)
• \(\{a, b, 1, 1, e\} = ???\)
• \(\{a, b, 1, d, e\} = \{a, a, \{a, b - 1, 1, d, e\}, d - 1, e\}\), \(b,d > 1\)
• \(\{a, b, c, d, e\} = \{a, \{a, b - 1, c, d, e\}, c - 1, d, e\}\), \(b,c > 1\)

3つ目の式が完成していませんが、4つ目と5つ目の式から逆方向に外挿することで、このように完成させることができます。

\(\{a, b, 1, 1, e\} = \{a, a, a, \{a, b - 1, 1, 1, e\}, e - 1\}\)

幸いにして、5つ目の引数は簡単に追加で来ました。同じパターンで、6つ目の引数を追加することができます。

• \(\{a, b\} = a^b\)
• \(\{a, 1, c, d, e, f\} = a\)
• \(\{a, b, 1, 1, 1, f\} = \{a, a, a, a, \{a, b - 1, 1, 1, 1, f\}, f - 1\}\), \(b,f > 1\)
• \(\{a, b, 1, 1, e, f\} = \{a, a, a, \{a, b - 1, 1, 1, e, f\}, e - 1, f\}\), \(b,e > 1\)
• \(\{a, b, 1, d, e, f\} = \{a, a, \{a, b - 1, 1, d, e, f\}, d - 1, e, f\}\), \(b,d > 1\)
• \(\{a, b, c, d, e, f\} = \{a, \{a, b - 1, c, d, e, f\}, c - 1, d, e, f\}\), \(b,c > 1\)

同様の一般化を、任意の数の引数に対して行うことができます。簡潔に書くために、いくつかの用語を定義します。1つ目の引数 \(a\) は 基数、2つ目の \(b\) は プライムと言います。プライムの後は、最初の1でない引数を パイロット、パイロットの1つ前の引数を 副操縦士と言います。そして、副操縦士よりも前のすべての引数を乗客と言います。配列の値を \(v(A)\) と書きます。これらの用語を使って、線形配列表記を記述することができます。

線形配列表記

\(b\) を基数、\(p\) をプライムとする。

1. 基数ルール パイロットがいない場合（すなわち、基数の後のすべての引数が1の時）、\(v(A) = b^p\)
2. プライムルール プライムが1の時、 \(v(A) = b\)
3. 破滅ルール それ以外の時には、
   1. 副操縦士を元の配列のプライムを1減らしたものに置き換える。
   2. パイロットの値を1減らす。
   3. すべての乗客を \(b\) にする。

(定義終了）

これが、2002年頃に作られた Bower の配列表記を再構築したものです。元々は5つのルールでしたが、現在のBEAFで採用されている3つのルールに落とし込むことができました。

例

線形配列表記の定義ができたので、計算の直感を得るために、いくつかの例を示します。

\begin{eqnarray*} \{3,3,1,1,1,3\} &=& \{3,3,3,3,\{3,2,1,1,1,3\},2\} \\ &=& \{3,3,3,3,\{3,3,3,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,2,3,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,1,3,3,3,2\},2,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,3,2,3,3,2\},2,3,3,2\},2\} \end{eqnarray*}

もし、配列の中の引数がすべて同じであれば、さらに高次の配列へと変換することができます。

3変数を4変数に変換:

• {a,a,a} = {a,2,1,2}
• {a,a,{a,a,a}} = {a,3,1,2}
• {a,a,{a,a,a,{a,a,a}}} = {a,4,1,2}
• 以下同様

4変数を5変数に変換:

• {a,a,a,a} = {a,2,1,1,2}
• {a,a,a,{a,a,a,a}} = {a,3,1,1,2}
• {a,a,a,{a,a,a,{a,a,a,{a,a,a,{a,a,a,a}}}}} = {a,6,1,1,2}

5変数を6変数に変換:

• {a,a,a,a,a} = {a,2,1,1,1,2}
• {a,a,a,a,a,{a,a,a,a,a}} = {a,3,1,1,1,2}
• {a,a,a,a,a,{a,a,a,a,a,{a,a,a,a,a}}} = {a,4,1,1,1,2}

一般に、 {a,b,1,1,...,1,1,2} = {a,a,a,...,a,a,{a,a,a,...a,a,{a,a,a,...,a,a,{a,a,a,...,a,a}...}}} となります。ここで、括弧{}はb 重です。

多次元配列

ここで、新しい概念である配列次元演算子を導入します。2つの整数a,bに対する配列次元演算子は、次のように定義されます。

\(b \& a = \underbrace{\{a, a, ..., a, a\}}_b\)

この関数は、これまでの定義すべてを「対角化」します。これはとても大きな関数です。急成長階層をよく知っているのであれば、 \(n \& n\) はおよそ \(f_{\omega^\omega}(n)\) と近似できます。

配列表記の拡張を続けるためには、直感の段階を上げる必要があります。\(b \& a\) は \(a^b = \underbrace{\{a \cdot a \cdots a \cdot a\}}_b\) と式の形が少し似ているので、基数ルールを次のように変えた「レベル2の配列表記」を考えます。

1. 基数ルール パイロットがいない場合（すなわち、基数の後のすべての引数が1の時）、\(v(A) = p \& b\)

レベル2の配列表記を示すために、配列に下付文字2を加えて \(\{a, b\}_2 = p \& b\) とします。同じようにして、レベル3の配列表記を作ることができます。\(b \&_2 a = \underbrace{\{a, a, ..., a, a\}_2}_b\) と定義して、基数ルールの \(\&\) を \(\&_2\) に変えます。はい、これがレベル3の配列表記です。

ここからは、拡張は簡単ですが少し退屈です。一般化して、レベル\(r\)の配列表記のルールをこのように作ってみましょう。

1. 基数ルール パイロットがいなくて、 \(r = 1\) であれば、 \(v(A) = b^p\) とする。
2. レベルルール パイロットがいなくて、 \(r > 1\) であれば、 \(v(A) = p \&_{r - 1} b\) とする。
3. プライムルールと破滅ルールは同じ。

では、どうすればこの拡張を最大限活用できるでしょうか？\(r\)を大きくしたいわけですから、\(r\)を配列の値にしてしまうのが一番効率的です。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}}\)

いっそのこと、これを \(b\) 回繰り返してしまいましょう。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}}}}\)

これを \(b \&_{1, 2} a\) と書きます。そうすれば、「レベル 1,2 の表記」を定義できます。（ううむ、なぜ「1,2」なのでしょうか？先に進んでから考えてみましょう。）次に、 \(2,2\) を考えますが、これは単純に \(\{a, a, \ldots, a, a\}_{1,2}\) です。ここから、レベルnの表記を考えたときと同様に、帰納的にレベルn,2の表記を定義できます。

そして、レベル 1,3 は

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},2},2}\)

となり、一般的にレベル 1,n は、n > 1 の時にこのようになります。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},n - 1},n - 1}\)

ここまでは悪くないです。では、1,1,2はどうなるでしょうか？ここから先は、レベルをあらわす \(r\) が複数の数字を持つわけなので、通常の線形配列と同じようにすれば良いわけです。つまり、\(r\)の複数の数字の中で、最初の1ではない数字を仮に「レベルパイロット」と呼んで、レベルパイロットの1つ前のレベル副操縦士を、配列全体からプライムを1減らしたものと入れ替えて、レベルパイロットを1減らして、最初の \(p\) 個の数字を\(b\)にします。

そもそも、なぜパイロットレベルパイロットを区別する必要があるのでしょうか？レベルについて気にする必要があるのは、配列が基数とプライムだけになったとき、つまり \(\{b, p\}_{1,1,2}\) のような形になったときだけです。ここで重要なことは、 \(r\) は配列の一部であるため、レベルパイロットはパイロットそのものである、ということです。

さて、ここでレベルをあらわす \(r\) を括弧の中に入れるように、表記法をアップデートしてみましょう。Bower は高次元に興味があったので、 \(r\) を2行目に入れてしまいました。たとえば、

\[\left\{ \begin{matrix} b,p \\ 1,1,2 \end{matrix} \right\}\]

となります。これを1行で書く時には、 \(\{b, p\ (1)\ 1, 1, 2\}\) と書きます。ここで、 (1) は行と行の間を示します。ここでまた、各行は（可算）無限個の1で自動的に満たされるため、この配列は \(\{b, p, 1\ (1)\ 1, 1, 2\}\) や \(\{b, p, 1, 1, 1\ (1)\ 1, 1, 2, 1, 1\}\) と同じことになります。

ためしに、新しい2行配列への拡張を今までのルールに適用してみましょう。たとえば、 \(\{b, p (1) 2\}\) を考えてみます。2がパイロットになりますが、2の前には数字がないので、副操縦士がいません！副操縦士がいない場合についても考える必要があります。また、このような場合にも問題があります。

\(\{b, p (1) 1, 1, 2\} = \{b, b, b, \ldots (1) b, \{b, p - 1 (1) 1, 1, 2\}, 2\}\)

問題は、1行目に無限個の b があることです。p個だけがほしいのです。「乗客」の定義も、2行配列にしたことで拡張する必要があります。まとめると、このようになります。

• 基数は、1つ目の要素。
• プライムは、2つ目の要素。
• パイロットは、基数の次の最初の1ではない要素。
• 副操縦士は、パイロットの直前の要素。2行目の最初がパイロットであれば、副操縦士は存在しない。
• 前の要素とは、同じ行にある前の要素である。したがって、 \(\{a, b (1) c, d\}\) においては、\(d\)の前の要素は \(c\) であって、 \(a\) と \(b\) は違う。
• ある行のプライムブロックは、その行の中の最初の \(p\) 個の要素、つまりプライムの個数の要素である。
• 飛行機は、パイロットとすべての前の要素である。パイロットが2行目にあれば、飛行機は前の行のプライムブロックを含む。
• 乗客は、飛行機の中でパイロットと副操縦士（もしいれば）を除くすべての要素である。

これ以外のルールは線形配列表記と同じです。最初に「レベル」として考えていたものは、配列の中に組み込まれてしまったので、「レベルルール」は必要ではありません。

ここに、計算例を示します。

\begin{eqnarray*} \{3,3,3 (1) 2\} &=& \{3,\{3,2,3 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,1,3 (1) 2\},2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,3,2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\},1 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,\{3,1,2 (1) 2\},1 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3 (1) 1\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3\} (1) 2\},2 (1) 2\} \end{eqnarray*}

3行以上

3行配列で最も簡単で意味のある配列は \(\{b, p (1) (1) 2\}\) です。ここで、2行目は1だけです。これは、パイロットが3行目の2で、副操縦士はなく、乗客は1行目と2行目のプライムブロックなので、それぞれ最初のp個のエントリとなって、その2行がすべてbになって、パイロットである3行目の最初の要素は2から1を引いて1となるため3行目が消去されて、 \(\{b, b, \ldots, b, b (1) b, b, \ldots, b, b\}\) と等しくなります。ここで、それぞれの行に、 \(p\) 個の要素があります。この例では、パイロットが3行目に移動しましたが、さらに副操縦士をつけると、たとえば \(\{b, p (1) (1) 1, 2\} = \{b, p (1) (1) \{b, p - 1 (1) (1) 1, 2\}\}\) のように計算ができます。3行以上は同様に振る舞うので、一般化してしまいましょう。

飛行機の定義を、次のように変える必要があります。

• 飛行機は、パイロットと、パイロットと同じ行のすべてのパイロットの前の要素と、すべての前の行のプライムブロックである。

パイロットが1行目にいるときには、前の行は存在しないため、飛行機は前の要素だけになります。これで、前の飛行機の定義に入っていた条件節（「パイロットが2行目にあれば」の文）を書く必要がなくなります。

さて、これでようやく平面配列表記の定義が完成しました。では、行の次には何が来るでしょうか？

3次元

そうです、平面です。平面と平面の間の境界には (2) を使います。最小の2平面配列は \(\{b, p (2) 2\} = \{b, b, \ldots, b, b (1) b, b, \ldots, b, b (1) \ldots (1) b, b, \ldots b, b (1) b, b, \ldots, b, b\}\)、つまり \(p \times p\) 配列の \(b\) です。(これを \(p^2 \& b\) とも書くことができます。後で、詳しく説明します。) ついに複数の平面に到達します。ほぼ予想通りに計算出来ます。

それでは、きちんとした定義を与えましょう。一般化するために、さらにいくつかの抽象的な用語を導入します。その1つは構造です。構造は、要素、行、あるいは平面のどの可能性もあります。それでは、一般的な構造に対するプライムブロックを定義しましょう。

• ある行のプライムブロックとは、最初の \(p\) 個の要素で、ある平面のプライムブロックは最初の \(p \times p\) の正方形の要素、つまり最初の \(p\) 行のプライムブロックである。
• Xの前の要素とは、Xと同じ行内の前の要素である。Xの前の行とは、Xと同じ平面内の前の行である。
• 飛行機とは、パイロットと、すべての前の要素、そしてすべての前の構造のプライムブロックである。

この最後の定義は、BEAFの動作の核心部分なので、よく理解して下さい。

たとえば、ザッポル = {10,10 (2) 2} を考えてみましょう。パイロットは 2 です。これは行の先頭の要素なので、前の要素はありません。そして、前の平面のプライムブロックは、\(10 \times 10\) の正方形の要素になります。破滅ルールにより、パイロットの2が1になって消去され、乗客であるプライムブロックはすべて10に変わることにより、\(10 \times 10\) 配列の 10 となります。

4次元以上

Bowers によれば、平面が無限に重なったもの、すなわち3次元空間は領域(realm)で、4次元空間はフルーン(flune)です。領域とフルーンを分ける記号は、それぞれ (3) and (4) です。

一般に、 (n) は次のn次元空間との境界を示す記号です。要素は0次元空間なので、カンマは (0) を省略したものだと考えることができます。"構造"とは、任意のn次元空間です。n次元空間を \(X^n\) と表記します。

それでは、これまでの定義を"構造"、"プライムブロック"、"前の構造"、そして"飛行機"によって書き直してみましょう。

• 構造とは、要素、行、平面、領域、フルーン、5次元空間、…等である。要素を構造として、構造の無限の連なりを構造であると、帰納的に定義出来る。
• ある行のプライムブロックとは、最初の\(p\)個の要素である。ある平面のプライムブロックとは、 \(p \times p\) の正方形である。ある領域のプライムブロックは、最初の \(p \times p \times p\) の立方体である。同様にして、より高次元のプライムブロックを定義出来る。ある行のプライムブロックとは最初の\(p\)個の要素であり、\(X^n\) 構造のプライムブロックは最初の \(p\) 個の \(X^{n-1}\)構造であるとすれば、帰納的に定義出来る。
• Aに対する前の構造とは、同じ \(X^{n + 1}\) 構造の中の前の \(X^n\) 構造である。例えば、Aの前の要素Aと同じ行の中のAよりも前の要素であり、Aの前の行とはAと同じ平面の中のAよりも行であり、等となる。
• 飛行機とは、パイロットと、すべての前の要素と、すべての前の構造のプライムブロックである。

ここまでで、完全に多次元配列表記を定義することができました。ここまでの定義をまとめます。

多次元配列表記

定義:

• 基数 \(b\) は、1番目の要素である。
• プライム \(p\) は、2番目の要素である。
• パイロットは、プライムの後の最初の1でない要素である。
• 副操縦士は、パイロットの直前の要素である。パイロットが行の最初であれば、副操縦士は存在しない。
• 構造とは、要素、行、平面、領域、フルーン、5次元空間、…等である。要素を構造として、構造の無限の連なりを構造であると、帰納的に定義出来る。
• ある行のプライムブロックとは、最初の\(p\)個の要素である。ある平面のプライムブロックとは、 \(p \times p\) の正方形である。ある領域のプライムブロックは、最初の \(p \times p \times p\) の立方体である。同様にして、より高次元のプライムブロックを定義出来る。ある行のプライムブロックとは最初の\(p\)個の要素であり、\(X^n\) 構造のプライムブロックは最初の \(p\) 個の \(X^{n-1}\)構造であるとすれば、帰納的に定義出来る。
• Aに対する前の構造とは、同じ \(X^{n + 1}\) 構造の中の前の \(X^n\) 構造である。例えば、Aの前の要素Aと同じ行の中のAよりも前の要素であり、Aの前の行とはAと同じ平面の中のAよりも行であり、等となる。
• 飛行機とは、パイロットと、すべての前の要素と、すべての前の構造のプライムブロックである。
• 乗客とは、飛行機の中のパイロットと副操縦士（もし存在すれば）以外のすべての要素である。

規則:

1. 基数ルール パイロットがいない場合（すなわち、基数の後のすべての引数が1の時）、\(v(A) = b^p\)
2. プライムルール プライムが1の時、 \(v(A) = b\)
3. 破滅ルール それ以外の時には、
   1. 副操縦士を元の配列のプライムを1減らしたものに置き換える。
   2. パイロットの値を1減らす。
   3. すべての乗客を \(b\)にする。

(定義の終了)

やりました！これが Bird と Bowers が開発した拡張配列表記です。当初は7つのルールがありましたが、現代の BEAF の定義によってかなり簡潔になっています。

配列次元演算子

配列次元演算子は、& と表記され（論理積 "and" 演算子と混同しないで下さい）、& の左側に書かれている構造の配列を、& の右側の数字で埋めます。ここで、構造とはなんでしょうか？最初の構造は数字で、 \(n\ \&\ m = \{\underbrace{m,m,m,\cdots,m,m,m}_{\text{n 個の m}}\}\) となります。数字よりも上の構造は、X構造と言われ、m として評価されます。したがって、 \(X\ \&\ m = m \&\ m = \{m, m (1) 2\}\) となります。

もし他の数字を使いたければ、括弧に数字を入れて示すことができます。つまり、 \(X\ \&\ a[b] = b\ \&\ a[b]\) ということです。この表記は、 Bowers 自身は使いませんでした。

数字 X の上の構造は X+1,X+2,X+3,...,2X,2X+1,2X+2,2X+3,...,3X,4X,...,\(X^2\), 等となります。X+m は1行の要素の下に m 個の要素があるもの、 2X は2行、 3X は3行、 nX+m は n 行の要素の下に m 個の要素があるもの、となります。ここで、ここまでに示してきた表記と配列次元演算子の間の対応を示します。

\begin{eqnarray*} 1\ \&\ n &=& \{n\} = n \\ 2\ \&\ n &=& \{n,n\} = n^n \\ 3\ \&\ n &=& \{n,n,n\} = n \uparrow^{n} n \\ 4\ \&\ n &=& \{n,n,n,n\} = n \underbrace{ \{\{\cdots\{\{n\}\}\cdots\}\} }_{n \{\}'s} n \\ m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} &=& \{n,m (1) 2\} \\ X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} &=& \{n,n (1) 2\} \\ X+1\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n\} \\ X+2\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n\} \\ X+3\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n,n\} \\ X+m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} \\ 2X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ 3X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ mX\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{m X's}}\} &=& \{n,m (2) 2\} \\ X^2\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{n X's}} &=& \{n,n (2) 2\} \end{eqnarray*}

お分かりのように、最後の3つの例は、それぞれ \(\{n,3 (2) 2\}, \{n,m (2) 2\}\) そして \(\{n,n (2) 2\}\) と簡略化できます。ここで、最後の "2" は次の平面で、3次元配列の開始を意味します。幸いにして、多次元の配列をそのままの形で描く必要がなくなります。重要な点は、多項式の形を使うことです。 \(a_1X^m+a_2X^{m-1}+a_3X^{m-2}+\cdots+a_{m-1}X+a_m \&\ b[p]\) という式は、配列が \(a_1\) 個の \(X^m\) (m次元配列の b)、そして \(a_2\) 個の \(X^{m-1}\)、そして \(a_3\) 個の \(X^{m-2}\)、といった構造となっていることを意味しています。要素の個数は、X を p に入れ替えて、通常の多項式を計算することで分かります。たとえば、 \(X^{100}+X^{99} \&\ 3[4]\) は \(4^{100}+4^{99}\) 個の要素があります。

外部リンク

• 3 entry arrays
• 4 entry arrays
• The World's Largest Numbers, Part One @ Things Of Interest (linear arrays)
• The World's Largest Numbers, Part Two @ Things Of Interest (planar arrays)