利用者:Flightbridge/sandbox/コンウェイのチェーン表記

コンウェイのチェーン表記とは、1995年にジョン・ホートン・コンウェイとリチャード・ケネス・ガイによって導入^[1]^[2]された巨大数の表記法である。

導入

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

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

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

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

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

このチェーンによって式 (3) を書き換えると次のような式になる。これは末尾 $\to c$ のチェーンを末尾 $\to (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}

さらにコンウェイはチェーン末尾の $\to 1$ は無視されるとした^[2]。従って式 (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$ のチェーンに、右向き矢印 $\to$ と正の整数を繋げたものは、長さ $n + 1$ のチェーンとなる。

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

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

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

{\begin{aligned}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{aligned}}

性質

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

長さ 3 のチェーンは、ハイパー演算子およびクヌースの矢印表記による表示をもつ。
- $p\rightarrow q\rightarrow r=H_{r+2}(p,\,q)$
- $p\rightarrow q\rightarrow r=p\uparrow ^{r}q$
任意のチェーンに対し常にただ一つの整数が定まる。
長さ $n$ のチェーン $X \to p \to q$ は適当な $r$ によって $X \to r$ と変形できる。即ち先頭から $n - 2$ 項を保ったまま長さを $1$ 短くできる。
$a$ から始まるチェーン $a \to X$ は $a$ の冪 $a t$ となる。
$1$ から始まるチェーン $1 \to X$ は $1$ に等しい。
1 より後の項はすべて無視することができる。
- $X\rightarrow 1\rightarrow Y=X$
先頭に $2$ が連なったチェーン $2 \to 2 \to X$ は $4$ に等しい。
末尾に $2$ が連なったチェーン $X \to 2 \to 2$ は $X \to (X)$ に等しい。

例

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

$2 \to 3 \to 3$

= 2 \to (2 \to 2 \to 3) \to 2

= 2 \to (2 \to (2 \to 1 \to 3) \to 2) \to 2

= 2 \to (2 \to 2 \to 2) \to 2

= 2 \to (2 \to (2 \to 1 \to 2) \to 1) \to 2

= 2 \to (2 \to 2) \to 2

= 2 \to 4 \to 2

= 2 \to (2 \to (2 \to (2 \to 1 \to 2) \to 1) \to 1) \to 1

= 2 \to (2 \to (2 \to 2))

= 2 222

= 2 16

= 65 536

$3 \to 2 \to 3$

= 3 \to (3 \to 1 \to 3) \to 2

= 3 \to 3 \to 2

= 3 \to (3 \to 2 \to 2) \to 1

= 3 \to (3 \to (3 \to 1 \to 2) \to 1) \to 1

= 3 \to (3 \to 3)

= 3 33

= 3 27

= 7 625 597 484 987

$4 \to 3 \to 2$

= 4 \to (4 \to (4 \to 1 \to 2) \to 1) \to 1

= 4 \to (4 \to 4)

= 4 44

= 4 256

= 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 = G 64 (4)$ を例にすると、不等式

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

が成り立つ^[2]。これは $G 64 (1) < G 64 (4) < G 65 (1)$ の意味である。また $3 \to 3 \to 3 \to 3$ は

3\rightarrow 3\rightarrow 3\rightarrow 3=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2=G^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)=G^{G^{27}(1)}(1)

となり、グラハム数よりも遥かに巨大な数^[2]であり、さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。

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

脚注

^ John H. Conway; Richard K. Guy (1996). The Book of Numbers. pp. 59–62
^ ^a ^b ^c ^d ^e John H. Conway、Richard K. Guy 著、根上生也訳『数の本』2001年、71–73頁。

参考文献

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

{@{巨大数}}

{@{DEFAULTSORT:こんうえいのちええんひようき}} [@[Category:数学の表記法]] [@[Category:数学に関する記事]]

[book-of-numbers_original-1] John H. Conway; Richard K. Guy (1996). The Book of Numbers. pp. 59–62

[book-of-numbers_japanese-2] John H. Conway、Richard K. Guy 著、根上生也訳『数の本』2001年、71–73頁。

[1]

[2]