高德纳箭头

高德纳箭头（Knuth's up-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,b,c$均为正整数，$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增长率为 ω，特别地，

$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(f_{c+1}(b))$

超运算

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

若定义后继运算的运算等级为$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年发明的大数记号，曾被 $\mathrm{R}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{d}\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{h}\mathrm{a}\mathrm{m}$ 用于递归地定义葛立恒数。

形式化定义

$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}}$