易坊好文馆

  1. 首页 > 奇闻 >

比“葛立恒数”还大——TREE(3)：从一棵树上长出来的最大数字！( 二 )



这种包含关系在数学上的术语叫做：下确界-可嵌入（INF-embeddable） ， 搞硬件嵌入式系统的朋友们应该相当熟悉这个词 。 这里INF是Infimum and supremum的简称 ， 是下确界或者说是最大下界的拉丁文缩写 。

为什么这里要用这个词 ， 因为合适：当我们把一棵树某个枝条上的节点当做一个大小进行排序 ， 且根节点最小时 ， 那么两个节点的最近共同祖先其实就是最大的 ， 且比这两个节点都小的节点 。 （很绕 ， 但真的就是这样的）
现在我们开始正式画树游戏 ， 我们要画出树尽可能多的森林 ， 也就是“树列” 。
从TREE(1)开始 ， 只用一只颜色画树：假设你用的是红色 ， 那么你只能画出一棵树 ， 不然就违反规则了 ， 因此TREE(1)=1 ， 如下图 。

接下来是TREE(2) ，我们用红色和蓝色画树 ， 我们发现 ， 最多只能画出三个树结构 ， 不然就违反规则了 ， 因此TREE(2)=3 ， 如下图 。

然后是TREE(3) ， 我们用红、蓝、绿三种颜色 ， 这下神奇的事情发生了 ， 按照这种规则我们好像可以无穷无尽的画下去 。

那究竟可不可以画完呢？TREE(3)究竟是不是无穷大呢？这就是数学家哈维·弗雷德曼研究的数学问题 。 结论是：TREE(3)并不是无穷大 ， 而是一个有限的数字 ， 只是比葛立恒数还要大得多 。
那TREE(3)不是无穷大这个结论是如何证明出来的呢？如果TREE(3)是无限大 ， 那TREE(3)就没有任何讨论的意义了 。 就像我们都知道自然数的个数是无限的 ， 讨论最大的自然数没有意义 。
TREE(3)这个数是有限的这个结论是经过了严密的证明的 ， 证明人就是计算机领域大名鼎鼎的克鲁斯卡尔 。 他的证明过程我们可以用一句话总结：如果TREE(3)是无限的 ， 那就一定存在违反规则的情况（一定会存在后面包含前面的情况） 。

这种证明方式很巧妙 ， 外行甚至会觉得这是耍小聪明 。 但是懂行地知道 ， 这是非常厉害且巧妙的一种方法 。
那我们如何理解TREE(3)的大小呢？前面我们理解葛立恒数用的是高德纳箭头 ， 但是这种方法在TREE(3)面前根本不管用 。 面对TREE(3) ， 我们需要用到“超运算表示法” 。
我们可以举个例子来理解超运算：
a+b表示a加上b个1的和 ， 用a[1
b表示 。
a*b表示b个a相加之和 ， 用a[2
b表示 。
a^b表示b个a相乘 ， 用a[3
b表示 。
迭代幂次b个a重幂表示a^a^a^···^a^a（一共b个a） ， 用a[4
b表示 ， 从右往左运算 。

举个例子 ， 超4运算：2[4
4=2^2^2^2=2^2^4=2^16 。
了解了超运算之后 ， 这里我们引入a[n
b ， 超n运算 ， 这里a是底数 ， b是超指数 ， n则是阶数 。 举个例子2[5
4=2^2^2^···^2^2 ， 一共65536个2 。 这已经不是指数爆炸了 ， 这是一个天文数字了 ， 比宇宙中所有原子的数量还要多得多 。
利用超运算 ， 数学家引入了一个阿克曼函数 ， 太复杂 ， 这里就不展开了：
总之记得这个阿克曼函数：A(x)=2[x+1
x 。
通过嵌套 ， 数学家们计算出葛立恒数约为：A^64(4) ， 而TREE(3)用超运算法 ， 通过阿克曼函数表示就是：
TREE(3)=A^A(187196)(1)

所以我们说葛立恒数在TREE(3)面前小的不能再小了 。 我们的大脑根本无法想象这个数到底有多大 ， 我们举个例子帮助大家理解：你在1后面写0 ， 假设物质和空间均是无限的 ， 你一个普朗克时间写一个0 ， 那么从宇宙诞生直到宇宙毁灭 ， 你都写不完这个数 。

在数学上 ， 我们想要构造出一个巨大无比的数字是非常简单的 ， 但是我们永远也无法理解这个数字究竟有多大 ， 这才是我们的无奈 。 我们明明无法理解这些大数字 ， 但是我们却知道这些大数字都是有限的 ， 且有数学意义的 。

不仅如此 ， TREE(3)是有限的 ， TREE(TREE(3))也是有限的 ， 但是我们无法理解 。 这就是数学的有趣之处 。
你知道数学里的“自然常数e”吗？看数学大神欧拉是如何解决的！

【比“葛立恒数”还大——TREE(3)：从一棵树上长出来的最大数字！】数学上最大的数有多大？葛立恒数：一个大到你写不出来的数字！

推荐阅读


上一篇：新冠病毒哪来的

下一篇：“神十三”3人组平安返航，中国载人航天20年，有些事你有必要知道