下箭号表示法

下箭号表示法（亦称"下箭头记号"），一种满足左结合律的二元运算。

定义

下箭号由如下公式递归定义：

$a ↓^{1} b = a^{b}$
$a ↓^{c} 1 = a$
$a ↓^{c + 1} (b + 1) = (a ↓^{c + 1} b) ↓^{c} a$

其中， $a, b, c$ 均为正整数， $a ↓^{c} b = a \underset{c}{\underset{⏟}{↓ ↓ \dots ↓}} b$ .

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

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

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

性质

下箭号有如下性质：

展开

$n ↓^{k} m = \underset{m个n}{\underset{⏟}{n ↓^{k - 1} n ↓^{k - 1} \dots ↓^{k - 1} n}}$

增长率

下箭号虽然看起来增长得比高德纳箭头慢得多，但其FGH 增长率仍为 $ω$ .

可以证明的是， $a ↓^{2 n - 1} b \geq a ↑^{n} b$ .

超运算

下箭号是一种超运算记号。

计算示例

$\begin{aligned} 3 ↓ ↓ ↓ 3 & = (3 ↓ ↓ 3) ↓ ↓ 3 \\ = (3 ↓ 3 ↓ 3) ↓ ↓ 3 \\ = (27 ↓ 3) ↓ ↓ 3 \\ = 19683 ↓ ↓ 3 \\ = 1968 3^{1968 3^{2}} \\ = 3^{3^{20}} \end{aligned}$