要比較 G(TREE(3))和 TREE(G(64))的大小,首先需要理解這兩個函數:
• G(n)是葛立恆函數,增長極其迅速,用於表示葛立恆數(例如 G(64)是著名的葛立恆數)。
• TREE(n)是TREE函數,源於克魯斯卡爾樹定理,其增長速率遠超過葛立恆函數,甚至遠超過 fϑ(Ω^ωω)(n)級別(在快速增長層級中)。
分析:
1. G(TREE(3)):這裏以 TREE(3)作為輸入計算葛立恆函數。TREE(3)本身是一個巨大的數,遠大於葛立恆數 G(64)。由於 G(n)的增長非常快(大致相當於 fω+1(n)級別),但輸入是巨大的 TREE(3),所以 G(TREE(3))是一個難以想像的數。
2. TREE(G(64)):這裏以葛立恆數 G(64)作為輸入計算TREE函數。由於 TREE(n)的增長速率遠超過 G(n)(實際上 TREE(n)的增長速率遠高於任何可遞歸函數,其增長率在快速增長層級中遠高於 fϑ(Ωωω)(n)),而 G(64)雖然巨大,但作為輸入時,TREE(G(64))會更大。
比較:
• TREE(n)的增長速率遠遠超過 G(n)。例如,即使對於較小的 n,TREE(n)也迅速超過 G(n)。事實上,TREE(3)已經遠大於 G(64)。
• 因此,TREE(G(64))是以 G(64)為輸入的TREE函數,其值會遠遠超過 G(TREE(3))。因為:
o G(TREE(3))是葛立恆函數應用於一個巨大數,但葛立恆函數的增長有上限(ω+1級別)。
o TREE(n)的增長速率遠高於葛立恆函數(高於 ϑ(Ωωω)級別),所以即使輸入是較小的數(但這裏輸入是 G(64),已經很大),輸出也會大得多。
結論:
TREE(G(64))遠大於 G(TREE(3))。
最終答案:
TREE(G(64))≫G(TREE(3))
即 TREE(G(64))比 G(TREE(3))大得多。