葛立恒数：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年6月30日 (一) 04:49的版本

葛立恒数是拉姆齐理论中一个问题（即葛立恒问题）的上界。它也是大数领域中最著名的数之一，与TREE(3)、SCG(3)齐名。

定义

葛立恒函数是用高德纳箭头递归定义的：

$G (0) = 4$

$G (1) = 3 ↑ ↑ ↑ ↑ 3$

$G (n + 1) = 3 ↑^{G (n)} 3$

葛立恒数被定义为 $G (64)$ 。（有时也被写作 $G$ 、 $g_{64}$ 、 $g (64)$ ）

$G (64) = \begin{aligned} 3 \underset{3 \underset{\underset{3 \underset{3 ↑ ↑ ↑ ↑ 3}{\underset{⏟}{↑ . . . . . . ↑}} 3}{\underset{⏟}{⋮}}}{\underset{⏟}{↑ . . . . . . . . ↑}} 3}{\underset{⏟}{↑ . . . . . . . . . ↑}} 3 \end{aligned}} 64 l a y e r s$

葛立恒函数的FGH 增长率约为 $ω + 1$ 。

历史

葛立恒数的作者其实并非葛立恒。葛立恒最早在1971年对葛立恒问题提供的上界为

$F^{7} (12) = F (F (F (F (F (F (F (12)))))))$ ，其中 $F (n)$ 的定义等价于使用了高德纳箭头的 $2 ↑^{n} 3$ .

而高德纳箭头在1976年才在出现在高德纳的论文中。现在的葛立恒数实际出自于加德纳在1977年发表的文章。

@@ 第12行： / 第12行： @@
 葛立恒数被定义为<math>G(64)</math>。（有时也被写作<math>G</math>、<math>g_{64}</math>、<math>g(64)</math>）
-<math>G(64)=\left. \begin{align} 3\underbrace{\uparrow ......... \uparrow}_{3 \underbrace{\uparrow .\,.\,.\,.\,.\,.\,.\, \uparrow}_{\underbrace{\ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ }_{3 \underbrace{\uparrow ...... \uparrow}_{3\uparrow\uparrow\uparrow\uparrow 3} 3} } 3} 3\end{align} \right\}64\ \rm layers</math>
+<math>G(64)=\left. \begin{align} 3\underbrace{\uparrow ......... \uparrow}_{3 \underbrace{\uparrow .\,.\,.\,.\,.\,.\,.\,.\, \uparrow}_{\underbrace{\ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ }_{3 \underbrace{\uparrow ...... \uparrow}_{3\uparrow\uparrow\uparrow\uparrow 3} 3} } 3} 3\end{align} \right\}64\ \rm layers</math>
 葛立恒函数的[[FGH]][[增长率]]约为<math>\omega +1</math>。