高德纳箭头

高德纳箭头(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$
• $1{\uparrow }^{c+1}b=1{\uparrow }^{c}1{\uparrow }^{c+1}(b-1)=1{\uparrow }^c{b}_2=...=1\uparrow b_k=1$
• $a{\uparrow }^{c+1}1=a{\uparrow }^{c}a{\uparrow }^{c+1}0=a{\uparrow }^{c}1=...=a\uparrow 1=a$

增长率

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

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

• $a\uparrow b\approx f_2(b)=2^b\times 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))\approx f_c(f_c^b(b))=f_c(f_{c+1}(b))$

超运算

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

若定义后继运算的运算等级为 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}$本人并未在论文中使用高德纳箭头或超运算来估计 Graham问题 的上界，而是使用了类似 ACKERMANN函数 的递归函数 $F(m,n)$，和分别近似为 $2\uparrow \uparrow n,2\uparrow \uparrow \uparrow n$ 的函数$TOWER(n),WOW(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}$