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

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

定義

タワー表記の拡張による。まず、3つ組の場合を定義する。0でない自然数 a, b, c について

<math>a \rightarrow \ b \rightarrow \ c = a \uparrow^{c} b = a \underbrace{\uparrow \cdots \uparrow}_{c} b</math>

次に、2つ組の場合を定義する。2つ組の場合は次のように単純な累乗と定めるものとする。

<math>a \rightarrow b = a \uparrow b = a^b</math>

4つ以上の0でない自然数を連ねて書いたときは、以下の規則によって変形できるものとする。

1. チェーンの数の最後及び最後から2番目が共に 1 でない場合
   • タワー表記における定義をコンウェイのチェーン表記で表すと次のようになる
     • a→b→n = a→(a→(b-1)→n)→(n-1)
   • よって、4つ以上の場合もこれに習って以下のように、最後の数は変えずに最後から2番目の数を 1 だけ減らしたチェーンと、最後の数を 1 だけ減らしたチェーンで表すものとする
     • a→b→...→x→y→z = a→b→...→x→(a→b→...→x→(y-1)→z)→(z-1)
2. チェーンの数の最後が 1 の場合
   • タワー表記における定義をコンウェイのチェーン表記で表すと次のようになる
     • a→b→1 = a→b
   • よって、4つ以上の場合もこれに習って以下のように最後の 1 を消去できるものとする
     • a→b→...→x→y→1 = a→b→...→x→y
3. チェーンの数の最後から2番目が 1 の場合
   • タワー表記における定義によると、 a→1→n は次のようにnの値に関係なく a となる

<math> a \rightarrow 1 \rightarrow n = a\uparrow^n 1 = a\uparrow^{n-1} (a\uparrow^n 0) = = a\uparrow^{n-1} 1 = ... = a\uparrow 1 = a \rightarrow 1 = a </math>

1. • よって、4つ以上の場合もこれに習って以下のように最後の数をその値に関係なく消去でき、さらには最後の数が消去されたことにより規則2により最後から2番目の 1 も消去できるものとする
     • a→b→...→x→1→z = a→b→...→x→1 = a→b→...→x

なお、これらの変形は、長さ3のチェーンのタワー表記における定義に基づいて長さ4以上のチェーンについて定義したものであるため、長さ2のチェーンでは規則1の変形は不可能であり、規則3の変形も最後から2番目の 1 を消去することはできない

規則2の変形は長さ2のチェーンでも可能である。また、規則3に該当する場合、変形するまでもなく 1 である。

性質

性質1

どんなチェーンも必ず一つの自然数に定まる。

Z を長さ N のチェーンとし、Z = a→b→...→x→y→z とする。 N ≦ 3 のとき一つの自然数に定まるのは明らかなので以下 N ≧ 4 のときのみ考える。

Z に規則1を適用すると、Z は全体のチェーン Z₁ = a→b→...→x→Y₁→(z-1) と、Z₁の最後から2番目の数となるチェーン Y₁ = a→b→...→x→(y-1)→z との2つのチェーンを含む形になる。

後者のチェーン Y₁ にさらに規則1を適用すると、同様に Z₂ = a→b→...→x→Y₂→(z-1) と Y₂ = a→b→...→x→(y-2)→z を含む形となる。したがって Z は Z₁, Z₂, Y₂ の3つのチェーンを含む形に変形できたことになる。

同様の手順をy-1回繰り返せば、 Z は Z₁...Z_y-1 および Y_y-1 = a→b→...→x→(y-(y-1))→z を含む形に変形できる。ここで Y_y-1 = a→b→...→x→1→z であり、規則3によって長さを1つ縮めることが出来る(さらにもう1つ縮めることも出来るが、ここではあえて1つしか縮めないものとする)。また、Z₁...Z_y-1 はそれぞれチェーンの最後の数が z-1 となっている。これにより Z は長さ N-1 のチェーンと、長さ N で最後の数が z-1 のチェーンのみを含む形に変形できる。

同様にして今度は長さ N で最後の数が z-1 のチェーンは長さ N-1 のチェーンと、長さ N で最後の数が z-2 のチェーンのみを含む形に変形できるため、 Z も長さ N-1 のチェーンと、長さ N で最後の数が z-2 のチェーンのみを含む形に変形できる。同じように繰り返していくと、最終的には Z は長さ N-1 のチェーンと、長さ N で最後の数が 1 のチェーンのみを含む形に変形できるが、長さ N で最後の数が 1 のチェーンは規則2によって長さを1つ縮めて長さ N-1 にできるため、結局 Z は長さ N-1 のチェーンのみを含む形に変形できる。

さらに同様にして今度は長さ N-1 のチェーンは長さ N-2 のチェーンのみを含む形に変形できるため、 Z も長さ N-2 のチェーンのみを含む形に変形できる。同じように繰り返していくと、最終的には Z は長さ 3 のチェーンのみを含む形に変形できるため、 Z は必ず一つの自然数に定まる。

性質2

どんな長さが 2 以上のチェーンも、最後の2つの数以外は変形しないで長さを1つ縮める事が出来る。

長さが 2 の場合もしくは最後もしくは最後から2番目の数が1の場合は明らかなので、以下長さが 3 以上かつ最後及び最後から2番目の数が共に1でない場合のみ考える。

先の Z₁ にさらに規則1を適用すれば、a→b→...→x→(a→b→...→x→(Y₁-1)→z)→(z-2) となる。さらに繰り返し適用することで最後の数を減らし、a→b→...→x→(...)→1 という形に出来る。(...) の中は長さ N のチェーンも含む非常に複雑なチェーンの組み合わせとなるが、性質1により結局はある自然数値に決まることが保証される。すなわち a→b→...→x→y→z というチェーンは a→b→...→x→Y という形に変形して、長さを1つ減らすことが出来る。

性質3

チェーンの途中に 1 があれば、その後ろのチェーンは全て消去できる。特に先頭から2番目が 1 のチェーンは先頭の値になり、先頭が 1 のチェーンは全て値が 1 である。

a→b→...→x→1→y→...→z の形は、性質2を繰り返し用いることで a→b→...→x→1→Y の形に変形できるので、規則3により a→b→...→x→1 と変形できる。

先頭から2番目が 1 のチェーンは、M→1→N の形まで変形すればタワー表記の定義より M であることは明らかである。

先頭が 1 のチェーンは、1→N の形まで変形すればタワー表記の定義より 1 であることは明らかである。

性質4

先頭と先頭から2番目が共に 2 のチェーンは全て値が 4 である。

性質2より、先頭と先頭から2番目が共に2のチェーンは一般に 2→2→N (Nは任意の0でない自然数) の形に変形できるので、

2→2→N

= 2→(2→1→N)→(N-1)

= 2→2→(N-1)

= …

= 2→2→1

= 2→2

= 2↑2

= 2²

= 2×2

= 2+2

= 4

例

• 3→3→3

= 3↑↑↑3

= 3↑↑3↑↑3

= 3↑↑(3↑3↑3)

= 3↑↑ 7625597484987

<math>= \underbrace{3^{3^{.^{.^{.3}}}}}_{7625597484987}</math>

• 3→3→3→3

= 3→3→(3→3→2→3)→2

= 3→3→(3→3→(3→3→1→3)→2)→2

= 3→3→(3→3→(3→3→1)→2)→2

= 3→3→(3→3→(3³)→2)→2

= 3→3→(3→3→27→2)→2

= 3→3→(3→3→(3→3→26→2)→1)→2

= 3→3→(3→3→(3→3→(3→3→25→2)→1))→2

<math>= \cdots =

\left. \begin{matrix} 3\underbrace{\uparrow\cdots\uparrow}_{3\underbrace{{}_{\uparrow\cdots\uparrow}}_{\underbrace{\vdots}_{{}_3 \underbrace{{}_{{}_{\uparrow\cdots\uparrow}}}_{3^3}{}_3}}3}3 \end{matrix} \right \} 3\rightarrow 3 \rightarrow 3^3 \rightarrow 2 =\left. \begin{matrix} 3\underbrace{\uparrow\cdots\uparrow}_{3\underbrace{{}_{\uparrow\cdots\uparrow}}_{\underbrace{\vdots}_{{}_3 \underbrace{{}_{{}_{\uparrow\cdots\uparrow}}}_{3^3}{}_3}}3}3 \end{matrix} \right \} \left. \begin{smallmatrix} 3\underbrace{\uparrow\cdots\uparrow}_{3\underbrace{{}_{\uparrow\cdots\uparrow}}_{\underbrace{\vdots}_{{}_3 \underbrace{{}_{{}_{\uparrow\cdots\uparrow}}}_{3^3}{}_3}}3}3 \end{smallmatrix} \right \} 3^3 </math>

その他

チェーン表記は、タワー表記では扱いにくかったとても巨大な数を表記するのに適しており、グラハム数を例にすると、不等式

<math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G^{64}(4) < 3\rightarrow 3\rightarrow 65\rightarrow 2 </math>

が成り立つ。これはG⁶⁴(1) < G⁶⁴(4) < G⁶⁵(1) の意味である。 また上記の3→3→3→3はグラハム数よりも遥かに巨大な数であり、さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。 タワー表記やチェーン表記の拡張版として回転矢印表記というものもあり矢印の回転を繰り返すことにより恐ろしく巨大な数を表記可能となる。

参考文献

• http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm（英語）
• http://home.earthlink.net/~mrob/pub/math/largenum-4.html（英語）