鏈式箭號表示法(英語:Chained arrow notation),是康威及蓋伊將上箭號表示法推廣之後而成的箭號表示法。[1][2]鳥的證明中說明,喬納森·鮑爾斯的數陣記號所表示的值通常比鏈式箭號表示法來得大。
Nathan Ho和Wojowu表明鏈式箭號表示法會終止;也就是說,對於所有輸入,都會有一個對應的輸出。[3]
定義[]
- \(a \rightarrow b = a^{b}\)
- \(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb\)(即為上箭號表示法)
- \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\)(當最後一項為1時,可以直接忽略)
- \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
- \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)
例子[]
以下是鏈式箭號的一些小例子:
\(3 \rightarrow 3 \rightarrow 2 = 3\uparrow\uparrow3 = 7,625,597,484,987\)
- \(3 \rightarrow 3 \rightarrow 2 \rightarrow 2\)
- \(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1\)
- \(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2)\)
- \(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3)\)
- \(= 3 \rightarrow 3 \rightarrow (3^{3})\)
- \(= 3 \rightarrow 3 \rightarrow 27\)
- \(= 3 \underbrace{\uparrow\ldots\uparrow}_{27} 3 \)
CG函數[]
康威及蓋伊使用鏈式箭號創造了類似阿克曼數的函數,即\(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\)。雖然在n等於1至3時都與阿克曼數相同,但\(cg(4) = 4\rightarrow 4\rightarrow 4\rightarrow 4 > \lbrace 4,4,3,2 \rbrace\)(使用鳥的證明),因此cg(4)遠遠大於葛立恆數,更遠遠大於第四個阿克曼數特利德特。
這個函數的增長率為\(f_{\omega^2}(n)\),相當於BEAF的4項數陣。
Peter Hurford的擴展[]
Peter Hurford擴展了鏈式箭號,並加入下述規則:[4]
\(a \rightarrow_c b = \underbrace{a \rightarrow_{c-1} a \rightarrow_{c-1}\ldots\rightarrow_{c-1} a \rightarrow_{c-1}a}_{b \rightarrow_{c-1}'s}\)
所有其他規則保持不變。因此,它適用於無下標的情況。注意,\(3 \rightarrow_{2} 3 \rightarrow 3\)是非法的,整個表達式的右箭號必須為單一形式。此外,Hurford表明\(f(n) = n \rightarrow_n n\)相當於\(f_{\omega^3}(n)\)(快速增長階層)。[5]如果我們允許表達式混合不同形式的右箭號,增長率可提升為\(f(n) \approx f_{\omega^\omega}(n)\)。
此外,他還定義了C(n):
- \(C(a) = a \rightarrow_a a\)
- \(C(a,1) = a \rightarrow_{C(a)} a\)
- \(C(a,b) = a \rightarrow_{C(a,b-1)} a\)
- \(C(a,1,1) = C(a,C(a,a))\)
- \(C(a,b,1) = C(a,C(a,b-1,1))\)
- \(C(a,1,c) = C(a,C(a,a,c-1),c-1)\)
- \(C(a,b,c) = C(a,C(a,b-1,c),c-1)\)
函數\(f(n) = C(n,n,n)\)和\(f_{\omega^3 + \omega}(n)\)(快速增長階層)的增長率相當。
來源[]
- ↑ The Book of Numbers, by J. H. Conway and R. K. Guy
- ↑ Chained Arrow Notation
- ↑ http://snappizz.com/termination
- ↑ Large Numbers, Part 2: Graham and Conway
- ↑ Large Numbers, Part 3: Functions and Ordinals