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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

導入[編集]

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

\begin{array}{lclcl}
 (1)\qquad
 a \times b
 &=& \underbrace{ a + a + \cdots + a }_{b}
 &=& \underbrace{
  a +
  \cdots
  a \,+
 }_{b-1} ~a
\\
 (2)\qquad
 a \uparrow b
 &=& \underbrace{ a \times a \times \cdots \times a }_{b}
 &=& \underbrace{
  a \times
  \cdots
  a \,\times
 }_{b-1} ~a
\\
 (3)\qquad
 a \uparrow^c b
 &=& \underbrace{ a \uparrow^{c-1} a \uparrow^{c-1} \cdots \uparrow^{c-1} a }_{b}
 &=& \underbrace{
  a \uparrow^{c-1}
  \cdots
  a \uparrow^{c-1}
 }_{b-1} ~a
\end{array} \,\!

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

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

(4)\qquad a \rightarrow b \rightarrow c = a \underbrace{\uparrow \cdots \uparrow}_{c} b = a \uparrow^c b

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


 (5)\qquad
 a \rightarrow b \rightarrow c
 =
\underbrace{
 a \rightarrow \biggl( \cdots \rightarrow \Bigl(
  a \rightarrow (
}_{b-1}
   \quad a \quad
\underbrace{
  ) \rightarrow (c-1)
 \Bigr) \rightarrow \cdots \biggr) \rightarrow (c-1)
}_{b-1}

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


 (6)\qquad
 X \rightarrow b \rightarrow c
 =
\underbrace{
 X \rightarrow \biggl( \cdots \rightarrow \Bigl(
  X \rightarrow (
}_{b-1}
   \quad X \quad
\underbrace{
  ) \rightarrow (c-1)
 \Bigr) \rightarrow \cdots \biggr) \rightarrow (c-1)
}_{b-1}

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

(7)\qquad a_1 \rightarrow \cdots \rightarrow a_n \rightarrow 1 = a_1 \rightarrow \cdots \rightarrow a_n

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


 (8)\qquad
 a \rightarrow b
 = a \rightarrow b \rightarrow 1
 = a \uparrow b
 = a^b

定義[編集]

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

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

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

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

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

\begin{align}
 X \rightarrow (p + 1) \rightarrow (q + 1)
 &=
\underbrace{
 X \rightarrow \biggl( \cdots \rightarrow \Bigl(
  X \rightarrow (
}_{p}
   \quad X \quad
\underbrace{
  ) \rightarrow q
 \Bigr) \rightarrow \cdots \biggr) \rightarrow q
}_{p}
\\
 &= \underbrace{ f( \cdots f( }_{p} \quad X \quad \underbrace{ ) \cdots ) }_{p}
\\
 &= f^p(X)
\end{align}

性質[編集]

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

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

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

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

同様の手順をy-1回繰り返せば、 Z は Z1...Zy-1 および Yy-1 = a→b→...→x→(y-(y-1))→z を含む形に変形できる。ここで Yy-1 = a→b→...→x→1→z であり、規則3によって長さを1つ縮めることが出来る(さらにもう1つ縮めることも出来るが、ここではあえて1つしか縮めないものとする)。また、Z1...Zy-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でない場合のみ考える。

先の Z1 にさらに規則1を適用すれば、a→b→...→x→(a→b→...→x→(Y1-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 と変形できる。 具体例を挙げると、 37→15→27→8→5→13→1→29→14→3 →26 は 37→15→27→8→5→13→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
= 22 = 2×2 = 2+2
= 4

[編集]

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

  • 2 → 3 → 3
= 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
= 65 536
  • 3 → 2 → 3
= 3 → (3 → 1 → 3) → 2
= 3 → 3 → 2
= 3 → (3 → (3 → 1 → 2) → 1) → 1
= 3 → (3 → 3)
= 333
= 327
= 7 625 597 484 987
  • 4 → 3 → 2
= 4 → (4 → (4 → 1 → 2) → 1) → 1
= 4 → (4 → 4)
= 444
= 4256
= 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 096

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


 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 1
  &=&
  p \underbrace{\uparrow \cdots \uparrow}_{ r } q
 \end{matrix}

 \left.
 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 2
  &=&p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q \\
  & &{\scriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q }\\
  & &{\scriptstyle   \underbrace{\quad~ \vdots ~\quad}       }\\
  & &{\scriptstyle p \underbrace{\uparrow \cdots \uparrow} q }\\
  & &{\scriptstyle p^q }
 \end{matrix}
 \right \} {\scriptstyle r }

 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 3
  &=& \\
  & & \\
  & & \\
  & & \\
  & & \\
  & & \\
  & & \\
 \end{matrix}
 \underbrace{
  \left.
   \begin{matrix}
    p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q \\
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q }\\
    {\scriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptstyle   \underbrace{\quad~ \vdots ~\quad}       }\\
    {\scriptstyle p \underbrace{\uparrow \cdots \uparrow} q }\\
    {\scriptstyle p^q }
   \end{matrix}
  \right \}
  \left.
   \begin{matrix}
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q }\\
    {\scriptscriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q }\\
    {\scriptscriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptscriptstyle   \underbrace{\quad~ \vdots ~\quad}       }\\
    {\scriptscriptstyle p \underbrace{\uparrow \cdots \uparrow} q }\\
    {\scriptscriptstyle p^q }
   \end{matrix}
  \right \}
  \cdots
  \left\}
   \begin{matrix}
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q }\\
    {\scriptscriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q }\\
    {\scriptscriptstyle   \underbrace{\quad~ \vdots ~\quad}       }\\
    {\scriptscriptstyle p \underbrace{\uparrow \cdots \uparrow} q }\\
    {\scriptscriptstyle p^q }
   \end{matrix}
  \right \} {\scriptscriptstyle p^q }
 }_{r}

その他[編集]

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

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

が成り立つ。これはG64(1) < G64(4) < G65(1) の意味である。また上記の 3→3→3→3 はグラハム数よりも遥かに巨大な数であり、さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。

タワー表記やチェーン表記の拡張版として回転矢印表記というものもあり、その矢印の回転を繰り返すことにより恐ろしく巨大な数が表記可能となる。

脚注[編集]

  1. ^ a b John H. Conway & Richard K. Guy, The Book of Numbers, 1996, p.59-62

参考文献[編集]