从加法到葛立恒数

作者: , 共 2308 字

前两天搞葛立恒数,写了一篇。后来感觉没写清楚,再写一篇吧。常常学习,有助于在 AI 时代保持基本智力能力。

要理解葛立恒数,主要是要理解高德纳箭头运算符 $\uparrow$$\uparrow\uparrow$$\cdots$$\uparrow\uparrow\cdots\uparrow$。其实它的定义非常自然,可以简单地理解成加法、乘法、乘方的扩展。

乘法可以认为是加法的重复,$b$$a$ 相加:

$$a\times b=a+a+\cdots+a$$

乘方可以认为是乘法的重复,$b$$a$ 相乘:

$$a^b=a\times a\times\cdots\times a$$

高德纳箭头其实就是这么递归定义的(注意从右往左算):

$$a\uparrow^{n+1}b=a\uparrow^n a\uparrow^n\cdots\uparrow^n a$$

右边是 $b$$a$。再给定初始值,分别为乘法和乘方:

$$a\uparrow^0 b=a\times b,\qquad a\uparrow^1 b=a^b$$

我们看一下乘方的重复是什么:

$$\begin{array}{rcl}a\uparrow^2 b&=&a\uparrow a\uparrow\cdots\uparrow a\\[2pt]&=&a^{a^{\cdot^{\cdot^{\cdot^{\,a}}}}}\end{array}$$

它是 $b$$a$ 摞成的幂塔。注意这个计算是从右上往左下算的:$3^{3^3}$$3^{27}$,而不是 $27^3$。前者是 7 万亿,后者不到 2 万。

$a\uparrow^2 b$ 还在人类的直观理解范围以内,$a\uparrow^3 b$ 已经无法直观理解了,但可以大致解释如下:

  • 生成一个 $a$ 层的 $a$ 的幂塔,得到一个数;
  • 生成一个 $a$ 的幂塔,层数为上一步得到的数;
  • 不断重复上面的步骤,一共执行 $b-1$ 次。

回到葛立恒数,定义如下:

$$A_n=3\uparrow^n 3$$

$$G_1=A_4,\qquad G_{n+1}=A_{G_n}$$

这里要注意递推的量是箭头数:$G_{n+1}=3\uparrow^{G_n}3$ 是箭头有 $G_n$ 个,而不是把塔高设成 $G_n$

$A_3$ 是最后一个人类可以在形式上直观理解的数:

$$\begin{array}{rcl}A_3&=&3\uparrow^2(3\uparrow^2 3)\\[2pt]&=&3^{3^{\cdot^{\cdot^{\cdot^{\,3}}}}}\end{array}$$

这座幂塔的层数是 $A_2=3\uparrow^2 3=7\,625\,597\,484\,987$,也就是 7 万亿多层。

但这个数已经不可能在物理世界里出现了。只要世界是离散可分的,那么在可以想象的时间范围、在可以想象的空间范围,考虑所有可能的粒子状态,整个宇宙的可描述状态不会超过 5 层幂塔。而 $A_3$ 的幂塔有 7 万亿层。

$G_1$ 是人类还可以大致想象的最后一个大数:

$$G_1=A_4=3\uparrow^3 A_3$$

它可以如下迭代产生:

  • 构建一个 3 的幂塔,层数为 $A_3$,得到一个数;
  • 构建一个 3 的幂塔,层数为上一步得到的数;
  • 不断重复上面的步骤,一共执行 $A_3-2$ 次。

就这么说吧,光是第一步得到的数,都远远超过「以宇宙可描述状态数为层数的幂塔」。更别提这样的操作还要做 $A_3-2$ 次。

而葛立恒数被定义为 $G_{64}$。这里的 64 并没有特殊含义。这里面每一个都不能被直观理解了,是哪个都无所谓,在大数领域没有明显区别。

Q. E. D.

最近迷上了学习超级大数,就是那种特别特别大的数,超乎想象的大。这其中最有名的就是葛立恒数。
写 TREE(3) 那篇的时候,开头有个热身小游戏(把树换成珠子串)。当时只手算了 1 种和 2 种颜色,这回把它算到底,并且把「为什么涨得这么快」讲清楚。文中的符号都是随用随定义的,末尾还附了一张符号表,忘了可以回头查。