高德纳箭头

高德纳箭头（Knuth's arrow notation，亦称"上箭头记号"），一种满足右结合律的二元运算。它涉及对运算的递归。

定义

高德纳箭头由如下公式递归定义：

• $a\uparrow b=a^b$
• $a{\uparrow }^{c}0=1$
• $a{\uparrow }^{c+1}(b+1)=a{\uparrow }^c(a{\uparrow }^{c+1}b)$

其中，$a,c$ 均为正整数，$b$ 为自然数，$a{\uparrow }^{c}b=a\underset{c}{\underbrace{\uparrow \uparrow \cdots \uparrow }}b$。

在计算高德纳箭头时，如无括号，按照从右往左的顺序计算，即：

$a{\uparrow }^{m}b{\uparrow }^{n}c=a{\uparrow }^m(b{\uparrow }^{n}c)$

若将高德纳箭头的右结合律更替为左结合律，其余定义不变，将得到下箭头记号。

性质

高德纳箭头有如下性质：

展开

$n{\uparrow }^{k}m=\underset{\text{m个n}}{\underbrace{n{\uparrow }^{k-1}n{\uparrow }^{k-1}\cdots {\uparrow }^{k-1}n}}$

恒等律

• $2{\uparrow }^{c+1}2=2{\uparrow }^{c}2=...=2\uparrow 2=4$
• $a{\uparrow }^{c+1}1=a{\uparrow }^{c}a{\uparrow }^{c+1}0=a{\uparrow }^{c}1=...=a\uparrow 1=a$
• $1{\uparrow }^{c+1}b+1=1{\uparrow }^c(1{\uparrow }^{c+1}b)=1{\uparrow }^c(1{\uparrow }^c(\cdots {\uparrow }^c(1{\uparrow }^{c}1)))=1{\uparrow }^{c}1=1$

增长率

高德纳箭头的 FGH 增长率为 $\omega$，特别地，$a{\uparrow }^{c}b\approx f_{c+1}(b)$。

该推论可通过审视以下两组式子得到：

• $a{\uparrow }^{c+1}(b+1)=a{\uparrow }^c(a{\uparrow }^{c+1}b)$
• $f_{c+1}(b+1)=f_c^{b+1}(b+1)=f_c(f_c^b(b+1))$

超运算

高德纳箭头是目前已被广泛认可、基本采用的超运算记号。

若定义后继运算的运算等级为 0，那么 n 个高德纳箭头的运算等级为 n+2。

历史

高德纳箭头是由 Donald Ervin Knuth 在 1976 年发明的大数记号，曾在 1977 年被 Martin Gardner 用于递归地定义葛立恒数。

而$\mathrm{R}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{d}\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{h}\mathrm{a}\mathrm{m}$本人并未在论文中使用高德纳箭头或超运算来估计 葛立恒问题 的上界，而是使用了类似 阿克曼函数 的递归函数 $F(m,n)$，和分别近似为 $2\uparrow \uparrow n,2\uparrow \uparrow \uparrow n$ 的函数 $\mathrm{T}\mathrm{O}\mathrm{W}\mathrm{E}\mathrm{R}\mathrm{(}\mathrm{n}\mathrm{)},\mathrm{W}\mathrm{O}\mathrm{W}\mathrm{(}\mathrm{n}\mathrm{)}$。

构造过程

高德纳箭头本质上是一种高级运算“折叠”低级运算的记号。

现在让我们回到数学的起点，并考察各种级别的运算是如何逐渐地建立起来的。这将进一步地启发我们构造增长率更快的计数法。

后继

为了使某数 n 变大，最简单的运算应该就是“数出 n 这个数后面的一个数”。我们将这种运算称为“后继”。后继是最基础的运算，表现为 n+1.

加法

我们经常需要表示一种“从 n 开始，取 m 次后继”这样的运算。写得次数太多了之后，我们就引入了一个新的运算符 +，将这样的运算称为“加法”，表示为 n+m.

在 n+m 中，运算 + 折叠了对 n 的 m 次后继运算，即

$n+m=n+\underset{\text{m个1}}{\underbrace{1+1+\cdots +1}}.$

乘法

还能不能更快些呢？假设我们已经通过某些操作得到了 n，那么要想最快地得到一些更大的数，我们就要将 n 加上自身，并将这个过程重复若干次。我们引入一个新的运算符 $\times$，将这样的运算称为“乘法”，表示为 $n\times m$.

在 $n\times m$ 中，运算 $\times$ 折叠了对 n 的 m 次 + 运算，即

$n\times m=\underset{\text{m个n}}{\underbrace{n+n+\cdots +n}}.$

乘方

对乘法重复若干次，我们就可以得到一个增长更快的运算。仿照之前的过程，我们进一步引入一个新的运算符 $\uparrow$，将这一运算称为“乘方”，表示为 $n\uparrow m$ 或 $n^m$.

在 $n^m$ ( $n\uparrow m$ ) 中，运算 $\uparrow$ 折叠了对 n 的 m 次 $\times$ 运算，即

$n^m=\underset{\text{m个n}}{\underbrace{n\times n\times \cdots \times n}}.$

幂塔

我们已经看到了上述各个运算的推广过程：最简单的运算是后继；将后继重复若干次可以得到一个增长更快的运算，称为加法；将加法重复若干次可以再次得到一个增长更快的运算，称为乘法；进一步地将乘法重复若干次，我们又可以得到一个增长速度更快的运算，称为乘方。这里面的每一个运算的增长速度都远远超过了此前的所有运算。

现在如果我们想要得到一个增长速度超越乘方的运算，那么应该如何做呢？答案已经很简单了：我们只需要将乘方运算（单箭头运算 $\uparrow$）重复若干次，并将其定义为一个新的运算“幂塔”即可。我们将这一运算的运算符用双箭头 $\uparrow \uparrow$ 来进行表示。

在 ${}^{m}n$ ( $n\uparrow \uparrow m$ ) 中，运算 $\uparrow \uparrow$ 折叠了对 n 的 m 次 $\uparrow$ 运算，即

$n\uparrow \uparrow m=\underset{\text{m个n}}{\underbrace{n\uparrow n\uparrow \cdots \uparrow n}}=\underset{\text{m个n}}{\underbrace{n^{n^{n^{\cdots }}}}}.$ （注意是右结合）

高德纳箭头

仿照上述定义，以此类推。

最终，我们得到了高德纳箭头的展开定义：

在 $n{\uparrow }^{k}m$ 中，运算 ${\uparrow }^k$ 折叠了对 n 的 m 次 ${\uparrow }^{k-1}$ 运算，即

$n{\uparrow }^{k}m=\underset{\text{m个n}}{\underbrace{n{\uparrow }^{k-1}n{\uparrow }^{k-1}\cdots {\uparrow }^{k-1}n}}.$

计算示例

$\begin{array}{rl}3\uparrow \uparrow \uparrow 3& =3\uparrow \uparrow 3\uparrow \uparrow 3\\ & =3\uparrow \uparrow (3\uparrow 3\uparrow 3)\\ & =3\uparrow \uparrow (3\uparrow 27)\\ & =3\uparrow \uparrow 7625597484987\\ & =\underset{7625597484987}{\underbrace{3^{3^{3^{\cdots }}}}}\end{array}$

$\begin{array}{rl}3\uparrow \uparrow \uparrow \uparrow 4& =3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3\\ & =3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \underset{7625597484987}{\underbrace{3^{3^{3^{\cdots }}}}}\\ & =3\uparrow \uparrow \uparrow (\underset{\underset{7625597484987}{\underbrace{3^{3^{3^{\cdots }}}}}}{\underbrace{3\uparrow \uparrow 3\uparrow \uparrow \cdots \uparrow \uparrow 3}})\\ & =\underset{\underset{\underset{7625597484987}{\underbrace{3^{3^{3^{\cdots }}}}}}{\underbrace{3\uparrow \uparrow 3\uparrow \uparrow \cdots \uparrow \uparrow 3}}}{\underbrace{3\uparrow \uparrow 3\uparrow \uparrow \cdots \uparrow \uparrow 3}}\end{array}$