查看“︁康威鏈式箭號表示法”︁的源代码

'''康威鏈式箭號表示法'''是由[[約翰·何頓·康威]]發明的，用來表示[[大數 (數學)|大數]]<ref>{{cite book |author=約翰·何頓·康威 |authorlink=約翰·何頓·康威 |title=On Numbers and Games（論數字與博弈） |year=2001 |publisher=A K PETERS Limited |isbn=1568811276 }}</ref>。形式上看起來會像這樣：2→3→4→5→6。

== 定義 ==
康威鏈式箭號表示法的長度定義如下：
*任何一個正整數是長度為1的康威鏈。
*假若有一個長度是n的康威鏈，後面加上→和一個正整數，此時形成的鏈長度為n+1。
如果兩個康威鏈代表相同的整數，那麼就說它們是等價的。
下面四個規則說明如何用康威鏈表示整數，其中<math>p</math>和<math>q</math>是正整數，<math>X</math>是一個較短的康威鏈：
# 康威鏈<math>p</math>表示正整數<math>p</math>。
# <math>p \to q</math>代表[[指數]]<math>p^q</math>。
# <math>X \to p \to 1</math>等價於<math>X \to p</math>。
# <math>X \to p \to (q + 1)</math>等價於<math>X \to ( X \to ( \cdots (X \to ( X ) \to q)\cdots ) \to q ) \to q</math> <br />（在這裡，<math>X</math>出現<math>p</math>次，<math>q</math>出現<math>p-1</math>次，括號數量為<math>p-1</math>）。
第四條規則可以以[[遞迴關係式]]列出，避免[[省略號]]的出現：
:4a. <math>X \to 1 \to (q + 1) = X</math>
:4b. <math>X \to (p + 1) \to (q + 1) = X \to (X \to p \to (q+1)) \to q</math>
上面的四條規則可用來定義所有的康威鏈。例如長度為3的康威鏈，利用第四條規則，基本上長度仍然一樣，但<math>p</math>和<math>q</math>會是遞減的，當遞減到1時，就可以利用第三條規則來使長度縮短，使得它可利用第二條規則來計算出來。

== 性質 ==
# 長度為3的康威鏈對應[[hyper運算符]]和[[高德納箭號表示法]]：<br><math>\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}</math>
# 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→a<sup>b</sup>。

康威鏈不能被拆分，其箭號並不是[[二元運算符]]。其他二元運算符具有[[交換律]]及[[結合律]]，如2 + 3 = 3 + 2，2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2)，或者是按照規定的順序，如2<sup>3<sup>4</sup></sup>這類指數是從右至左計算，先計算3<sup>4</sup> = 81，再計算2<sup>81</sup>。康威鏈並不符合上述性質。例如：
* <math>2\rightarrow3\rightarrow2 = 2\uparrow\uparrow3 = 2^{2^2} = 16</math>
* <math>2\rightarrow\left(3\rightarrow2\right) = 2^{(3^2)} = 2^{3^2} = 512</math>
* <math>\left(2\rightarrow3\right)\rightarrow2 = \left(2^3\right)^2 = 64</math>
第一個式子並不等於下面任何式子。

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

n
:= n  （規則1）

p→q
:= p<sup>q</sup> （規則2）
:例如 3→4 = 3<sup>4</sup> = 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→(4<sup>4</sup>)→1（規則2）
:= 4→(256)→1（計算指數）
:= 4→256→1（去括號）
:= 4→256（規則3）
:= 4<sup>256</sup>（規則2）

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

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）

高德納箭號表示法：<math>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</math>

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）
:= <math>2^{2^{\dots^2}}</math>（其中2出現2<sup>16</sup> = 65536次） = <sup>65536</sup>2（見[[迭代冪次]]）
若用高德納箭號表示法可得<math>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</math>

2→3→2→2
:= 2→3→(2→3)→1（規則4）
:= 2→3→8（規則2和規則3）（利用高德納箭號表示法即為<math>2 \uparrow^8 3</math>）
:= 2→(2→2→7)→7（規則4）
:= 2→4→7（性質6，利用高德納箭號表示法即為<math>2 \uparrow^7 4</math>）
:= 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（利用前面的例子）
:= 大到無法想像的數
高德納箭號表示法：<math>2 \uparrow^6 2 \uparrow^5 2 \uparrow^4 2 \uparrow^3 2 \uparrow^2 65536</math>

3→2→2→2
:= 3→2→(3→2)→1（規則4）
:= 3→2→9（規則2和規則3）
:= 3→3→8（規則4）
高德納箭號表示法：<math>3 \uparrow^8 3</math>

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→(...<math>3 \uparrow^8 3</math>...)))→2（高德納箭號表示法），3→2出現8次。
:= 3→2→(3→2→(3→2→(...3→2→(<math>3 \uparrow^8 3</math>)...)))→2
:= 3→2→(3→2→(3→2→(...<math>3 \uparrow^{3 \uparrow^8 3} 3</math>...)))→2（高德納箭號表示法），3→2出現7次。
:= ...
:= 3→2→<math>\begin{matrix} \underbrace{ 3 \uparrow^{3 \uparrow^{... 3 \uparrow^8 3 ...}3} 3} \\ 8 \text{ arrows} \end{matrix}</math>→2（高德納箭號表示法）
:= 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1（規則4），其中3→2出現<math>\begin{matrix} \underbrace{ 3 \uparrow^{3 \uparrow^{... 3 \uparrow^8 3 ...}3} 3} \\ 8 \text{ arrows} \end{matrix}</math>次。
:= 3→2→(3→2→(...3→2→(3→2)))（規則3），其中3→2出現<math>\begin{matrix} \underbrace{ 3 \uparrow^{3 \uparrow^{... 3 \uparrow^8 3 ...}3} 3} \\ 8 \text{ arrows} \end{matrix}</math>次。
:= <math>{ 3 \uparrow^{3 \uparrow^{... 3 \uparrow^{3 \uparrow 2} 3 ...}3} 3}</math>，其中向上箭號出現<math>\begin{matrix} \underbrace{ 3 \uparrow^{3 \uparrow^{... 3 \uparrow^8 3 ...}3} 3}\\ 8 \text{ arrows} \end{matrix}</math>次。
:= <math>\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}</math>

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

=== 一般性的例子 ===
簡單的例子：
* <math>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</math>
: 最後利用了性質1。
* <math>a \to b \to 3 \to 2 = a \to b \to (a \to b \to (a \to b) \to 1) \to 1 </math><br /> <math> = 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</math>
: 最後利用了<math>a \to b \to 2 \to 2</math>。
* <math>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</math>
: 最後利用了<math>a \to b \to 3 \to 2</math>。
對於任何康威鏈X，設<math>f(p) = X \to p</math>，則<math>X \to p \to 2 = f^p(1)</math>（見[[複合函數]]）。

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

例如<math>10 \to 10 \to 3\to 2 = 10 \uparrow ^{10 \uparrow ^{10^{10}} 10} 10 \!</math>。

進而：
* <math>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)</math>

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

根據上面可知，
<math>g_2(p) = a \to b \to p \to 2 = f^p(1)</math>以及<math>g_3(p) = g_2^p(1)</math>，所以<math>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)</math>。

== 阿克曼函數 ==
[[阿克曼函數]]可以使用康威鏈式箭號表示法來表示：
:''A''(''m'', ''n'') = (2 → (''n'' + 3) → ''(m'' − 2)) − 3 for ''m'' > 2
相反的
:2 → ''n'' → ''m'' = ''A''(''m'' + 2,''n'' &minus; 3) + 3 for ''n'' > 2

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

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

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

<math>f^{64}(1)\, </math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1))\cdots ))\, </math> （這裡有64個 <math>3 \rightarrow 3</math>）
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3) \rightarrow 1) \cdots ) \rightarrow 1) \rightarrow 1\, </math>
:<math>= 3 \rightarrow 3 \rightarrow 64 \rightarrow 2;\, </math>

<math>f^{64}(4) = G;\, </math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 4))\cdots ))\, </math> （這裡有64個 <math>3 \rightarrow 3</math>）

<math>f^{64}(27)\, </math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27))\cdots ))\, </math> （這裡有64個 <math>3 \rightarrow 3</math>）
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3)))\cdots ))\, </math> （這裡有65個 <math>3 \rightarrow 3</math>）
:<math>= 3 \rightarrow 3 \rightarrow 65 \rightarrow 2\, </math>

由於<math>f(n)</math>是[[單調函數|嚴格遞增函數]]，
:<math>f^{64}(1) < f^{64}(4) < f^{64}(27)\, </math>

這給出了上下界。

利用康威鏈式箭號表示法，很容易表示遠遠大於葛立恆數的數：
:<math> 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\, </math>

其中<math>3 \rightarrow 3 \rightarrow 27 \rightarrow 2</math>遠遠大於<math>65</math>，因此<math>3 \rightarrow 3 \rightarrow 3 \rightarrow 3</math>遠遠大於葛立恆數。

== 參見 ==
*[[hyper運算符]]
*[[高德納箭號表示法]]
*[[阿克曼函數]]

==參考資料==
{{reflist}}

== 外部連結 ==
* [http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm Factoids &gt; big numbers] {{Wayback|url=http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm |date=20100807083733 }}{{en}}
* [http://www.mrob.com/pub/math/largenum.html Robert Munafo's Large Numbers] {{Wayback|url=http://www.mrob.com/pub/math/largenum.html |date=20170516055144 }}{{en}}
*[https://docs.google.com/viewer?a=v&q=cache:gv7MebfOp6oJ:futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/01-MA-Mathematics,%2520Economics%2520and%2520Preparation%2520for%2520University/011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography/Additional%2520Resources/J.H.%2520Conway,%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw The Book of Numbers by J. H. Conway and R. K. Guy] {{Wayback|url=https://docs.google.com/viewer?a=v&q=cache%3Agv7MebfOp6oJ%3Afuturetg.com%2FFTHumanEvolutionCourse%2FFTFreeLearningKits%2F01-MA-Mathematics%2C%2520Economics%2520and%2520Preparation%2520for%2520University%2F011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography%2FAdditional%2520Resources%2FJ.H.%2520Conway%2C%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw |date=20211122085221 }}{{en}}

{{大數}}

[[Category:數學表示法]]
[[Category:大數]]