BEAF

BEAF (Bowers Exploding Array Function) とは、Jonathan Bowersによって考案された、巨大数を表すための表記法の一つである^[1]。クヌースの矢印表記を拡張して配列表記を作り、更にその配列表記を拡張して作られている。

現代^[いつ?]の巨大数界のかなりの範囲をカバーできる巨大数表記法であることが想定されている。ただし2021年現在、BEAFの定義が数学的に意味を持つように定式化されているのはテトレーション配列のレベルまでであり、テトレーション配列を超えるレベルを表すことが想定されている記号や表記法も考案されているが、これは定義が未完成である。

定義[2]

「基数」 (b) は、配列の1番目の要素である。
「プライム」 (p) は、配列の2番目の要素である。
「パイロット」は、プライムの次の最初の1ではない要素である。パイロットは3番目以降の要素となる。
「副操縦士」は、パイロットの1つ前の要素である。パイロットが行の中で1番目の要素であれば、副操縦士は存在しない。
「構造」は配列の一部で、配列よりも低次元なグループによって構成されるものである。構造は、要素 (X^0 と書く)、行 ( X^1と書く)、平面 (X^2)、3次元の領域 (X^3)、4次元のフルーン (X^4)、さらに高次元の構造 (X^5, X^6 等)、そしてのようなテトレーション構造、といった可能性がある。さらに、そこから先はペンテーション構造、ヘキセーション構造, ..., 膨張構造, ... と続く。
「前の要素」は、パイロットと同じ行にあり、パイロットよりも前にある要素である。「前の行」は、パイロットと同じ平面にあり、パイロットよりも前にある行である。「前の平面」は、パイロットと同じ領域にあり、パイロットよりも前にある平面である。同様に、定義を続けることができる。これらは「前の構造」と呼ばれる。
構造 Sの「プライムブロック」は、構造を表記する記号の Xをすべて p に置き換えたものである。例えば、もしS=X^3であれば、プライムブロックはp^3 、すなわち一辺の長さが p の立方体となる。 X^X構造のプライムブロックはp^p 、すなわち一辺が pの p次元超立方体となる。
「飛行機」は、パイロットと、すべての前の要素と、すべての前の構造のプライムブロックを含んだものである。
「乗客」は、飛行機の中のパイロットと副操縦士以外の要素である。
配列 A の値は u(A)と表記する。

ルール[2]

プライムルール: もし p=1 であれば、u(A)=b とする。
初期ルール: もしパイロットがなければ、u(A)=b^p とする。
破滅ルール: 1 も 2 もあてはまらない場合には、次のようにする。
1. パイロットの値を 1 減らす。
2. 副操縦士の値を元の配列のプライムを1減らしたものに置き換える。
3. すべての乗客を b にする。
4. 配列のそれ以外の要素は変化しない。

解説

ハイパー演算子

まず、BEAFの元になった、ハイパー演算子について記す。詳細はハイパー演算子を参照。

指数表記

乗算は、加算の反復によって定義できる。

a\times b=\underbrace {a+a+\dots +a} _{b{\text{　個　の　}}a}

同様に、冪乗は、乗算の反復によって定義できる。

a^{b}=\underbrace {a\times a\times \dots \times a} _{b{\text{　個　の　}}a}

拡張

クヌースは、 $\uparrow \uparrow$ を、冪乗の繰り返しを表す演算子として再帰的に定義した。

a\uparrow \uparrow b=a\uparrow (a\uparrow \uparrow (b-1))=\underbrace {a\uparrow a\uparrow \cdots \uparrow a} _{b{\text{ 個　の　}}a}=\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} _{b{\text{ 個　の }}a}

ここで、 $a\uparrow \uparrow 0=1$ である。これを、テトレーション、またはその見た目からタワー（power tower^[3]）とも呼ぶ。同様に、 $\uparrow \uparrow \uparrow$ も次のように定義できる。

a\uparrow \uparrow \uparrow b=a\uparrow \uparrow (a\uparrow \uparrow \uparrow (b-1))=\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} _{b{\text{ 個　の　}}a}

ここで、 $a\uparrow \uparrow \uparrow 0=1$ である。さらに、n本の上向き矢印に対して再帰的に定義すると、次のようになる。

a\uparrow ^{n}b={\begin{cases}1,&{\mbox{if }}b=0\\a^{b},&{\mbox{if }}n=1\\a\uparrow ^{n-1}\left(a\uparrow ^{n}\left(b-1\right)\right),&{\mbox{otherwise}}\end{cases}}

ここで、a, b, n は整数であり、a ≥ 1,　b ≥ 0,　n ≥ 1である。また、 $\uparrow ^{n}$ は $\uparrow$ をn本並べたものを表す。

計算例

$2\uparrow ^{2}2=2\uparrow 2=4$

$2\uparrow ^{2}3=2\uparrow 2\uparrow 2=2\uparrow 4=16$

$2\uparrow ^{2}4=2\uparrow 2\uparrow 2\uparrow 2=2\uparrow 16=65536$

$3\uparrow ^{2}2=3\uparrow 3=27$

$3\uparrow ^{2}3=3\uparrow 3\uparrow 3=3\uparrow 27=7625597484987$

$3\uparrow ^{2}4=3\uparrow 3\uparrow 3\uparrow 3=3\uparrow 7625597484987\approx 10^{10^{12.88}}$

$3\uparrow ^{3}2=3\uparrow ^{2}3=7625597484987$

$3\uparrow ^{3}3=3\uparrow ^{2}3\uparrow ^{2}3=\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} _{7625597484987{\text{ 個　の }}3}=\underbrace {3^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} _{7625597484987{\text{ 個　の }}3}$

このように、矢印の本数を増やすと、値が爆発的に増加することがわかる。これにより、非常に大きな自然数を表現する事が可能である。

注意点

$a\uparrow ^{n}b=a\uparrow ^{n-1}\left(a\uparrow ^{n}\left(b-1\right)\right)$

からもわかるように、複数の演算子が並んでいるときは、右から順に計算していく。すなわち、

$3\uparrow \left(2\uparrow 3\right)=3\uparrow 8=3^{8}=6561$

であって、

$\left(3\uparrow 2\right)\uparrow 3=9\uparrow 3=9^{3}=729$

ではない。

括弧を使った演算子表記

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

$a\uparrow ^{n}b=a\{n\}b$

例えば、 $3\{6\}4=3\uparrow ^{6}4$ である。この表記法は、単に矢印表記を書き換えたに過ぎないが、Bowersは{}を1重から2重に増やすことで、拡張した。

$a\{\{1\}\}b=\underbrace {a\{a\{\cdots \{a\{a} _{b{\text{ 個　の }}a}\}a\}\cdots \}a\}a=\left.{\begin{matrix}a\underbrace {\uparrow \cdots \cdots \uparrow } _{a\underbrace {\uparrow \cdots \cdots \uparrow } _{\underbrace {\vdots } _{a\underbrace {\uparrow \cdots \uparrow } _{a{\text{本}}}a{\text{本}}}}a{\text{本}}}a\end{matrix}}\right\}b{\text{層}}$

Bowersはこれを、aのb重膨張と呼んだ。

{{}}の中を増やしていくと、次のようになる。

$a\{\{2\}\}b=\underbrace {a\{\{1\}\}a\{\{1\}\}\cdots \{\{1\}\}a\{\{1\}\}a} _{b{\text{ 個　の }}a}$

$a\{\{3\}\}b=\underbrace {a\{\{2\}\}a\{\{2\}\}\cdots \{\{2\}\}a\{\{2\}\}a} _{b{\text{ 個　の }}a}$

$a\{\{n\}\}b=\underbrace {a\{\{n-1\}\}a\{\{n-1\}\}\cdots \{\{n-1\}\}a\{\{n-1\}\}a} _{b{\text{ 個　の }}a}$

{}を二重から三重にすると、aのb重爆発となる。

$a\{\{\{1\}\}\}b=\underbrace {a\{\{a\{\{\cdots \{\{a\{\{a} _{b{\text{ 個　の }}a}\}\}a\}\}\cdots \}\}a\}\}a$

$a\{\{\{2\}\}\}b=\underbrace {a\{\{\{1\}\}\}a\{\{\{1\}\}\}\cdots \{\{\{1\}\}\}a\{\{\{1\}\}\}a} _{b{\text{ 個　の }}a}$

$a\{\{\{3\}\}\}b=\underbrace {a\{\{\{2\}\}\}a\{\{\{2\}\}\}\cdots \{\{\{2\}\}\}a\{\{\{2\}\}\}a} _{b{\text{ 個　の }}a}$

$a\{\{\{n\}\}\}b=\underbrace {a\{\{\{n-1\}\}\}a\{\{\{n-1\}\}\}\cdots \{\{\{n-1\}\}\}a\{\{\{n-1\}\}\}a} _{b{\text{ 個　の }}a}$

{}を四重にすると爆轟、五重にするとペントネーションと続く。また、

$a\underbrace {\{\{\{\cdots \{\{} _{d{\text{ 重}}}c\}\}\cdots \}\}\}b=a\{c\}^{d}b$

と書いて圧縮することができる。すなわち、

$a\{c\}^{d}b={\begin{cases}4&({\text{if}}.a=b=2)\\a\uparrow ^{c}b&({\text{if}}.d=1)\\a&({\text{if}}.b=1)\\a\{a\{c\}^{d}(b-1)\}^{d-1}a&({\text{if}}.c=1)\\a\{c-1\}^{d}a\{c\}^{d}(b-1)&({\text{others}})\end{cases}}$

である。

配列表記

→詳細は「配列表記」を参照

$a\{c\}^{d}b=\{a,b,c,d\}$

と書き換えることが可能である。この表記を多変数へ一般化したものは配列表記と呼ばれ、クヌースの矢印表記やコンウェイのチェーン表記や拡張チェーン表記や回転矢印表記よりも強力な表記である。

配列表記は以下のように定義される。

${\begin{array}{lcl}\{{a,b}\}=a^{b}\\\{{A,1}\}=\{{A}\}\\\{{a,1,A}\}=a\\\{{a,b+1,\underbrace {1\cdots ,1} _{n},1,c+1,A}\}=\{{a,a,\underbrace {a\cdots ,a} _{n},\{{a,b,\underbrace {1\cdots ,1} _{n},c,A}\},c,A}\}\\\{{a,b+1,c+1,A}\}=\{{a,\{a,b,c+1,A\},c,A}\}\end{array}}$ ^[4]

配列表記は、急成長階層で $f_{\omega ^{\omega }}$ に近似され、多変数アッカーマン関数と同じくらいの強さである。

拡張配列表記

Bowersは配列表記をさらに多次元へ一般化し、拡張配列表記を作った。^[5]