从迭代的角度认识葛立恒数
日常 2020-2-13
(1),什么是大数呢,大数有很多,在生活中能用科学计数法表示的数字就以足够了,很少会出现二重指数。
而自然科学领域最大的数字莫过于宇宙基本粒子状态总和，它的数值为10^10^10^10^10^122，这是一个很大的数字。但和葛立恒数比起来还是微不足道的。那么葛立恒数到底有多大？它的定义又是什么？
(2),葛立恒数是葛立恒问题的一个解的上限的虚高估计值。
那么什么是葛立恒问题呢？
葛立恒问题
葛立恒数是拉姆齐理论（Ramsey theory）中一个极其异乎寻常问题的上限解，是一个难以想象的巨型数。这个问题表述为：
连接n维超立方体的每对几何顶点，获得一个有着2^n个顶点的完全图（每对顶点之间都恰连有一条边的简单图）。将该图每条边的颜色填上红色或蓝色。那么，使所有填法在四个共面顶点上包含至少一个单色完全子图的最小n值为多少?
这个问题很好理解,现在请你想象一个正方形,把它的每两个点都连上一条线,这样你就得到了一个完全图,所谓完全图就是将每两个点都连起来的图形。然后用两种颜色,分别是红和蓝。对这个图形的每一条边进行染色。你要作的是:不要让一个平面上都是一种颜色,其实二维很容易做到。
但，如果是三维呢？那么你将得到一个正方体，将所有顶点连起来会得到28条线。然后再按上述规则操作，你就会得到:(见下图)
其实,三维也可以做到,如果想在四维也做这个事情,那么就有些困难了,因为随着维度的增加,所连的点数也会成指数增长,最后会让你崩溃。
但美国数学家葛立恒却给出了一个上界,这个解的维度最大也大不过这个G,其中G就是葛立恒数。
那么葛立恒数到底有多大呢？
为了表示它的大小,科学计数法已经无法表示了,我们需要一种运算,叫做上箭号表示法。全称高德纳箭号表示法。
它的定义如下:
a↑b=a^b
a↑↑b=a↑(a↑…(a↑a)…)一共迭代了b次。
a↑↑↑b=a↑↑(a↑↑(…))
…
以此类推,那么现在的数已经有多大了呢？就拿两个3为例
3↑3=3^3=27
3↑↑3=3↑3↑3=3^3^3=3^27≈7.625*10^12
3↑↑↑3=3↑↑3↑↑3=3↑↑(3^3^3)=3^3^3…^3^3
一共有3^3^3个3的迭代幂次,其实哪怕是3↑↑5就已经很恐怖了,见下图:
就更不要说3↑↑↑3了,其实就这个数就已经超越了任何科学意义上所能达到的最大限度了。
但葛立恒数还要比这大的多。
如果定义g(0)=4,g(1)=3↑↑↑↑3,g(n)=3↑↑…↑3共有g(n-1)个连续的箭头。
那么葛立恒数=g(64)
或者定义a↑^(c)b=a↑↑…↑b，共有c个连续的箭头的话,葛立恒数可以表示为:
其实,就最下面那层3↑↑↑↑3,也就是g(1)就已经非常巨大了,如果定义A(1)=3,A(2)=3^3^3,A(n)=3^3^…3共有A(n-1)个三的话,那么g(1)=A(A(3)),通俗点说,见下图。
做为对比,第一层就已经非常巨大了,但葛立恒数是最大的数吗？没有最大的数,但葛立恒数已经被多个数字超越,下面就来看一下葛立恒数在List of googolisms里的排名吧。
下面是TREE(3)以及SCG(13)的排名
差距就是这么大…
在这些更高层级的可计算数字里所用的运算符也相当复杂,不然也绝不容易表示出一个比SCG(13)还大的数字,最后就来看一下葛立恒数还可以用那些运算符号表示。
康威链式箭号:
≈3→3→64→2~3→3→65→2
BEAF≈{3,65,1,2}
E#系统:≈E[3]3##4#64
超阶乘数阵:≈64![2]
另外在葛立恒数G再被求出之前,这个数已经有了一个上界=F^7(12),F(n)=2↑^(n)3.
直到现在为止,葛立恒问题的下界以被提升至13,而上限则被降到了2↑↑2↑↑2↑↑9,这个数仍然特别大。
最后放出葛立恒数G的最后五百位:
02425 95069 50647 38395 65747 91365 19351 79833 45353 62521
43003 54012 60267 71622 67216 04198 10652 26316 93551 88780
38814 48314 06525 26168 78509 55526 46051 07117 20009 97092
91249 54437 88874 96062 88291 17250 63001 30362 29349 16080
25459 46149 45788 71427 83235 08292 42102 09182 58967 53560
43086 99380 16892 49889 26809 95101 69055 91995 11950 27887
17830 83701 83402 36474 54888 22221 61573 22801 01329 74509
27344 59450 43433 00901 09692 80253 52751 83328 98844 61508
94042 48265 01819 38515 62535 79639 96189 93967 90549 66380
03222 34872 39670 18485 18643 90591 04575 62726 24641 95387