コンウェイのチェーン表記

コンウェイのチェーン表記（コンウェイのチェーンひょうき、）とは、1995年にイギリスの数学者ジョン・ホートン・コンウェイによって導入された巨大数の表記法の一つである。
クヌースの矢印表記やアッカーマン関数などより比較的強い演算である。具体的には、3つ組ではクヌースの矢印表記と等価だが、更に長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数を表すことができる。
導入.
加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって と表して、さらに の反復を （テトレーション）、 の反復を （ペンテーション）、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。
コンウェイのチェーン表記は、このクヌースの矢印表記の一般化、拡張である。以下チェーンの各項はすべて自然数であるものとする。
コンウェイはまず長さが のチェーンを、クヌースの矢印表記を用いて次のように与えた。
このチェーンによって を書き換えると次のような式になる。これは末尾 のチェーンを末尾 のチェーンに分解する式となっている。
この式の を部分チェーン に置き換えることで、長さが 以上のチェーンに対する式が得られる。
さらにコンウェイはチェーン末尾のは無視されるとした。従って式 , を繰り返して末項を にすることで、長さが 短いチェーンへと分解することができる。
また、この規則から長さが のチェーンは累乗となる。
さらにコンウェイはチェーン途中のの右側の全ても無視されるとした。それにより4つ組チェーンの計算も行える。
定義.
次のようにチェーンを定義する。
さらに を正の整数、 を部分チェーンとするとき、チェーンについて以下が成り立つ。
ここで関数 を とおくと、最後の二つの条件は次のようにも述べられる。但し は の 回反復合成である。
別の定義.
上記以外の書き方でされている定義もある。
書き方は違うが、意味は同じである。
以下の4つの定義でチェーン表記を定義することも可能である。
チェーン表記formula_10(a~zは正の整数)を以下のように定義する。
性質.
以下、項（正の整数）を小文字 、チェーン（および部分チェーン）を大文字 で表す。
例.
以下は長さが のチェーンの計算例である。
以下は長さが のチェーンのクヌースの矢印表記による展開例(縦横展開)である。
アッカーマン関数.
アッカーマン関数はコンウェイのチェーン表記へ置き換えられる:
よって
グラハム数.
グラハム数 formula_22 それ自体を、コンウェイのチェーン表記を用いて簡潔に表す事は出来ない。しかし、仲介させる関数を formula_23 と定義することで formula_24 と表記できる。(写像の冪を参照。)又、 formula_25 である。
コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。
formula_30
数formula_31 は65よりもはるかに大きいので、formula_26はグラハム数よりはるかに大きい。
さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。formula_33はコンウェイのテトラトリと呼ばれる。
CG関数.
コンウェイとに共同制作された単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:
formula_34
その出力を順に並べると:
この関数は予測されるように、とても急速に増大する。
この関数は急増加関数でformula_35と近似できる。
拡張チェーン系の表記.
このチェーン表記にも、次のような拡張表記が考案されている。
ピーター・ハーフォードによる拡張.
Webデベロッパーで統計学者のピーター・ハーフォードは、2011年にこの表記法の拡張を定義した。
formula_36（あくまでformula_37がformula_38本、という意味）
formula_39は既に cg(a) と同等であり、関数formula_40は cg(n) よりも大きな増加速度を持つ。
定義.
formula_41formula_42formula_43
formula_44formula_42formula_46
formula_47formula_42formula_49
formula_50formula_42formula_49
formula_53formula_42formula_55
formula_56
この表記は拡張チェーン表記と呼ばれ、同じ拡張チェーン系の回転矢印表記と同じくらいの強さである。歴史的には、回転矢印表記が先に考案され、後にそれとは独立にこのハーフォードの拡張チェーン表記が考案されたが、現在ではチェーン表記の拡張としてはより定義や記述がすっきりしているこのハーフォード式が標準的となっている。もっとも、拡張チェーン系表記のレベルの巨大数は、巨大数論的に中途半端なポジションということもあり、そのレベルの巨大数を表す場合は拡張チェーン系表記より強力な配列表記（海外）あるいは多変数アッカーマン関数（日本）を用いるのが最も主流となっている。
この表記は急増加関数でformula_57と近似できる。
ちなみに多変数アッカーマン関数でformula_58程度である。
彼は上記以外の規則は変更しなかった。（一つのチェーンにおいては1種類の矢印のみを使用できた。つまりb≠dの際formula_59は規則違反になる）
もし更に規則を若干訂正し
formula_60
とすると、formula_59は規則違反では無くなる上に表記法が更に強くなる(あまり意味はない。つまり、本質的に大きくする手段は別にある。)。
クリス・バードによる拡張（回転矢印表記）.
矢印表記やチェーン表記の拡張版として、クリス・バード(Chris Bird)によって考案された回転矢印表記というものもある。この表記法ではその矢印の回転を繰り返すことにより、非拡張チェーンを遥かに超える巨大な数が表記可能となる。これは2chの巨大数スレッドで一時期ある程度使われたことがある。ただしこれは発想こそ単純であるものの、ピーター・ハーフォードの拡張チェーン表記とほぼ同等の増加速度であり、それと比べると若干定義が複雑なことと、配列表記の方が効率的に数の大きさを爆発させることができることもあり、近年ではこの回転矢印表記が用いられることはほとんどなくなっている。
その他.
その他の拡張チェーン系の表記としては、次のようなものが考えられている。
更に、ハーフォード式・バード式（回転矢印表記）・Aeton式の三者よりも強力な表記として、
その他.
チェーン表記（およびその拡張表記）では、数の大きさを評価するための重要度は次の通りである：
（拡張チェーン系の表記におけるチェーンの拡張レベル＞）チェーンの長さ＞末尾の変数＞末尾から2番目の変数＞それ以外の変数
チェーン表記（およびその拡張表記）では、どの変数の値が増えても厳密には数は増えるものの、特に5つ組以上のチェーンでは、末尾の2つ以外の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。また末尾の変数が巨大数レベルになれば、末尾から2番目の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。
ふぃっしゅ数バージョン1はCG関数でCG(グラハム数)、つまりformula_62より遥かに大きい。ふぃっしゅ数バージョン1はピーター・ハーフォードの拡張チェーン表記による近似で≒5→264→22、ふぃっしゅ数バージョン2は同表記による近似で≒3→643→642程度の大きさとなる。このようにふぃっしゅ数はバージョン1とバージョン2までは、拡張チェーン系の表記の範囲で近似可能であるが、バージョン3以上になるとそのレベルをも遥かに本質的に超えてしまう。
チェーン表記とは異なった規則により、チェーン表記（およびその拡張表記）よりも効率的に数の大きさを爆発させることができる表記として、配列表記があり、それにも拡張表記が考案されており、その最終形態にはBEAFとバードの配列表記がある。具体的には、チェーン表記で表される数は多変数アッカーマン関数では3変数程度で配列表記では4変数程度、ピーター・ハーフォードの拡張チェーン表記（あるいはクリス・バードの回転矢印表記）で表される数は多変数アッカーマン関数では4変数程度で配列表記では5変数程度のレベルとなる。チェーン表記およびその拡張表記と配列表記との比較（近似・大小関係）については配列表記#チェーン表記との比較および回転矢印表記#他表記との比較を参照のこと。
BEAFの配列表記は多変数アッカーマン関数と同じくらいの増加速度を持ち、BEAFそのものはさらに大きい増加速度を持つ（テトレーション配列など）。