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

コンウェイのチェーン表記とは、1995年にイギリスの数学者ジョン・ホートン・コンウェイによって導入された巨大数の表記法の一つである。

クヌースの矢印表記やアッカーマン関数などより比較的強い演算である。具体的には、3つ組ではクヌースの矢印表記と等価だが、更に長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数を表すことができる。

1. 導入
-----

加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって mvar と表して、さらに ↑}} の反復を ↑↑}}、↑↑}} の反復を ↑↑↑}}、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。

コンウェイのチェーン表記は、このクヌースの矢印表記の一般化、拡張である。以下チェーンの各項はすべて自然数であるものとする。

コンウェイはまず長さが 3}} のチェーンを、クヌースの矢印表記を用いて次のように与えた。

このチェーンによって }} を書き換えると次のような式になる。これは末尾 → mvar のチェーンを末尾 → (mvar のチェーンに分解する式となっている。

この式の a}} を部分チェーン X}} に置き換えることで、長さが 4}} 以上のチェーンに対する式が得られる。

さらにコンウェイはチェーン末尾の→ 1}}は無視されるとした。従って式 }}, }} を繰り返して末項を 1}} にすることで、長さが 1}} 短いチェーンへと分解することができる。

また、この規則から長さが 2}} のチェーンは累乗となる。

さらにコンウェイはチェーン途中の→ 1}}の右側の全ても無視されるとした。それにより4つ組チェーンの計算も行える。

2. 定義
-----

次のようにチェーンを定義する。

任意の正の整数は、長さ 1}} のチェーンである。
長さ n}} のチェーンに、右向き矢印 →}} と正の整数を繋げたものは、長さ mvar のチェーンとなる。さらに mvar を正の整数、X}} を部分チェーンとするとき、チェーンについて以下が成り立つ。

長さ 0}} のチェーンは、1}} に等しい。
長さ 1}} のチェーン p}} は、p}} に等しい。
長さ 2}} のチェーン mvar は、mvar に等しい。
長さ 3}} のチェーン mvar は mvar に、mvar は 1}} に各々等しい。
mvar は X}} に等しい。即ちチェーン右端の → 1}} は取り除くことができる。
mvar は X}} に等しい。即ちチェーン右端の → 1 → mvar は取り除くことができる。
mvar は に等しい。ここで関数 f}} を mvar とおくと、最後の二つの条件は次のようにも述べられる。但し mvar は f}} の p}} 回反復合成である。

2.1. 別の定義
---------

上記以外の書き方でされている定義もある。

書き方は違うが、意味は同じである。

以下の4つの定義でチェーン表記を定義することも可能である。

チェーン表記を以下のように定義する。

3. 性質
-----

以下、項を小文字 mvar 、チェーンを大文字 mvar で表す。

長さ 3}} のチェーンは、ハイパー演算子、クヌースの矢印表記、および配列表記による表示をもつ。
任意のチェーンに対し常にただ一つの整数が定まる。
長さ mvar のチェーン mvar は適当な mvar によって mvar と変形できる。即ち先頭から mvar 項を保ったまま長さを 1}} 短くできる。
mvar から始まるチェーン mvar は mvar の冪 mvar となる。
1}} から始まるチェーン 1 → mvar は 1}} に等しい。
1}} より後の項はすべて無視することができる。
先頭に 2}} が連なったチェーン 2 → 2 → mvar は 4}} に等しい。
末尾に 2}} が連なったチェーン mvar は mvar に等しい。
p-q}} は p →  → 0) → }} に等しい。
p/q}} は p →  → 1) → 0}} に等しい。
p →  → 2) → 1 =}} psup は psup に等しい。

4. 例
----

以下は長さが 3}} のチェーンの計算例である。

以下は長さが 4}} のチェーンのクヌースの矢印表記による展開例である。

5. アッカーマン関数
-----------

アッカーマン関数はコンウェイのチェーン表記へ置き換えられる:

//m// > 2の際 //A// =  → //) − 3 よって

//n// > 2の際 2 → //n// → //m// = //A// + 3   =   −1 と //A//   =   1に対応し、論理的に加算できる。)

6. グラハム数
--------

グラハム数 それ自体を、コンウェイのチェーン表記を用いて簡潔に表す事は出来ない。しかし、仲介させる関数を と定義することで と表記できる。又、 である。

コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。

数 は65よりもはるかに大きいので、はグラハム数よりはるかに大きい。 さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。はコンウェイのテトラトリと呼ばれる。

7. CG関数
-------

コンウェイとに共同制作された単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:

その出力を順に並べると:

この関数は予測されるように、とても急速に増大する。

この関数は急増加関数でと近似できる。

8. 拡張チェーン系の表記
-------------

このチェーン表記にも、次のような拡張表記が考案されている。

8.1. ピーター・ハーフォードによる拡張
---------------------

Webデベロッパーで統計学者のピーター・ハーフォードは、2011年にこの表記法の拡張を定義した。

は既に cg と同等であり、関数は cg よりも大きな増加速度を持つ。

8.1.1. 定義
---------

この表記は拡張チェーン表記と呼ばれ、同じ拡張チェーン系の回転矢印表記と同じくらいの強さである。歴史的には、回転矢印表記が先に考案され、後にそれとは独立にこのハーフォードの拡張チェーン表記が考案されたが、現在ではチェーン表記の拡張としてはより定義や記述がすっきりしているこのハーフォード式が標準的となっている。もっとも、拡張チェーン系表記のレベルの巨大数は、巨大数論的に中途半端なポジションということもあり、そのレベルの巨大数を表す場合は拡張チェーン系表記より強力な配列表記あるいは多変数アッカーマン関数を用いるのが最も主流となっている。

この表記は急増加関数でと近似できる。

ちなみに多変数アッカーマン関数で程度である。

彼は上記以外の規則は変更しなかった。

もし更に規則を若干訂正し

とすると、は規則違反では無くなる上に表記法が更に強くなる。

8.2. クリス・バードによる拡張
-----------------

矢印表記やチェーン表記の拡張版として、クリス・バードによって考案された回転矢印表記というものもある。この表記法ではその矢印の回転を繰り返すことにより、非拡張チェーンを遥かに超える巨大な数が表記可能となる。これは2chの巨大数スレッドで一時期ある程度使われたことがある。ただしこれは発想こそ単純であるものの、ピーター・ハーフォードの拡張チェーン表記とほぼ同等の増加速度であり、それと比べると若干定義が複雑なことと、配列表記の方が効率的に数の大きさを爆発させることができることもあり、近年ではこの回転矢印表記が用いられることはほとんどなくなっている。

8.3. その他
--------

その他の拡張チェーン系の表記としては、次のようなものが考えられている。

チェーンを角括弧で括り、[a→b]nのように拡張レベルを角括弧の外に書いて、2変数の場合の右側の数bを1つ下のレベルのチェーンのaの個数とするAeton式更に、ハーフォード式・バード式・Aeton式の三者よりも強力な表記として、

拡張レベルを多変数化して例えば3[3,1,2]3[3,1,2]3などのように書く配列チェーン表記
ハーフォード式と同じように矢印に添字を付ける→nという表記を使いながら、添字が揃っていなくても計算でき、かつレベルの違いを活かして強くした混合チェーン表記

9. その他
------

チェーン表記では、数の大きさを評価するための重要度は次の通りである：

チェーンの長さ＞末尾の変数＞末尾から2番目の変数＞それ以外の変数

チェーン表記では、どの変数の値が増えても厳密には数は増えるものの、特に5つ組以上のチェーンでは、末尾の2つ以外の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。また末尾の変数が巨大数レベルになれば、末尾から2番目の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。

ふぃっしゅ数バージョン1はCG関数でCG、つまりより遥かに大きい。ふぃっしゅ数バージョン1はピーター・ハーフォードの拡張チェーン表記による近似で≒5→264→22、ふぃっしゅ数バージョン2は同表記による近似で≒3→643→642程度の大きさとなる。このようにふぃっしゅ数はバージョン1とバージョン2までは、拡張チェーン系の表記の範囲で近似可能であるが、バージョン3以上になるとそのレベルをも遥かに本質的に超えてしまう。

チェーン表記とは異なった規則により、チェーン表記よりも効率的に数の大きさを爆発させることができる表記として、配列表記があり、それにも拡張表記が考案されており、その最終形態にはBEAFとバードの配列表記がある。具体的には、チェーン表記で表される数は多変数アッカーマン関数では3変数程度で配列表記では4変数程度、ピーター・ハーフォードの拡張チェーン表記で表される数は多変数アッカーマン関数では4変数程度で配列表記では5変数程度のレベルとなる。チェーン表記およびその拡張表記と配列表記との比較については配列表記#チェーン表記との比較および回転矢印表記#他表記との比較を参照のこと。

BEAFの配列表記は多変数アッカーマン関数と同じくらいの増加速度を持ち、BEAFそのものはさらに大きい増加速度を持つ。

10. 出典
------

11. 参考文献
--------

[1]
[2]

12. 関連項目
--------

巨大数
クヌースの矢印表記
配列表記