康威鏈式箭號表示法是由約翰·何頓·康威發明的，用來表示大數。形式上看起來會像這樣：2→3→4→5→6。
定義
康威鏈式箭號表示法的長度定義如下：
*任何一個正整數是長度為1的康威鏈。
*假若有一個長度是n的康威鏈，後面加上→和一個正整數，此時形成的鏈長度為n+1。
如果兩個康威鏈代表相同的整數，那麼就說它們是等價的。
下面四個規則說明如何用康威鏈表示整數，其中p和q是正整數，X是一個較短的康威鏈：
康威鏈p表示正整數p。
p \to q代表指數函數p^q。
X \to p \to 1等價於X \to p。
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 = X
:4b. X \to p \to q = X \to (X \to (p-1) \to q) \to (q-1)
上面的四條規則可用來定義所有的康威鏈。例如長度為3的康威鏈，利用第四條規則，基本上長度仍然一樣，但p和q會是遞減的，當遞減到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}
X→Y形式上如同X→p（設Y是一個較短的康威鏈，如同X一樣），因此：
一個康威鏈的開頭是冪。
1→Y等價於1。
X→1→Y等價於X。
2→2→Y等價於4。
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\rightarrow3\rightarrow2 = 2\uparrow\uparrow3 = 2^{2^2} = 16
- 2\rightarrow\left(3\rightarrow2\right) = 2^{(3^2)} = 2^{3^2} = 512
- \left(2\rightarrow3\right)\rightarrow2 = \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 。
證明：這裡會使用到規則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)
這給出了上下界。
利用康威鏈式箭號表示法，很容易表示遠遠大於葛立恆數的數：
: 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運算符
*高德納箭號表示法
*阿克曼函數
參考資料
外部連結
- [http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm Factoids > big numbers]
- [http://www.mrob.com/pub/math/largenum.html Robert Munafo's Large Numbers]
评论 (0)