定義
康威鏈式箭號表示法的 長度定義如下:
•任何一個正整數是長度為1的康威鏈。
•假若有一個長度是n的康威鏈,後面加上→和一個正整數,此時形成的鏈長度為n+1。
如果兩個康威鏈代表相同的整數,那么就說它們是等價的。 下面四個規則說明如何用康威鍊表示整數,其中 和 是正整數, 是一個較短的康威鏈:
1、康威鏈 表示正整數 。
2、 代表指數 。
3、 等價於 。
4、 等價於 (在這裡, 出現 次, 出現 次,括弧數量為 對).
第四條規則可以以遞迴關係式列出,避免省略號的出現:
4a、
4b、
上面的四條規則可用來定義所有的康威鏈。例如長度為3的康威鏈,利用第四條規則,基本上長度仍然一樣,但 和 會是遞減的,當遞減到1時,就可以利用第三條規則來使 長度縮短,使得它可利用第二條規則來計算出來。
性質
1、長度為3的康威鏈對應hyper運算符和高德納箭號表示法:
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是先被算出來的整數,如 .
康威鏈不能被拆分,其箭號並不是二元運算符。其他二元運算符具有交換律及結合律,如2 + 3 = 3 + 2,2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2),或者是按照規定的順序,如 這類指數是從右至左計算,先計算 = 81,再計算 。康威鏈並不符合上述性質。例如:
第一個式子並不等於下面任何式子。
例子
例子很快會變得非常複雜,先從簡單的開始(其中有些例子也會套用高德納箭號表示法):
(1)n
= n(規則1)
(2)p→q
= (規則2)
例如:
(3)1→(任何康威鏈)
= 1,因為任何康威鏈最終可以被簡化成一個數字,而1的任何次方都是1。 (事實上,任何含有1的康威鏈,在1後面的那些數字和箭號都可直接消去,一個例子如X→1→Y = X。)
(4)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)
利用高德納箭號表示法可以很容易解決:
(5)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)
高德納箭號表示法:
(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)
= 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出現 次)(見疊代冪次)
=65536
若用高德納箭號表示法可得:
(7)2→3→2→2
= 2→3→(2→3)→1(規則4)
= 2→3→8(規則2和規則3)(利用高德納箭號表示法即為 )
= 2→(2→2→7)→7(規則4)
= 2→4→7(性質6,利用高德納箭號表示法即為 )
= 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(利用前面的例子)
= 大到無法想像的數
高德納箭號表示法:
(8)3→2→2→2
= 3→2→(3→2)→1(規則4)
= 3→2→9(規則2和規則3)
= 3→3→8(規則4)
高德納箭號表示法:
(9)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→(... ...)))→2(高德納箭號表示法),3→2出現8次。
= 3→2→(3→2→(3→2→(...3→2→( )...)))→2
= 3→2→(3→2→(3→2→(... ...)))→2(高德納箭號表示法),3→2出現7次。
= ...
= 3→2→ →2(高德納箭號表示法)
= 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1(規則4),其中3→2出現 次。
= 3→2→(3→2→(...3→2→(3→2)))(規則3),其中3→2出現 次。
= ,其中向上箭號出現 次。
可見得3→2→3→3為使用高德納箭號表示法都難以表示的數,這個例子可證明,使用康威鏈式箭號表示法表示大數的效率會比高德納箭號表示法高很多(葛立恆數則是另一個例子)。
一般性的例子
簡單的例子:
,最後利用了性質1。
,最後利用了
,最後利用了 。
對於任何康威鏈X,設 ,則 (見複合函式)。
設 ,則 ,所以 。
例如 ,進而:
我們可以進一步一般化。假設 ,則 ,就是說 。
根據上面可知, ,以及 ,所以
阿克曼函式
阿克曼函式可以使用康威鏈式箭號表示法來表示:
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。)
葛立恆數
葛立恆數 無法用康威鏈式箭號表示法來簡單的表示,但是可以訂出簡潔的上下界。設 ,則 ,(見複合函式),可以得到
證明:這裡會使用到規則3和規則4:
(這裡有64個3→3)
(這裡有64個3→3)
(這裡有64個3→3)
(這裡有65個3→3)
由於是嚴格遞增函式,
這給出了上下界。
利用康威鏈式箭號表示法,很容易表示遠遠大於葛立恆數的數:
其中遠遠大於65,因此遠遠大於葛立恆數。