巨大数研究 Wiki
Advertisement
主要記事: 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\)
\(2\uparrow\uparrow 4 = 2\uparrow 2\uparrow 2\uparrow 2 = 2\uparrow 2\uparrow 4 = 2\uparrow 16 = 65536\)
\(4\uparrow\uparrow 4 = 2361022671...5261392896\)、およそ\(8.0723\cdot 10^{153}\) ケタ
\(3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow 3\uparrow\uparrow 3 = 3\uparrow\uparrow 3^{3^3} = 3\uparrow\uparrow 7625597484987\)

演算子表記[]

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

\(a\ \{n\}\ b = a\uparrow^n b\)
すなわち \(a\ \{1\}\ b = a^b\)、
そして\(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の個数です。(情報科学者の方へ — 膨張は原始帰納ではありません。あらかじめ計算された回数のループでは、プログラムできないからです。)

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

\(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-1 重の括弧)となります。

多次元配列[]

ここで、新しい概念である配列次元演算子 ("Array of" operator)を導入します。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だけです。期待通り、これは各行に\(p\)個の要素がある配列 \(\{b, b, \ldots, b, b (1) b, b, \ldots, b, b\}\) と等しくなります。今やパイロットは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)と(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つのルールがありましたが、現在ではかなり簡潔になっています。


配列次元演算子[]

配列次元演算子は、& と表記され(論理積 "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}\) 個の要素があります。

ゴンギュラス は、配列次元演算子を使うと (10100) & 10 と書くことができて、これは100次元超立方体に1辺に10が10個入っている状態ですが、それを 101次元超立方体を使って簡略化すると {10,10 (100) 2} となります。

テトレーション配列[]

ここまでで、急増加関数が分かる方であれば、 \(f_{\omega^{\omega^\omega}}\) のレベルまでのシステムを構築することができました。次のステップはあまり分かりやすくはありませんが、さらに上のシステムへと続けるためには、肝要です。

\(\{b, p (0, 1) 2\}\)

これは一体何を意味するのでしょうか?これは \(X^X\) 構造で、 \(X^X\) 構造のプライムブロックは \(p^p\) 構造、つまり \(\underbrace{p \times p \times \cdots \times p \times p}_p\) の多次元立方体となります。つまり、2 x 2 の正方形か、 3 x 3 x 3 の立方体か、 4 x 4 x 4 x 4 の超立方体か、といったようになります。これを実際に計算する時には、 (0, 1) を (p) と入れ替えます。たとえば、 \(\{b, 4 (0, 1) 2\} = \{b, 4 (4) 2\}\) となります。

技術的なメモ: \(X^X\) 構造で表現される空間を、次元グループと言います。次元グループでは、それぞれの座標を特定の有限の数の組ではなく、順序型 \(\omega\) を持つ座標の列で表現します。

\(\{b, p (1, 1) 2\}\)

これは \(X^{X + 1}\) 構造を持ちます。 プライムブロックは \(p^{p + 1}\) です。一般的に、 \((n, m)\) は \(X^{mX + n}\) 構造の区切りを生み出します。

線形配列セパレータは、可能な限りの \(X^P\) 構造を記述可能です。ここで \(P\)は\(X\)の多項式で、係数が非負整数であるものとします。(以降この記事において、多項式は非負整数係数のものに限ります。) 0次からの係数のリストによってこれは実現されます:

\((a_0, a_1, a_2, a_3, \ldots)\) は、構造 \(X^{a_0 + a_1X + a_2X^2 + a_3X^3 + \cdots}\) を表す。

例えば、(0, 0, 1) は \(X^{x^2}\) を、(1, 0, 6, 1) は \(X^{1 + 6X^2 + X^3}\) を表します。区切れ目の数字は1からではなく0から数えることに注意してください。

もちろん、セパレータを線形配列に留めておかなければならない理由などありません。

\(\{b, p (0 (1) 1) 2\} = \{b, p ((1) 1) 2\}\)

これは \(X^{X^X}\) 構造、すなわち「超次元グループ」です。(超次元グループの座標を表すベクトルは、順序型\(\omega^\omega\)を持ちます。)

もう少し一般的な表現にします。

\((a_{00}, a_{01}, a_{02}, \ldots (1) a_{10}, a_{11}, a_{12}, \ldots )\) は構造 \(X^{a_{00} + a_{01}X + a_{02}X^2 + a_{03}X^3 + \cdots + a_{10}X^X + a_{11}X^{X + 1} + a_{12}X^{X + 2} + \ldots}\) を表す。

3行のセパレータ ((1)(1)1) は \(X^{X^{2X}}\) を表し(まだ \(X^{X^{X^X}}\) ではありませんよ!)、(n+1)行のセパレータは \(X^{X^{nX}}\) を表します。第2平面 ((2)1) は \(X^{X^{X^2}}\)、第2領域 ((3)1) は \(X^{X^{X^3}}\)、という具合で、フルーン以降も表記されます。とうとう、次なる次元グループ ((0, 1) 1) の構造 \(X^{X^{X^X}} = X \uparrow\uparrow 4\) に到達しました。内側の括弧は \(X\) の多項式 \(P\) を表し、外側の括弧まで含めて構造 \(X^{X^{X^P}}\) を表します。

\(\{b, p (((1) 1) 1) 2\}\)

これは \(X^{X^{X^{X^X}}} = X \uparrow\uparrow 5\) 構造を持ちます。以降、

\(\{b, p (((0, 1) 1) 1) 2\}\) は構造 \(X \uparrow\uparrow 6\)
\(\{b, p ((((1) 1) 1) 1) 2\}\) は構造 \(X \uparrow\uparrow 7\)
\(\{b, p ((((0, 1) 1) 1) 1) 2\}\) は構造 \(X \uparrow\uparrow 8\)
etc.

と続きます。これらの極限は \(X \uparrow\uparrow X\) 構造です。ここまでで、私たちはテトレーション配列表記を得ることができました。

定義への挑戦[]

折り畳みされている内容は、Bowersが書いた元の文では言及されていません。

Bowers はテトレーション配列に厳密な定義を与えようとしませんでしたが、ためしにやってみましょう。今私たちを阻んでいるのはプライムブロックの定義だけです。 これは、次元配列専用に特別に調整されています。現在の帰納的定義を見てみましょう:

  • エントリのプライムブロックはエントリです。
  • \(X^{n+1}\)構造のプライムブロックは、最初の \(p\) \(X^n\)-構造のプライムブロックです。

(ここでは若干の変更がありますが、効果は最小限であることがわかります。)\(X^{n + 1}\)-構造ではないため、 この定義は、構造が\(X^X\)構造である場合に何が起こるかを示していません。

この定義を拡張して、次数1の多項式\(P \)のすべての\(X ^ P \)を許可してみましょう。

  • エントリのプライムブロックはエントリです。
  • \(X^{P+1}\)-構造のプライムブロックは最初の\(p \)\(X^P\)-構造のプライムブロックであり、\(P\)は\(X\)の多項式です。
  • \(X ^ {P + X} \)構造のプライムブロックは、最初の\(X ^ {P + p} \)構造のプライムブロックです。

これは予想どおり\(X ^ {X ^ 2} \)で機能しますが、パターンが出現しています。

  • エントリのプライムブロックはエントリです。
  • \(X^{P+1}\)-構造のプライムブロックは最初の\(p \)\(X^P\)-構造のプライムブロックであり、\(P\)は\(X\)の多項式です。
  • \(X^{P+X}\)-構造のプライムブロックは最初の\(X^{P + p}\)構造のプライムブロックです。
  • \(X^{P+X^2}\)-構造のプライムブロックは最初の\(X^{P + pX}\)構造のプライムブロックです。
  • \(X^{P+X^3}\)-構造のプライムブロックは最初の\(X^{P + pX^2}\)構造のプライムブロックです。
  • \(X^{P+X^{n+1}}\)-構造のプライムブロックは最初の\(X^{P + pX^n}\)構造のプライムブロックです。

これは\(X^{X^X}\)まで機能します。しかし、この定義では、\(X \uparrow\uparrow X\)に到達することはありません!

2回目の挑戦[]

折り畳みされている内容は、Bowersが書いた元の文では言及されていません。

「構造」の概念を一般化して、定義を補足しましょう。

  • \(0\)は構造です。
  • \(\alpha\)が構造体なら、\(X^\alpha\)も構造体です。
  • \(\alpha\)と\(\beta\)が構造体なら、\(\alpha + \beta\)も構造体です。

これにより、\(2X\)や\(4X^X + X + 1\)など、\(X \uparrow\uparrow X\)までの構造体が一般化できます。

さらに、 \(\alpha > 0\)のときは\(X^\alpha\) 、 \(\alpha\)、\(\beta\) が極限構造のときは\(\alpha+\beta\)となる極限構造、\(\alpha + 1\)の形である後続構造を定義しましょう。

ここで、構造体\(\alpha[p]\)のプライムブロックを再帰的に定義します。

  • \(0[p] = \{\}\)
  • \((\alpha + 1)[p] = \alpha[p] \cup \alpha + 1\text{の最後の引数}\}\)
  • \(X[p] = p\) かつ \(X^{\alpha + 1}[p] = X^{\alpha} p\)
  • \(\alpha\)が極限構造のとき、\(X^{\alpha}[p] = X^{\alpha[p]}\)
  • \((X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} + X^{\alpha_k})[p] = (X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} )[p] \cup X^{\alpha_k}[p])\)、\(\alpha_k\) は最小の \(\alpha_i\)
  • \(X\uparrow\uparrow X[0] = 1\) かつ\(X\uparrow\uparrow X[p] = X^{X\uparrow\uparrow X[p-1]}\)

必要なのはこれがどう機能するかという考え方だけなので、分からないのなら読み飛ばして構いません。

最後に、上の定義で「最小」という言葉を使いました。ただ構造は数ではなく、まだ順序を定義していないことに注目してください。これについては簡単です。

  • \(\alpha < \alpha + X^0\)
  • \(\alpha < \beta\)のとき、\(X^\alpha < X^\beta\)
  • \(\alpha < \beta\)のとき、\(\alpha + \gamma < \beta + \gamma\)

これでおしまいです!

…ただ、もっと簡潔に出来ないでしょうか?

順序数として (上級編)[]

折り畳みされている内容は、Bowersが書いた元の文では言及されていません。

数学の知識がある読者は、ここまでの議論が順序数による階層と似ていることに気がついたかもしれません。\(X\) 関数は \(\omega\) とよく似ていて、プライムブロックの定義は急増加関数の Wainer 階層と似ているように見えます。\(\alpha[p]\) という表記を使ったのはそのためです。ここまでで、 \(\varepsilon_0\) までの表記を構築できました。これは、ここまでの BEAF の強さになっています。これまでの表記を順序数を使って書き直すのは、理にかなっています。やってみましょう。

まず配列を1より大きい出力の数は有限である関数\(A : \varepsilon_0 \mapsto \mathbb{N}_+\)として定義します。(これで{6, 6, 6, ...}というような無限に続く配列になるのを防げます。)そして\(b = A(0)\)、\(p = A(1)\)、\(\pi = \min\{\alpha > 1: A(\alpha) > 1\}\) (パイロットの位置)、\(\kappa = \pi - 1\) (副操縦士の位置)とします。

プライムブロック \(\Pi(\alpha)\)を次のように定義します。

  • \(\Pi(0) = \{\}\)
  • \(\Pi(\alpha + 1) = \{\alpha\} \cup \Pi(\alpha)\)
  • \(\alpha\)が極限順序数のとき、\(\Pi(\alpha) = \Pi(\alpha[p])\)

(これは緩成長関数の定義とよく似ています。)乗客\(S\)を次のように定義します。\(S = \Pi(\pi) \backslash \{\pi, \kappa\}\)

そして以下の3つのルールを定義します。

  1. 基数ルール \(\pi\)が存在しないとき、\(v(A) = b^p\)
  2. プライムルール \(p = 1\)のとき、 \(v(A) = p\)
  3. 破滅ルール  \(A'\)を以下のように修正した\(A\)とします。
    • \(B\)を\(A\)と定義します(ただし\(B(1) = p - 1\))
    • \(\kappa\) が存在するとき、\(A'(\kappa) := v(B)\)
    • \(A'(\pi) = A(\pi) - 1\)
    • \(\sigma \in S\)のときは\(A(\sigma) := b\)
    • \(v(A) = v(A')\)

わかりにくいですが、先の定義よりかなりシンプルです!

もうひとつ、\(\varepsilon_0\)以下の序数列の基本数列を定義してみましょう。

  • 極限順序数 \(\alpha\)に対し、\(\omega^\alpha[n] = \omega^{\alpha[n]}\)
  • \(\omega^{\alpha + 1}[n] = \omega^\alpha n\)
  • \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k\)のとき、\((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k}[n]\)
  • \(\omega \uparrow\uparrow 0 = 1\)
  • \((\omega \uparrow\uparrow (\alpha + 1))[n] = \omega^{\omega \uparrow\uparrow \alpha}[n]\)


このシステムは定義が曖昧で、動作の大まかなスケッチに使用されているだけであることに注意してください。

Bowersの\(X\)階層を正しく反映させるために、\(\omega \uparrow\uparrow n\)の定義を導入しました。実際、\(\varepsilon_0\)以降の基本シーケンスは通常とは少し異なります。

ペンテーション配列[]

ペンテーション配列は、少しわけがわかりません。なんといっても一番良くないのは、ペンテーション配列を表記する方法が考案されていないのです!Bowers は、そのことを気にしませんでした。彼はただ、配列次元演算子を使ってペンテーション配列を書いただけです。

配列次元演算子を覚えていますか?このようなものです。

\(a \& b = \{b, a (1) 2\}\)

配列次元演算子は、1行の配列の時に導入してから、ずっと使っていませんでした。そして、 & の記号はさらにその先のレベルにまで拡張可能であることが分かります。

\(a^2 \& b = \{b, a (2) 2\}\)

右辺はa×aの配列にbという要素が満たされているもの、すなわち a2 配列の b であることを理解することは、難しくありません。ここで、 "\(a^2\)" という表記は、最初に計算してしまってはいけないことに注意して下さい。これはむしろ、配列の次元の形を示す青写真です。

\(a^k \& b = \{b, a (k) 2\}\)

一般に、配列次元演算子では多くの次元を指定することができ、このような四則演算の配列も指定できます。

\(a^{a^a} \& b = a \uparrow\uparrow 3 \& b = \{b, a ((1) 1) 2\}\)

上記の序数的定義を理解した人は、\(f(a) \& b = \{0 \mapsto b, 1 \mapsto a, f(\omega) \mapsto 2\}\)と正式に定義できます。

最小のペンテーション配列は以下のようなものです。

\((a \uparrow\uparrow a) \& b = \{b, a (???) 2\}\)

この配列(\(X \uparrow\uparrow X\)構造)の表記法がありませんが、 \(\omega \uparrow\uparrow \omega = \varepsilon_0\)の基本列を\(\varepsilon_0[n] = \omega \uparrow\uparrow n\)とする順序数で定義できることは明らかです。「順序数」が何なのかわからない方々、申し訳ありません。もしあなたがその中の一人なら、レギオン配列の項目まで飛ばしてください。

この時点で\(X \uparrow\uparrow\uparrow X\)がどんなものかと考えるかもしれませんが、そこにたどり着くには\(X \uparrow\uparrow (X2)\)と\(\omega \uparrow\uparrow (\omega2)\)の基本列について定義しなければなりません。

順序数における\(\uparrow\uparrow\)の定義が不完全なために\(\omega \uparrow\uparrow (\omega2) = \omega \uparrow\uparrow \omega\)となってしまうので、これを修正しないといけないのです。

定義を\(\omega \uparrow\uparrow (1 + \alpha) = \omega^{\omega \uparrow\uparrow \alpha}\)に修正すれば、\(\omega \uparrow\uparrow (1 + \omega) = \omega \uparrow\uparrow \omega\)が関数\(\omega \mapsto \omega^\alpha\)の不動点であることがはっきりとわかります。

\(\omega \uparrow\uparrow (\omega2)\)は次の不動点\(\varepsilon_1\)になるはずです。\(\varepsilon_1\)の特にきれいな定義は、\(\varepsilon_0, \varepsilon_0^{\varepsilon_0}, \varepsilon_0^{\varepsilon_0^{\varepsilon_0}}, \ldots\)の極限というものです。ではなぜ\(\varepsilon_1 = \varepsilon_0 \uparrow\uparrow \omega = (\omega \uparrow\uparrow \omega) \uparrow\uparrow \omega\)とならないのでしょう?

一般には \(a \uparrow\uparrow a2 \neq (a \uparrow\uparrow a) \uparrow\uparrow a\)となるので、最初これは奇妙に思えます。順序数はおかしな動きをしますね。

次の不動点は\(\omega \uparrow\uparrow (\omega3) = \varepsilon_1 \uparrow\uparrow \omega = \varepsilon_2\)で、一般に有限の\(n(n > 0)\)に対し、\(\omega \uparrow\uparrow (\omega n) = \varepsilon_{n - 2} \uparrow\uparrow \omega = \varepsilon_{n-1}\)になります。 これらの極限は無論\(\omega \uparrow\uparrow (\omega^2) = \varepsilon_\omega\)となります。

・・・・・。 \(\varepsilon_{\varepsilon_0} = \omega \uparrow\uparrow (\omega \uparrow\uparrow \omega) = \omega \uparrow\uparrow\uparrow 3\)、\(\varepsilon_{\varepsilon_{\varepsilon_0}} = \omega \uparrow\uparrow\uparrow 4\)、となるまで面白いことは何もないです。矢印3本はかなり有望で、これらすべての極限は\(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\)となります。はい。

厳密な定義[]

良い知らせです。ペンテーション配列を正式に定義するためには、順序数と収束列を定義すればそれでいいわけです。配列表記は標準的な順序数の計算には含まれていないため、きちんと定義を与える必要があります。

  • \(\alpha \uparrow\uparrow 0 = 1\)
  • \(n < \omega\)のとき、\(\alpha \uparrow\uparrow (n + 1) = \alpha^{\alpha \uparrow\uparrow n}\)
  • 極限順序数\(\beta\)に対し、\(\alpha \uparrow\uparrow \beta = \bigcup\{\gamma < \beta : \alpha \uparrow\uparrow \gamma\}\)
  • \(\beta \geq \omega\)のとき、\(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)},(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)}},...\}\)
  • \((\alpha \uparrow\uparrow \beta)[n] = \alpha \uparrow\uparrow \beta[n]\)

この超演算子と基本列の系は読者の便宜のために、望ましい作用素の定義方法を大まかに説明しているだけでまだ未定義であるため、正式な定義は全く与えられていないことに注意してください。

より大きいレギオンを使わない配列[]

折り畳みされている内容は、Bowersが書いた元の文では言及されていません。

前節で、 \(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\) まで定義ができました。これは、 \(\omega \uparrow\uparrow\uparrow \omega = \{\omega, \omega, 3\}\) とも書くことができます。では、 \(\{\omega, \omega, 4\}\) の定義をしない理由があるでしょうか?また、\(\{\omega, \omega, 1, 2\}\) はどうでしょう?\(\{\omega, \omega (0, 1) 2\}\) は?

唯一の障害は、厳密な定義ができるかどうかです。順序数による BEAF を定義する必要があります。まずは、有限の長さの矢印に対する矢印表記から始めます。

  • \(\alpha \uparrow \beta = \alpha^\beta\)
  • \(\alpha \uparrow^k 0 = 1\)
  • \(n < \omega\)のとき、\(\alpha \uparrow^{k + 1} (n + 1) = \alpha \uparrow^k (\alpha \uparrow^{k + 1} n)\)
  • 極限順序数\(\beta\)に対し、\(\alpha \uparrow^k \beta = \sup\{\gamma < \beta : \alpha \uparrow^k \gamma\}\)
  • \(\beta \geq \omega\)のとき、\(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta))\uparrow^{k-1}(\alpha \uparrow^k \beta),...\} \)
  • \((\alpha \uparrow^k \beta)[n] = \alpha \uparrow^k \beta[n]\)


矢印表記による順序数がヴェブレン関数に似ていることはややわかりやすく、違いはほとんど基本階層にあります。ヴェブレン関数と同じように、\(\alpha \mapsto \omega \uparrow^{k + 1} (\omega + \alpha)\)は\(\alpha \mapsto \omega \uparrow^k \alpha\)の不動点を表します。

この定義はルールの多さによってすでに少し煩わしいものとなっています。とにかく、試しに\(k = \omega\)としてみましょう。

  • \(\alpha \uparrow^\omega \beta = \sup\{k < \omega : \alpha \uparrow^k \beta\}\)
  • \((\alpha \uparrow^\omega \beta)[n] = \alpha \uparrow^n \beta\)

ただし\(\omega \uparrow^\omega \omega = \phi_\omega(0)\)です。すでに考えた枠組みは、後継順序数\(k\)に対して機能しますが、ここでは以下の制限が必要です。

  • \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\)
  • \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\)

まとめると、

  • \(\alpha \uparrow \beta = \alpha^\beta\)
  • \(\alpha \uparrow^\kappa 0 = 1\)
  • \(n < \omega\)のとき、\(\alpha \uparrow^{\kappa + 1} (n + 1) = \alpha \uparrow^\kappa (\alpha \uparrow^{\kappa + 1} n)\)
  • \(\beta \geq \omega\)のとき、\(\alpha \uparrow^\kappa (\beta + 1) = (\alpha \uparrow^\kappa \beta) \uparrow^\kappa \alpha\)
  • 極限順序数\(\kappa\)に対し、\(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\)
  • 極限順序数\(\beta\)に対し、\(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \beta : \alpha \uparrow^\kappa \gamma\}\)
  • 極限順序数\(\kappa\)に対し、\((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\)
  • 極限順序数\(\beta\)に対し、\((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^\kappa \beta[n]\)

この定義は問題なく機能しますが、最後の2組のルールは同じ条件になっています。\((\omega \uparrow^\omega \omega)[n]\)となる場合、むしろ\(\omega \uparrow^n \omega\)とした方がいいので、\(\kappa\)と\(\beta\)が極限順序数のときは, まず\(\kappa\) に焦点を当てるべきです。

とりあえず、これを引数3の配列表記で書き出してみましょう。これは通常の引数3の記法にいくつかの極限順序数を加えたものです。物事を単純化するために、普通の配列表記のようにどの引数も0にならないとします。

  • \(\{a, b, 1\} = a^b\)
  • \(\{a, 1, c\} = a\)
  • \(b < \omega\)のとき、\(\{a, b + 1, c + 1\} = \{a, \{a, b, c + 1\}, c\}\)
  • \(b \geq \omega\)のとき、\(\{a, b + 1, c\} = \{\{a, b, c\}, a, c\}\)
  • \(c \in \text{Lim}\)のとき、\(\{a, b, c\} = \sup\{x < c: \{a, b + 1, x\}\}\)
  • \(b \in \text{Lim}\)のとき、\(\{a, b, c + 1\} = \sup\{x < b: \{a, b + 1, c + 1\}\}\)
  • \(c \in \text{Lim}\)のとき、\(\{a, b, c\}[n] = \{a, b, c[n]\}\)
  • \(b \in \text{Lim}\)のとき、\(\{a, b, c + 1\}[n] = \{a, b[n], c + 1\}\)

\(\text{Lim}\)はすべての極限順序数の集合です。

また、4番目と5番目のルールをそれぞれ6番目と7番目のルールの限界と定義すれば、取り除くこともできます。

引数4:

  • \(\{a, b, 1, 1\} = a^b\)
  • \(\{a, 1, c, d\} = a\)
  • \(b < \omega:\)
    • \(\{a, b + 1, 1, d + 1\} = \{a, \{a, b, 1, d + 1\}, 1, d\}\)
    • \(\{a, b + 1, c + 1, d\} = \{a, \{a, b, c + 1, d\}, c, d\}\)
  • \(b > \omega:\)
    • \(\{a, b + 1, c, d\} = \{\{a, b, c, d\}, a, c, d\}\)
  • \(d \in \text{Lim}\)のとき、\(\{a, b, c, d\}[n] = \{a, b, c, d[n]\}\)
  • \(c \in \text{Lim}\)のとき、\(\{a, b, c, d + 1\}[n] = \{a, b, c[n], d + 1\}\)
  • \(b \in \text{Lim}\)のとき、\(\{a, b, c + 1, d + 1\}[n] = \{a, b[n], c + 1, d + 1\}\)

ここから一般化するのは簡単です。

線形順序数配列表記

定義は同じです — 基数 \(b\) は1番目の要素。プライム \(p\) は2番目の要素。 パイロットはプライムの次の最初の1ではない要素。副操縦士はパイロットの直前の要素。乗客は副操縦士以前の1の要素。これらに加え、リミッター\(l\)を基数の後の最後の極限順序数(もしプライム以降後続順序数しかない場合は、存在しないかもしれない)と定義します。

すべての要素は0から\(\omega_1\)までの排他的なものです。

  1. 基数ルール パイロットがいない場合、\(v(A) = b^p\)
  2. プライムルール \(p = 1\)のとき、 \(v(A) = p\)
  3. 破滅ルール リミッターがなく、\(p < \omega\)のとき、
    1. 副操縦士を、プライムを1減らした配列のコピーに置き換える(プライムは後続順序数でなければならず、そうでなければリミッターがかかる)。
    2. パイロットの値を1減らす。
    3. すべての乗客を\(b\)に置き換える。
  4. 永久破滅ルール リミッターがなく、\(p \geq \omega\)のとき、
    1. 基数を、プライムを1減らした配列のコピーに置き換える(プライムは後続順序数でなければならず、そうでなければリミッターがかかる)。
    2. プライムを元のbの値に設定する。
  5. 制御ルール 上記のいずれにも当てはまらないとき、
    1. リミッターを\(l[n]\)に変更した配列の値を\(v(A)[n]\)とする。
    2. \(v(A) = \sup\{1 \leq < n < \omega : v(A)[n]\}\).
(定義終了)

もちろん、線形配列でおしまいにする理由はありません。 テトレーション配列も簡単に順序数に拡張できます。となれば、制御ルールを導入して、\(A\)の領域を\(\varepsilon_0\)から\(\omega_1\)まで拡張すればいいのです。\(\omega_1\)は、数えられる長さの基本列を持たない最初の序数列です。 ・・・ここでもう可算順序数を(どんなに大きなものでも)ただ突っ込むのはやめにしましょう。BEAFを使って一から順序数を定義しながら進めており、本筋からそれているからです。

ところで、これでどこまでの順序数を定義したことになるでしょうか?かなりたくさんです。

  • \(\Gamma_0 = \{\omega, \omega, 1, 2\}\) (膨張配列)
  • \(\vartheta(\Omega^2) = \{\omega, \omega, 1, 1, 2\}\)
  • \(\vartheta(\Omega^\omega) = \{\omega, \omega (1) 2\}\)
  • \(\vartheta(\Omega^\Omega) = \{\omega, \omega, 2 (1) 2\}\) (英語版のソースのコメントより: これが本当かどうかは分からない。LVO のページからコピーしただけ。)
  • \(\vartheta(\varepsilon_{\Omega + 1}) = \{\omega, \omega (\varepsilon_0) 2\}\)

現時点でのこの表記の限界は \(\vartheta(\Omega_\omega)\) となります。これは、ものすごい成果です!

レギオン配列[]

順序数が分からない読者の皆さん、ここまでお待ちいただいてありがとうございます!ここまでで、レギオンを使わないBEAFである「サブレギオン BEAF」の説明をしました。Bowers は、ここまでのすべてを「L空間」(L-space) と呼びました。

ここで、配列次元演算子 & がよみがえります。どんどんと強い表記が出てきていますが、& も同様に強くなります。ここまでの配列次元演算子では、たとえば {3, 3, 3}&3 (トリアクルス) によってペンテーション配列が定義出来ました。配列次元演算子は、常に最も強い表記を対角化することができます。

トリアクルスは、 (3&3)&3 とも書くことができます。配列次元演算子は左結合なので、この括弧を外して 3&3&3 と書くことができます。そうすると、自然に新しい演算子 ♦ が導入され、 bp = b&b&...&b&bp 回繰り返したものと定義できます。この演算子は、レギオンを使わないBEAFの限界を示していて、これまでに定義した関数の中で最も強力になります。

\(b♦p\) という式の形から、少し \(b^p\) を思い出させられるので、2行配列の時にやったことと同じトリックを使ってみましょう。この「レベル2のサブレギオンBEAF」を、基数ルールを \(b♦p\) に定義し直すことで作ることができます。

2行配列表記の時にやったように、高レベルのサブレギオン BEAF へと拡張して、レベルは配列の一部となります。ここでは、すぐにレベルを配列の中に入れてしまいましょう。

\(\{b, p / 2\} = b♦p\)

スラッシュの境界は、レギオン空間と言われる新しい空間の種類の区切りです。パイロットの 2 は2番目のレギオンにあります。これはちょうど、平面配列表記の時に、パイロットを2行目に移動したのと同じことです。レギオンのプライムブロックは \(b♦p\) となり、したがってたとえば \(\{b, p / 3\} = \{b♦p / 2\}\) となります。

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

レギオンは列やプレーン、あるいはこれまで定義してきた構造よりも大きな空間を形成するので、2番目のレギオンに複数の要素を置くことができます。

\(\{b, p / 1 / 2\} = \{b♦p / b♦p\}\)

また、2つ以上のレギオンを置くこともできます。

\(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) (\(p\)つのレギオン)
\(\{b, p (/0,1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) (レギオンが\(p^{p}\)構造を形成する)

そして、レギオン自体もあらゆる大きさの次元構造を取ることができます。

\(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\)の別の表記は\(p \&\& b\)になります。同様に、\(\{b, p (/(1)1) 2\} = p^p \&\& b\)とできるので、演算子&&は&に似たような働きをしますが、要素の代わりにレギオンが入ります。

ここでは、b♦♦pをb&&b&&...&&b&&bのp回という意味で使い、区切り記号に「レギオン・レギオン空間」\(//\)を導入します。

\(\{b, p // 2\} = b♦♦p = b \&\& b \&\& \ldots \&\& b \&\& b\)
\(\{b, p (//1) 2\} = \{b♦♦p / b♦♦p / \ldots / b♦♦p / b♦♦p\} = b \&\&\& p\)
\(\{b, p /^n 2\} = b♦^np = b \&^n b \&^n \ldots \&^n b \&^n b\)
\(\{b, p (/^n1) 2\} = \{b♦^np / b♦^np / \ldots / b♦^np / b♦^np\} = b \&^{n + 1} p\)

拡張は簡単です。

\(\{b, p (1)/ 2\} = \{b, p /^p 2\} = b (1)\& p\)
\(\{b, p ///(1)///(1)/// 2\}\)

なぜレギオン自体に多次元構造を与えないのでしょう?問題は、これを定義する必要があるということです。Lをレギオンの構造としましょう。Lはレギオンを除くすべての構造より大きいです。(つまりLはXが行であるのと同じように、レギオンとなります。) L = {X, X / 2}とも言えますが、回りくどいです。とにかく、レギオンのプライムブロックは\(b♦p\)になります。

レギオン2個は\(2L\)構造、レギオン1列は\(XL\)構造、レギオン1個は\(L^2\)構造となります。ここからは、{X, X, X}などと同じように、\(\{L, L\}\)、\(\{L, L, L\}\)、\(\{L, X (1) 2\} = X\&L\)など、Lを配列の中に入れることができます。残念ながら、この時点ではセパレータの表記法はありませんが、Bowersはbを底、pをプライムとして解かれる\(\{L, L\}\) 構造を意味する\(\{L, L\}_{b, p}\)という表記法を提示しました。

Lをどんどん大きな配列に落としていくと、\(\{L, L / 2\}\)というランドマーク、ルギオン空間に到達できます。Bowersはこの\(L2\)も区切り記号\と演算子\(a@b\)(aレギオン記号配列のb)を使って書いています。

定式化[]

ここでは、順序数を持つレギオン配列の定義について簡単に説明しましょう。まず、配列次元演算子には基底、プライム、構造の型の3つの部分があることに気が付くと思います。例えば, \(3\&4\) は 基底が4, プライムが3, 構造の型がX。そして\(3 \uparrow\uparrow\uparrow 4 \& 5\)は基底が5, プライムが3, 構造の型が\(X \uparrow\uparrow\uparrow 4\)といったようにです。Bowersのちょっとした表記の乱れは、3つの引数を持つ配列次元演算子で修正できます。

\(\lambda(b, p, \xi) = \{(0, b), (1, p), (\xi, 2)\}\)

つまり基底\(b\)、プライム\(p\)、そして \(\xi\)の位置にある数2です。 普通\(\xi\)は極限順序数ですが、この関数は、任意の\(\xi > 1\)を配置できます。

レギオン空間の序数は名前のない順序数\(\vartheta(\Omega_\omega) = \{\omega, \omega / 2\}\)で、 その基本列は\(\vartheta(\Omega_\omega)[1] = \omega,\,\vartheta(\Omega_\omega)[2] = \lambda(\omega, \omega, \omega),\,\vartheta(\Omega_\omega)[3] = \lambda(\omega, \omega, \lambda(\omega, \omega, \omega)),\cdots\)と続いていきます。これは、先に定義した \(\vartheta(\Omega_\omega)\)構造のプライムブロックを定義するものです。

(ここから先は、英語版ではコメントアウトされていますが、そのまま載せてみます。)

この順序数はBowersのL空間に直接類似しています。順序数で物事を変換するには、Lを\(\vartheta(\Omega_\omega)\)に置き換えればよいのです。

  • \(2L = \vartheta(\Omega_\omega)2\), separator "/ 1 /"
  • \(XL = \vartheta(\Omega_\omega)\omega\), separator "(/1)"
  • \(L^2 = \vartheta(\Omega_\omega)^2\), separator "//"
  • \(\{L, X\} = \vartheta(\Omega_\omega)^\omega\), separator "(1)/"
  • \(\{L, L\} = \vartheta(\Omega_\omega)^{\vartheta(\Omega_\omega)}\)
  • \(\{L, L, 2\} = \vartheta(\Omega_\omega) \uparrow\uparrow \vartheta(\Omega_\omega)\)
  • \(\{L, L (1) 2\} = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \omega)\)
  • \(\{L, L (0, 1) 2\} = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \varepsilon_0)\)
  • \(\{L, L / 2\} = L2 = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \vartheta(\Omega_\omega))\), separator "\"
  • \(\{L2, L2 \backslash 2\} = L3 = \lambda(L2, L2, L2)\), separator "|"
  • \(\{L3, L3 | 2\} = L4 = \lambda(L3, L3, L3)\), separator "-"
  • \(\{L4, L4 - 2\} = L5 = \lambda(L4, L4, L4)\)
  • \(LX = \vartheta(\Omega_{\omega^2})\)
  • \(L(X^2) = \vartheta(\Omega_{\omega^3})\)
  • \(L(X^X) = \vartheta(\Omega_{\omega^\omega})\)
  • \(LL = \vartheta(\Omega_\Omega)\)
  • \(LLL = \vartheta(\Omega_{\Omega_\omega})\)
  • \(L^X = \psi(\psi_I(0))\)

私たちの記法はそれ自身と衝突しています。\(L^X\)はすでに定義したはずなのですが、なぜ今回はもっと大きくなるのでしょう?BowersのL表記は曖昧さのためにここで最大となりますが、理解のために続けて使う(悪用する)ことにします。

  • \(L^{2X} = \psi(\psi_I(1))\)
  • \(L^{X^2} = \psi(\psi_I(\omega))\)
  • \(L^{X^X} = \psi(\psi_I(\omega^\omega))\)
  • \(L^L = \psi(\psi_I(\vartheta(\Omega_\omega)))\)
  • \(\{L, 3, 2\} = \psi(\psi_I(\vartheta(\Omega_\omega)))\)
  • \(\{L, 4, 2\} = \psi(\psi_I(\psi(\psi_I(\vartheta(\Omega_\omega)))))\)
  • \(\{L, X, 2\} = \psi(I)\)
  • \(\{L, L, 2\} = \psi(I \vartheta(\Omega_\omega))\)
  • \(\{L, \{L, L, 2\}, 2\} = \psi(I \psi(I \vartheta(\Omega_\omega)))\)
  • \(\{L, X, 3\} = \psi(I^2)\)
  • \(\{L, X, n\} = \psi(I^{n-1})\)
  • \(\{L, X, X\} = \psi(I^\omega)\)
  • \(\{L, L / 2\} = \)

これをやめる正当な理由はありませんが、BEAFは伝統的にここで終了します。この最後の順序数はミーミーミーロッカプーワ・ウンパのレベルを表しています。

外部リンク[]

Advertisement