Array Notation

 日本語に訳すと『配列表記』とでも訳せるだろうか?もしくはタワー、チェーンがカタカナ語のまま訳されている事を考えると『アレー(アレイ)表記』が適切かも知れない。考案者はJonathan Bowers(1969~)である。
 日本ではまだ殆ど知られていない?表記法で、複数の数字を1つの数にまとめ上げる演算法はアッカーマン関数やチェーン表記と似ているが、チェーン表記よりも効率的に数の大きさを爆発させる事ができる。
 ふぃっしゅ数をまともに書き表すためには、オリジナルのチェーン表記では足りないと言われる。チェーンの拡張表記や、このアレー表記といったものが必要になってくるだろう。また、アレー表記にも拡張表記が考案されており、その最終形態はBEAFと呼ばれるものである。


表記法

・このように、{}の中に数字を,区切りで入れていく。
 \{a,b,c,\dots\}


規則

(1) 1つ組および2つ組のアレー表記。
 \{a\}=a 及び \{a,b\}=a^b である。

(2) 最後の数字が1の時はこれを落とせる。
 \{a,b,c,\dots,y,z,1\}=\{a,b,\dots,y,z\}

(3) 2番目の数字が1の時はそれ以降を全て落とせる。
 \{a,1,b,\dots,z\}=\{a\}=a

ここまではチェーン表記と一緒。ここからが異なる。

(4) 3番目の数字が1の時、それ以降を全て落とす・・・のではありません。
 言葉で説明するのは難しいのでとりあえず下図を見よう。

 \{a,b,\underbrace{1,\dots,1}_{n\text{ copies of }1},1,c,d,\dots,z\}
 
=\{a,a,\underbrace{a,\dots,a}_{n\text{ copies of }a},
\{a,b-1,\underbrace{1,\dots,1}_{n\text{ copies of }1},1,c,d,\dots,z\}
,c-1,d,\dots,z\}}

(5) (1)~(4)のいずれでも無い時、次の様に変形する。
 ※チェーン表記が右側から変形していくのに対し、こちらは左側から変形していく。
 ※なお、4番目以上の数字が1の時も、こちらの変形を適応させる事となる。
 \{a,b,c,d,\dots,z\}=\{a,\{a,b-1,c,d,\dots,z\},c-1,d,\dots,z\}


性質

・3つ組アレーは3つ組チェーンと一致します。つまりタワー表記とも一致します。
 \{a,b,c\}=a\rightarrow b\rightarrow c=a\uparrow^c b

・規則(4)を逆に辿ると、{a,a,a,…と連続しているArrayは次の用に変形する事ができます。aの列の多くを1に変換する代わりに、cの値が一つ上がります。
 おそらくarrayの本質を理解する上で重要なヒントになる事だと思いますし、数の大きさをarrayで見積もろうとするときに頻繁に使うことになるだろうと思うので、是非頭に入れておきましょう。
 ふぃっしゅ氏は同様の変形手法に対して『繰り上がり』という語を与えています。

\{a,a,\underbrace{a,a,\dots,a,a}_{n},c,d,\dots,z\}
=\{a,2,\underbrace{1,1,\dots,1,1}_{n},c+1,d,\dots,z\}

タグ:

+ タグ編集
  • タグ:
最終更新:2013年12月16日 20:53