康威鏈式箭號表示法,是由約翰·何頓·康威發明的,用來表示大數。形式上看起來會像這樣:2→3→4→5→6。
基本介紹
- 中文名:康威鏈式箭號表示法
- 分類:數學表示法、大數
定義,性質,例子,一般性的例子,阿克曼函式,葛立恆數,
定義
康威鏈式箭號表示法的長度定義如下:
- 任何一個正整數是長度為1的康威鏈。
- 假若有一個長度是n的康威鏈,後面加上→和一個正整數,此時形成的鏈長度為n+1。
3、
等價於
。
![](/img/8/3b2/44879a835333e5052accda6bce91.jpg)
![](/img/c/818/ecd839dd6cdcd4e3d49b68cf83ea.jpg)
4、
等價於
(在這裡,
出現
次,
出現
次,括弧數量為
對).
![](/img/e/6e0/fd6938204ac5e2bc05be2f6eb4bf.jpg)
![](/img/f/739/fe0f9a623eedd9b3d9abdc4f8afa.jpg)
![](/img/3/6b6/5c8a46bf34b78cbb1329d9b70077.jpg)
![](/img/8/1a8/3d8247f8a5d11f4d2772cb48d98d.jpg)
![](/img/f/868/be2a3f84ee6d8257907b86f3fd0d.jpg)
![](/img/1/f3a/62d42ff43da61e30a67ad8e62828.jpg)
![](/img/1/f3a/62d42ff43da61e30a67ad8e62828.jpg)
第四條規則可以以遞迴關係式列出,避免省略號的出現:
4a、![](/img/c/79c/9ffb00e54e6832b3f295b73146c0.jpg)
![](/img/c/79c/9ffb00e54e6832b3f295b73146c0.jpg)
4b、![](/img/2/ee7/dec202af38dcfba5d8089c7dff1d.jpg)
![](/img/2/ee7/dec202af38dcfba5d8089c7dff1d.jpg)
性質
1、長度為3的康威鏈對應hyper運算符和高德納箭號表示法:
![](/img/a/6b2/2d99a94fb1e1a8f2d0988a032818.jpg)
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是先被算出來的整數,如
.
![](/img/3/c88/9e71cc0663554bf23c592d6fadc2.jpg)
康威鏈不能被拆分,其箭號並不是二元運算符。其他二元運算符具有交換律及結合律,如2 + 3 = 3 + 2,2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2),或者是按照規定的順序,如
這類指數是從右至左計算,先計算
= 81,再計算
。康威鏈並不符合上述性質。例如:
![](/img/5/598/541c4aafb2ab082b13a88a74acaf.jpg)
![](/img/e/01a/2ee43431bca0c32fff2e882a3be8.jpg)
![](/img/8/c99/a934225949d6f16233eff2317d9e.jpg)
![](/img/b/467/fed086ea615f1d182734eb1bd9dd.jpg)
![](/img/2/654/2fa9071f62385fc17022225556cd.jpg)
![](/img/0/640/54abde71ba174f5c8ac6ebaba0bc.jpg)
第一個式子並不等於下面任何式子。
例子
例子很快會變得非常複雜,先從簡單的開始(其中有些例子也會套用高德納箭號表示法):
(1)n
= n(規則1)
(2)p→q
=
(規則2)
![](/img/e/f7a/636e69029556246777a9359b981c.jpg)
例如:![](/img/5/3ea/7c591eef2d4f4893a6bdfccaa3cf.jpg)
![](/img/5/3ea/7c591eef2d4f4893a6bdfccaa3cf.jpg)
(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)
利用高德納箭號表示法可以很容易解決:![](/img/6/789/ca5f008ed7fbb358e33a9cbc086d.jpg)
![](/img/6/789/ca5f008ed7fbb358e33a9cbc086d.jpg)
(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)
高德納箭號表示法:![](/img/5/b84/b07233b2cd14867ee4369038c635.jpg)
![](/img/5/b84/b07233b2cd14867ee4369038c635.jpg)
(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)
![](/img/0/d76/eab87f6fd19ffe13a8336a9a6c16.jpg)
![](/img/f/e85/c4d57f0474250e876d4035bc484e.jpg)
=65536
若用高德納箭號表示法可得:![](/img/6/81a/e3e6e4961caf6c51147e83eec912.jpg)
![](/img/6/81a/e3e6e4961caf6c51147e83eec912.jpg)
(7)2→3→2→2
= 2→3→(2→3)→1(規則4)
= 2→3→8(規則2和規則3)(利用高德納箭號表示法即為
)
![](/img/b/5a5/15624feddb0d1dc93446e0d0bc1d.jpg)
= 2→(2→2→7)→7(規則4)
= 2→4→7(性質6,利用高德納箭號表示法即為
)
![](/img/6/a5f/5a6660d6d54a23d90e8c19004c15.jpg)
= 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(利用前面的例子)
= 大到無法想像的數
高德納箭號表示法:![](/img/4/b5c/6cc2594a2074317e7a90f85e7409.jpg)
![](/img/4/b5c/6cc2594a2074317e7a90f85e7409.jpg)
(8)3→2→2→2
= 3→2→(3→2)→1(規則4)
= 3→2→9(規則2和規則3)
= 3→3→8(規則4)
高德納箭號表示法:![](/img/6/670/0595d5aed954be6c3539ffd14bc9.jpg)
![](/img/6/670/0595d5aed954be6c3539ffd14bc9.jpg)
(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次。
![](/img/b/04a/4e301a92d801c49236725db076e5.jpg)
= 3→2→(3→2→(3→2→(...3→2→(
)...)))→2
![](/img/5/c57/1f13abccdbfbd5d7ce61631da048.jpg)
= 3→2→(3→2→(3→2→(...
...)))→2(高德納箭號表示法),3→2出現7次。
![](/img/c/629/05c3f292f7e39da8d244d1f6f86a.jpg)
= ...
= 3→2→
→2(高德納箭號表示法)
![](/img/2/74a/fb7a997f0bcd9c3f2fc25f5d41a2.jpg)
= 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1(規則4),其中3→2出現
次。
![](/img/6/1c3/7854bb0179388e27dcfe2f096e0d.jpg)
= 3→2→(3→2→(...3→2→(3→2)))(規則3),其中3→2出現
次。
![](/img/4/f7b/cef96cd78e973c0ad20c99ffab09.jpg)
=
,其中向上箭號出現
次。
![](/img/a/d51/74b7b466f43809ea862f5adc7f7b.jpg)
![](/img/4/f7b/cef96cd78e973c0ad20c99ffab09.jpg)
![](/img/5/ed3/b46f67863f5fb95bee35165b8c53.jpg)
可見得3→2→3→3為使用高德納箭號表示法都難以表示的數,這個例子可證明,使用康威鏈式箭號表示法表示大數的效率會比高德納箭號表示法高很多(葛立恆數則是另一個例子)。
一般性的例子
簡單的例子:
![](/img/9/4be/93045c8c11a3ee56d193f7a73a2b.jpg)
![](/img/a/ed4/90a002e756378a5f5147e40022b7.jpg)
![](/img/a/5f7/c41169b0df0eca7d2daa34287067.jpg)
![](/img/4/939/a375bbd7cb5f6f7d0d03adb02cf8.jpg)
![](/img/5/8dc/3eec398b76f1b8536bdb8ad1829d.jpg)
![](/img/6/0dc/4843355ab39e534177f4f57a73c5.jpg)
設
,則
,所以
。
![](/img/6/19f/87ab271a8d7358a4afc565246099.jpg)
![](/img/6/b85/9df9acaf14844a4a85e26ac42f00.jpg)
![](/img/2/7cb/9ea8773ed1c972b3ab2a85a83768.jpg)
例如
,進而:
![](/img/9/32b/a2219e075e7267d2bea0fdcd3260.jpg)
![](/img/a/690/738d1a79edf3da1f97965f140465.jpg)
![](/img/6/efd/36dc751759a51347a7bdeba2226b.jpg)
![](/img/3/712/a555db35a5c866db293e65297cf9.jpg)
![](/img/a/43e/a66b60c0cfa487d1528a95f2f2ee.jpg)
根據上面可知,
,以及
,所以![](/img/c/5ff/d1e25383e06b59e677be6347f601.jpg)
![](/img/1/23a/f31259683364a3cf54459d87ea26.jpg)
![](/img/d/041/a8b27a0bb82378c52a429e1b43cb.jpg)
![](/img/c/5ff/d1e25383e06b59e677be6347f601.jpg)
阿克曼函式
阿克曼函式可以使用康威鏈式箭號表示法來表示:
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。)
葛立恆數
![](/img/c/2e9/2d08915e24044343b15f894f973d.jpg)
證明:這裡會使用到規則3和規則4:
![](/img/2/8e4/8b44a47edd2f5dca420a1711f7a2.jpg)
![](/img/0/ef1/d0045d9223a10bd2b76c1d52a5ac.jpg)
![](/img/2/9fa/45e83b05a90ea236929916240f83.jpg)
![](/img/f/5a2/6cfb7e8908d0a9c3a7028ed7a336.jpg)
![](/img/6/7cd/566358c9365bed9184880d7bdbce.jpg)
![](/img/5/22d/91c0b3c81ff30a6d065f96d4aba0.jpg)
![](/img/a/490/0a2330339b6ba2dac5a5c55ee24b.jpg)
![](/img/2/7be/dbe2208e6964992cc7c997ae9777.jpg)
![](/img/2/a60/03d5831544364310f906633cf921.jpg)
![](/img/5/caf/0e9df8c05771b12e635c9a203bb6.jpg)
由於
是嚴格遞增函式,
![](/img/1/36b/a83b526b5dc34783baf9181d1cdd.jpg)
![](/img/7/fe6/ce8fb68b712b3a3a3258e176d009.jpg)
這給出了上下界。
利用康威鏈式箭號表示法,很容易表示遠遠大於葛立恆數的數: