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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

クヌースの矢印表記アッカーマン関数などより比較的強い演算である。

導入[編集]

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

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

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

(とも書き換えられる)

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

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

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

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

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

定義[編集]

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

  • 任意の正の整数は、長さ 1 のチェーンである。
  • 長さ n のチェーンに、右向き矢印 と正の整数を繋げたものは、長さ n + 1 のチェーンとなる。

さらに p, q を正の整数、X を部分チェーンとするとき、チェーンについて以下が成り立つ。

  • 長さ 0 のチェーン(空チェーン)は、1 に等しい。
  • 長さ 1 のチェーン p は、p に等しい。
  • 長さ 2 のチェーン pq は、pq に等しい。
  • 長さ 3 のチェーン pq → 0pq に、p → 0 → 21 に各各等しい。
  • X → 1X に等しい。即ちチェーン右端の → 1 は取り除くことができる。
  • X → 1 → pX に等しい。即ちチェーン右端の → 1 → p は取り除くことができる。
  • X → (p + 1) → (q + 1) に等しい。

ここで関数 ff(x) = X → (x) → q とおくと、最後の二つの条件は次のようにも述べられる。但し fpfp反復合成である。

別の定義[編集]

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

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

チェーン表記(a~zは正の整数)を以下のように定義する。

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

性質[編集]

以下、項(正の整数)を小文字 a, b, ... 、チェーン(および部分チェーン)を大文字 A, B, ... で表す。

  • 長さ 3 のチェーンは、ハイパー演算子およびクヌースの矢印表記による表示をもつ。
  • 任意のチェーンに対し常にただ一つの整数が定まる。
  • 長さ n のチェーン Xpq は適当な r によって Xr と変形できる。即ち先頭から n − 2 項を保ったまま長さを 1 短くできる。
  • a から始まるチェーン aXa の冪 at となる。
  • 1 から始まるチェーン 1 → X1 に等しい。
  • 1 より後の項はすべて無視することができる。
  • 先頭に 2 が連なったチェーン 2 → 2 → X4 に等しい。
  • 末尾に 2 が連なったチェーン X → 2 → 2X → (X) に等しい。
  • p-qp → (q → (-1) → 0) → (-1) に等しい。
  • p/qp → (q → (-1) → 1) → 0 に等しい。
  • p → (q → (-1) → 2) → 1 = pq → (-1) → 2plogq(logq(q → (+1) → 2)) = plogq(logq(q)) = plogq(1) = p0 = 1 に等しい。

[編集]

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

  • 2 → 3 → 3
= 2 → (2 → 2 → 3) → 2
= 2 → (2 → (2 → 1 → 3) → 2) → 2
= 2 → (2 → 2 → 2) → 2
= 2 → (2 → (2 → 1 → 2) → 1) → 2
= 2 → (2 → 2) → 2
= 2 → 4 → 2
= 2 → (2 → (2 → (2 → 1 → 2) → 1) → 1) → 1
= 2 → (2 → (2 → 2))
= 2222
= 216
= 65536
  • 3 → 2 → 3
= 3 → (3 → 1 → 3) → 2
= 3 → 3 → 2
= 3 → (3 → 2 → 2) → 1
= 3 → (3 → (3 → 1 → 2) → 1) → 1
= 3 → (3 → 3)
= 333
= 327
= 7625597484987
  • 4 → 3 → 2
= 4 → (4 → (4 → 1 → 2) → 1) → 1
= 4 → (4 → 4)
= 444
= 4256
= 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

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

アッカーマン関数[編集]

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

m > 2の際 A(m, n) = (2 → (n + 3) → (m − 2)) − 3 (ハイパー演算の角括弧表記を用いると A(m, n) = 2 [m] (n + 3) - 3)

よって

n > 2の際 2 → nm = A(m + 2,n − 3) + 3

(n = 1 と n = 2 は A(m, −2) = −1 と A(m, −1) = 1に対応し、論理的に加算できる。)

ちなみに多変数アッカーマン関数でくらいである。

グラハム数[編集]

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

証明: 定義の"反復合成を用いた規則"を適用させると、次の様になる。:

(64組の "")


(64組の "")

(64組の "")
(65組の "")
(上記のように計算する)

g単調増加なので、

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

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

CG関数[編集]

コンウェイとリチャード・K・ガイ英語版に共同制作された単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:

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

cg(1) = 1

cg(2) = 2 → 2 = 22 = 4

cg(3) = 3 → 3 → 3 = 3↑↑↑3 = 3↑↑(3↑↑3)= 3↑↑7625597484987

cg(4) = 4 → 4 → 4 → 4 = 4 → 4 →(4 → 4 →(4 → 4 →(4 → 4)→ 3)→ 3)→ 3 = 4 → 4 →(4 →4 →(4 →4 → 256 →3) →3 ) →3

cg(5) = 5 → 5 → 5 → 5 → 5 = 5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5)→ 4)→ 4)→ 4)→ 4 = 5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 2 → 6)→ 4)→ 4)→ 4)→ 4

cg(6) = 6 → 6 → 6 → 6 → 6 → 6 = 6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6) → 5) → 5) → 5) → 5) → 5

……………

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

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

拡張チェーン系の表記[編集]

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

ピーター・ハーフォードによる拡張[編集]

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

(あくまで本、という意味)

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

定義[編集]

この表記は拡張チェーン表記と呼ばれ、同じ拡張チェーン系の回転矢印表記と同じくらいの強さである。歴史的には、回転矢印表記が先にできて、後にこのハーフォードの拡張チェーン表記ができた。

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

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

彼は上記以外の規則は変更しなかった。(ひとつのチェーンにおいては1種類の矢印のみを使用できた。つまりb≠dの際は規則違反になる)

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

とすると、は規則違反では無くなる上に表記法が更に強くなる(あまり意味はない。つまり、本質的に大きくする手段は別にある。)。[2]

クリス・バードによる拡張(回転矢印表記)[編集]

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

その他[編集]

チェーン表記(およびその拡張表記)では、数の大きさを評価するための重要度は次の通りである:

(拡張チェーン系の表記におけるチェーンの拡張レベル>)チェーンの長さ>末尾の変数>末尾から2番目の変数>それ以外の変数

チェーン表記(およびその拡張表記)では、どの変数の値が増えても厳密には数は増えるものの、特に5つ組以上のチェーンでは、末尾の2つ以外の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。

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

チェーン表記とは異なった規則により、チェーン表記よりも効率的に数の大きさを爆発させることができる表記として、配列表記があり、それにも拡張表記が考案されており、その最終形態はBEAFと呼ばれるものである。チェーン表記で表される数は配列表記では4変数程度、ピーター・ハーフォードの拡張チェーン表記(あるいはクリス・バードの回転矢印表記)で表される数は配列表記では5変数程度のレベルとなる。

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

脚注[編集]

[脚注の使い方]
  1. ^ a b John H. Conway & Richard K. Guy, The Book of Numbers, 1996, p.59-62
  2. ^ “Large Numbers, Part 2: Graham and Conway - Greatplay.net”. archive.is. (2013年6月25日). https://archive.is/rEzX6 2018年2月18日閲覧。 

参考文献[編集]