康威鏈式箭號表示法

**康威鏈式箭號表示法**是由約翰・何頓・康威發明的，用來表示大數。形式上看起來會像這樣：2→3→4→5→6。

## 定義

康威鏈式箭號表示法的長度定義如下：

* 任何一個正整數是長度為 1 的康威鏈。
* 假若有一個長度是 n 的康威鏈，後面加上→和一個正整數，此時形成的鏈長度為 n+1。

如果兩個康威鏈代表相同的整數，那麼就說它們是等價的。
下面四個規則說明如何用康威鏈表示整數，其中 $p$ 和 $q$ 是正整數， $X$ 是一個較短的康威鏈：

1. 康威鏈 $p$ 表示正整數 $p$ 。
2. $p\to q$ 代表指數 $p^{q}$ 。
3. $X\to p\to 1$ 等價於 $X\to p$ 。
4. $X\to p\to (q+1)$ 等價於 $X\to (X\to (\cdots (X\to (X)\to q)\cdots )\to q)\to q$ 
（在這裡， $X$ 出現 $p$ 次， $q$ 出現 $p-1$ 次，括號數量為 $p-1$ ）。

第四條規則可以以遞迴關係式列出，避免省略號的出現：

　
: 4a. $X\to 1\to (q+1)=X$

　
: 4b. $X\to (p+1)\to (q+1)=X\to (X\to p\to (q+1))\to q$

上面的四條規則可用來定義所有的康威鏈。例如長度為 3 的康威鏈，利用第四條規則，基本上長度仍然一樣，但 $p$ 和 $q$ 會是遞減的，當遞減到 1 時，就可以利用第三條規則來使長度縮短，使得它可利用第二條規則來計算出來。

## 性質

1. 長度為 3 的康威鏈對應 hyper 運算符和高德納箭號表示法： 
 ${\begin{matrix}p\to q\to r={\text{hyper}}(p,r+2,q)=p\!\!\!&\underbrace {\uparrow \dots \uparrow } &\!\!\!q=p\uparrow ^{r}q.\\&\!\!\!r{\text{ arrows}}\!\!\!\end{matrix}}$
2. X→Y 形式上如同 X→p（設 Y 是一個較短的康威鏈，如同 X 一樣），因此：
3. 一個康威鏈的開頭是冪。
4. 1→Y 等價於 1。
5. X→1→Y 等價於 X。
6. 2→2→Y 等價於 4。
7. X→2→2 等價於 X→(X)，其中後面的 X 是先被算出來的整數，如 a→b→2→2 = a→b→(a→b) = a→b→ab。

康威鏈不能被拆分，其箭號並不是二元運算符。其他二元運算符具有交換律及結合律，如 2 + 3 = 3 + 2，2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2)，或者是按照規定的順序，如 234 這類指數是從右至左計算，先計算 34 = 81，再計算 281。康威鏈並不符合上述性質。例如：

 * $2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=16$
* $2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^{3^{2}}=512$
* $\left(2\rightarrow 3\right)\rightarrow 2=\left(2^{3}\right)^{2}=64$

第一個式子並不等於下面任何式子。

## 例子

例子很快會變得非常複雜，先從簡單的開始（其中有些例子也會應用高德納箭號表示法）：

n

　
: = n （規則 1）

p→q

　
: = pq （規則 2）

　
: 例如 3→4 = 34 = 81

1→（任何康威鏈）

　
: = 1，因為任何康威鏈最終可以被簡化成一個數字，而 1 的任何次方都是 1。 （事實上，任何含有 1 的康威鏈，在 1 後面的那些數字和箭號都可直接消去，一個例子如 X→1→Y = X。）

4→3→2

　
: = 4→(4→(4)→1)→1（規則 4），從內向外展開。

　
: = 4→(4→4→1)→1（去掉多餘的括號）

　
: = 4→(4→4)→1（規則 3）

　
: = 4→(44)→1（規則 2）

　
: = 4→(256)→1（計算指數）

　
: = 4→256→1（去括號）

　
: = 4→256（規則 3）

　
: = 4256（規則 2）

利用高德納箭號表示法可以很容易解決： $4\uparrow ^{2}3=4\uparrow \uparrow 3=4\uparrow 4\uparrow 4=4\uparrow 4^{4}=4\uparrow 256=4^{256}$

2→2→4

　
: = 2→(2)→3（規則 4）

　
: = 2→2→3（去括號）

　
: = 2→2→2（規則 4，去括號）

　
: = 2→2→1（規則 4，去括號）

　
: = 2→2（規則 3）

　
: = 4（規則 2）（事實上，任何以 2→2 為開頭的康威鏈其值均為 4，本例是一個例子，應用性質 6）

高德納箭號表示法： $2\uparrow ^{4}2=2\uparrow \uparrow \uparrow \uparrow 2=2\uparrow \uparrow \uparrow 2=2\uparrow \uparrow 2=2\uparrow 2=2^{2}=4$

2→4→3

　
: = 2→(2→(2→(2)→2)→2)→2（規則 4）

　
: = 2→(2→(2→2→2)→2)→2（去括號）

　
: = 2→(2→(4)→2)→2（性質 6）

　
: = 2→(2→4→2)→2（去括號）

　
: = 2→(2→(2→(2→(2)→1)→1)→1)→2（規則 4）

　
: = 2→(2→(2→(2→2→1)→1)→1)→2（去括號）

　
: = 2→(2→(2→(2→2)))→2（規則 3）

　
: = 2→(2→(2→(4)))→2（規則 2）

　
: = 2→(2→(16))→2（規則 2）

　
: = 2→65536→2（規則 2）

　
: = 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1（規則 4），其中括號出現 65535 次

　
: = 2→(2→(2→(...2→(2→(2))...)))（規則 3）

　
: = 2→(2→(2→(...2→(4)...)))（規則 2）

　
: = 2→(2→(2→(...16...)))（規則 2）

　
: = $2^{2^{\dots ^{2}}}$ （其中 2 出現 216 = 65536 次） = 655362（見迭代冪次）

若用高德納箭號表示法可得 $2\uparrow ^{3}4=2\uparrow \uparrow \uparrow 4=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow 2=2\uparrow \uparrow 2\uparrow \uparrow 4=2\uparrow \uparrow 2\uparrow 2\uparrow 2\uparrow 2=2\uparrow \uparrow 65536$

2→3→2→2

　
: = 2→3→(2→3)→1（規則 4）

　
: = 2→3→8（規則 2 和規則 3）（利用高德納箭號表示法即為 $2\uparrow ^{8}3$ ）

　
: = 2→(2→2→7)→7（規則 4）

　
: = 2→4→7（性質 6，利用高德納箭號表示法即為 $2\uparrow ^{7}4$ ）

　
: = 2→(2→(2→2→6)→6)→6（規則 4）

　
: = 2→(2→4→6)→6（性質 6）

　
: = 2→(2→(2→(2→2→5)→5)→5)→6（規則 4）

　
: = 2→(2→(2→4→5)→5)→6（性質 6）

　
: = 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6（規則 4）

　
: = 2→(2→(2→(2→4→4)→4)→5)→6（性質 6）

　
: = 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4)→5)→6（規則 4）

　
: = 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6（性質 6）

　
: = 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6（利用前面的例子）

　
: = 大到無法想像的數

高德納箭號表示法： $2\uparrow ^{6}2\uparrow ^{5}2\uparrow ^{4}2\uparrow ^{3}2\uparrow ^{2}65536$

3→2→2→2

　
: = 3→2→(3→2)→1（規則 4）

　
: = 3→2→9（規則 2 和規則 3）

　
: = 3→3→8（規則 4）

高德納箭號表示法： $3\uparrow ^{8}3$

3→2→3→3

　
: = 3→2→(3→2→(3→2)→2)→2（規則 4）

　
: = 3→2→(3→2→9→2)→2（規則 2）

　
: = 3→2→(3→2→(3→2→(...3→2→(3→2)→1...)→1)→1)→2（規則 4），其中 3→2 出現 10 次，也就是原本的 1 個，加上括號裡的 9 個。

　
: = 3→2→(3→2→(3→2→(...3→2→(3→2)...)))→2（規則 3），3→2 出現 10 次。

　
: = 3→2→(3→2→(3→2→(...3→2→9...)))→2（規則 2），3→2 出現 9 次。

　
: = 3→2→(3→2→(3→2→(...3→3→8...)))→2（規則 4），3→2 出現 8 次。

　
: = 3→2→(3→2→(3→2→(... $3\uparrow ^{8}3$ ...)))→2（高德納箭號表示法），3→2 出現 8 次。

　
: = 3→2→(3→2→(3→2→(...3→2→( $3\uparrow ^{8}3$ )...)))→2

　
: = 3→2→(3→2→(3→2→(... $3\uparrow ^{3\uparrow ^{8}3}3$ ...)))→2（高德納箭號表示法），3→2 出現 7 次。

　
: = ...

　
: = 3→2→ ${\begin{matrix}\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{8}3...}3}3} \\8{\text{ arrows}}\end{matrix}}$ →2（高德納箭號表示法）

　
: = 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1（規則 4），其中 3→2 出現 ${\begin{matrix}\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{8}3...}3}3} \\8{\text{ arrows}}\end{matrix}}$ 次。

　
: = 3→2→(3→2→(...3→2→(3→2)))（規則 3），其中 3→2 出現 ${\begin{matrix}\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{8}3...}3}3} \\8{\text{ arrows}}\end{matrix}}$ 次。

　
: = ${3\uparrow ^{3\uparrow ^{...3\uparrow ^{3\uparrow 2}3...}3}3}$ ，其中向上箭號出現 ${\begin{matrix}\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{8}3...}3}3} \\8{\text{ arrows}}\end{matrix}}$ 次。

　
: = ${\begin{matrix}\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{3\uparrow 2}3...}3}3} _{\underbrace {3\uparrow ^{3\uparrow ^{...3\uparrow ^{8}3...}3}3{\text{ arrows}}} }\\8{\text{ arrows}}\end{matrix}}$

可見得 3→2→3→3 為使用高德納箭號表示法都難以表示的數，這個例子可證明，使用康威鏈式箭號表示法表示大數的效率會比高德納箭號表示法高很多（葛立恆數則是另一個例子）。

### 一般性的例子

簡單的例子：

 * $a\to b\to 2\to 2=a\to b\to (a\to b)\to 1=a\to b\to a^{b}=a\uparrow ^{a^{b}}b$

　
: 最後利用了性質 1。

 * $a\to b\to 3\to 2=a\to b\to (a\to b\to (a\to b)\to 1)\to 1$ 
 $=a\to b\to (a\to b\to a^{b})=a\to b\to (a\to b\to 2\to 2)=a\uparrow ^{a\to b\to 2\to 2}b$

　
: 最後利用了 $a\to b\to 2\to 2$ 。

 * $a\to b\to 4\to 2=a\to b\to (a\to b\to (a\to b\to a^{b}))=a\uparrow ^{a\to b\to 3\to 2}b$

　
: 最後利用了 $a\to b\to 3\to 2$ 。

對於任何康威鏈 X，設 $f(p)=X\to p$ ，則 $X\to p\to 2=f^{p}(1)$ （見複合函數）。

設 $X=a\to b$ ，則 $f(p)=a\uparrow ^{p}b$ ，所以 $a\to b\to p\to 2=f^{p}(1)=a\uparrow ^{a\to b\to (p-1)\to 2}b$ 。

例如 $10\to 10\to 3\to 2=10\uparrow ^{10\uparrow ^{10^{10}}10}10\!$ 。

進而：

 * $a\to b\to 2\to 3=a\to b\to 2\to (2+1)=a\to b\to (a\to b)\to 2=a\to b\to a^{b}\to 2=f^{a^{b}}(1)$

我們可以進一步一般化。假設 $g_{q}(p)=X\to p\to q$ ，則 $X\to p\to q+1=g_{q}^{p}(1)$ ，就是說 $g_{q+1}(p)=g_{q}^{p}(1)$ 。

根據上面可知， $g_{2}(p)=a\to b\to p\to 2=f^{p}(1)$ 以及 $g_{3}(p)=g_{2}^{p}(1)$ ，所以 $a\to b\to 2\to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^{a^{b}}(1)$ 。

## 阿克曼函數

阿克曼函數可以使用康威鏈式箭號表示法來表示：

　
: _A_(_m_, _n_) = (2 → (_n_ + 3) → _(m_ − 2)) − 3 for _m_ > 2

相反的

　
: 2 → _n_ → _m_ = _A_(_m_ + 2,_n_ − 3) + 3 for _n_ > 2

（n=1 和 n=2 有特別的規定，A (m, -2) = -1 以及 A (m, -1) = 1。）

## 葛立恆數

葛立恆數 $G\!$ 無法用康威鏈式箭號表示法來簡單的表示，但是可以訂出簡潔的上下界。設 $f(n)=3\rightarrow 3\rightarrow n\!$ ，則 $G=f^{64}(4)\,$ （見複合函數），可以得到 $3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2\,$ 。

**證明：**這裡會使用到規則 3 和規則 4：

$$
f^{64}(1)\,
$$

　
: $=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))\,$ （這裡有 64 個 $3\rightarrow 3$ ）

　
: $=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1\,$

　
: $=3\rightarrow 3\rightarrow 64\rightarrow 2;\,$

$$
f^{64}(4)=G;\,
$$

　
: $=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))\,$ （這裡有 64 個 $3\rightarrow 3$ ）

$$
f^{64}(27)\,
$$

　
: $=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))\,$ （這裡有 64 個 $3\rightarrow 3$ ）

　
: $=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))\,$ （這裡有 65 個 $3\rightarrow 3$ ）

　
: $=3\rightarrow 3\rightarrow 65\rightarrow 2\,$

由於 $f(n)$ 是嚴格遞增函數，

　
: $f^{64}(1)<f^{64}(4)<f^{64}(27)\,$

這給出了上下界。

利用康威鏈式箭號表示法，很容易表示遠遠大於葛立恆數的數：

　
: $3\rightarrow 3\rightarrow 3\rightarrow 3~~=~~3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 2)\rightarrow 2\,~~=~~3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,$

其中 $3\rightarrow 3\rightarrow 27\rightarrow 2$ 遠遠大於 $65$ ，因此 $3\rightarrow 3\rightarrow 3\rightarrow 3$ 遠遠大於葛立恆數。

## 參見

* hyper 運算符
* 高德納箭號表示法
* 阿克曼函數

## 參考資料

## 外部連結

* Factoids > big numbers （頁面存檔備份，存於網際網路檔案館）（英文）
* Robert Munafo's Large Numbers （頁面存檔備份，存於網際網路檔案館）（英文）
* The Book of Numbers by J. H. Conway and R. K. Guy （頁面存檔備份，存於網際網路檔案館）（英文）