-
康威鏈式箭號表示法
鎖定
- 中文名
- 康威鏈式箭號表示法
- 分 類
- 數學表示法、大數
康威鏈式箭號表示法定義
康威鏈式箭號表示法的長度定義如下:
- 任何一個正整數是長度為1的康威鏈。
- 假若有一個長度是n的康威鏈,後面加上→和一個正整數,此時形成的鏈長度為n+1。
3、
等價於
。
4、
等價於
(在這裏,
出現
次,
出現
次,括號數量為
對).
第四條規則可以以遞迴關係式列出,避免省略號的出現:
4a、
4b、
康威鏈式箭號表示法性質
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)
=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為使用高德納箭號表示法都難以表示的數,這個例子可證明,使用康威鏈式箭號表示法表示大數的效率會比高德納箭號表示法高很多(葛立恆數則是另一個例子)。
康威鏈式箭號表示法一般性的例子
簡單的例子:
設
,則
,所以
。
例如
,進而:
根據上面可知,
,以及
,所以
康威鏈式箭號表示法阿克曼函數
阿克曼函數可以使用康威鏈式箭號表示法來表示:
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:
由於
是嚴格遞增函數,
這給出了上下界。
利用康威鏈式箭號表示法,很容易表示遠遠大於葛立恆數的數:
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:4次歷史版本
- 最近更新: smile极度冰点