康威鏈式箭號表示法

维基百科,自由的百科全书
跳转至: 导航搜索

康威鏈式箭號表示法,是由約翰·何頓·康威發明的,用來表示大數[1]。形式上看起來會像這樣:2→3→4→5→6。

定義[编辑]

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

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

如果兩個康威鏈代表相同的整數,那麼就說它們是等價的。 下面四個規則說明如何用康威鏈表示整數,其中pq是正整數,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的康威鏈,利用第四條規則,基本上長度仍然一樣,但pq會是遞減的,當遞減到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\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)

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→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次規則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))...)))(使用65535次規則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 ↑8 3)
= 2→(2→2→7)→7(規則4)
= 2→4→7(性質6,利用高德納箭號表示法即為2 ↑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

一般性的例子[编辑]

簡單的例子:

  • 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 → nm = 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遠遠大於葛立恆數。

參見[编辑]

參考資料[编辑]

  1. ^ 約翰·何頓·康威. On Numbers and Games(論數字與博弈). A K PETERS Limited. 2001. ISBN 1568811276. 

外部連結[编辑]