葛立恒数

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

定义

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

$G(0)=4$

$G(1)=3\uparrow \uparrow \uparrow \uparrow 3$

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

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

[math]G(64)=\left. \begin{matrix} 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow}3 \\3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\ \underbrace{\qquad \quad \vdots \qquad \quad} \\3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow}3 \\3\uparrow \uparrow \uparrow \uparrow3\end{matrix} \right \} \text{64 layers}[/math]

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

历史

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

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

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

一说是加德纳在与葛立恒交流后，葛立恒给他提供的这个较为宽松的上界，但无从考证。加德纳的原文章里也没有提及此事。