高德纳箭头

高德纳箭头(Knuth's arrow notation, 亦称"上箭头记号")，一种满足右结合律的二元运算。其定义如下：

• $a\uparrow b=a^b$
• $a{\uparrow }^{c}1=a$
• $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 }^{c}b{\uparrow }^{c}c=a{\uparrow }^c(b{\uparrow }^{c}c)\ne (a{\uparrow }^{c}b){\uparrow }^{c}c$

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

恒等律

$2{\uparrow }^{c+1}2=2{\uparrow }^{c}2=4$

$1{\uparrow }^{c+1}b=1{\uparrow }^{c}b=1$

$a{\uparrow }^{c+1}0=a{\uparrow }^{c}0=1$

增长率

高德纳箭头的FGH增长率为$\omega$，特别地，

$a{\uparrow }^{c}b\approx f_c(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)$

超运算

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

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

历史

高德纳箭头是由 $\mathrm{D}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{d}\mathrm{E}\mathrm{r}\mathrm{v}\mathrm{i}\mathrm{n}\mathrm{K}\mathrm{n}\mathrm{u}\mathrm{t}\mathrm{h}$ 在1976年发明的大数记号，曾在1977年被 $\mathrm{M}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{G}\mathrm{a}\mathrm{r}\mathrm{d}\mathrm{n}\mathrm{e}\mathrm{r}$ 用于递归地定义葛立恒数。

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

形式化定义

$n\uparrow m=n^m$

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

该定义可通过以下分析与推理得到：

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

后继是最基础的运算，表现为 $n+1$.

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

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

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

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

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

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

在 ${}^{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}$