高德纳箭头

高德纳箭头（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$

增长率

高德纳箭头的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 }^{c}m=\underset{\text{m个n}}{\underbrace{n{\uparrow }^{c-1}n{\uparrow }^{c-1}\cdots {\uparrow }^{c-1}n}}$