葛立恒数：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年6月30日 (一) 18:20的版本

葛立恒数是拉姆齐理论中一个问题（即葛立恒问题）的上界。它也是大数领域中最著名的数之一，与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年^[1]对葛立恒问题提供的上界为

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

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

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

参考资料

↑ GRAHAM R L, ROTHSCHILD B L. Ramsey’s theorem for ff-parameter sets[J]. Transactions of the American Mathematical Society, 1971, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf
↑ Donald E. Knuth, Mathematics and Computer Science: Coping with Finiteness, Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf
↑ GARDNER M. Mathematical games[J]. Scientific American, 1977, 237(3): 28-38.https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf

[1] GRAHAM R L, ROTHSCHILD B L. Ramsey’s theorem for ff-parameter sets[J]. Transactions of the American Mathematical Society, 1971, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf

[2] Donald E. Knuth, Mathematics and Computer Science: Coping with Finiteness, Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf

[3] GARDNER M. Mathematical games[J]. Scientific American, 1977, 237(3): 28-38.https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf

[1]

[2]

[3]

@@ 第17行： / 第17行： @@
 ==== 历史 ====
-葛立恒数的作者其实并非葛立恒。葛立恒最早在1971年对葛立恒问题提供的上界为
+葛立恒数的作者其实并非葛立恒。葛立恒最早在1971年<ref>GRAHAM R L, ROTHSCHILD B L. Ramsey’s theorem for ff-parameter sets[J]. Transactions of the American Mathematical Society, 1971, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf</ref>对葛立恒问题提供的上界为
 <math>F^7(12)=F(F(F(F(F(F(F(12)))))))</math>，其中<math>F(n)</math>的定义等价于使用了高德纳箭头的<math>2\uparrow ^n 3</math>.
-而高德纳箭头在1976年才在出现在高德纳的论文中。现在的葛立恒数实际出自于加德纳在1977年发表的文章。
+而高德纳箭头在1976年才在出现在高德纳的论文<ref>Donald E. Knuth, ''Mathematics and Computer Science: Coping with Finiteness'', Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf</ref>中。现在的葛立恒数实际出自于加德纳在1977年发表的文章<ref>GARDNER M. Mathematical games[J]. Scientific American, 1977, 237(3): 28-38.https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf</ref>。
 一说是加德纳在与葛立恒交流后，葛立恒给他提供的这个较为宽松的上界，但无从考证。加德纳的原文章里也没有提及此事。
+==== 参考资料 ====
+<references />