高德纳箭号表示法

高德纳箭号表示法（Knuth's up-arrow notation）是种用来表示很大的整数的方法，由高德纳于1976年设计。它的概念来自幂是重复的乘法，乘法是重复的加法。

## 简介

乘法是重复的加法：$a \times b = a+a+\cdots+a$ （有$b$个$a$）

幂是重复的乘法：$a^b = a \uparrow b = a \times a \times \cdots \times a$（有$b$个$a$）

于是高德纳定义“双箭号”运算符，作重复的幂运算，或称迭代幂次：

$a \uparrow\uparrow b= \begin{matrix} \underbrace{ a \uparrow a \uparrow \cdots \uparrow a } \\ b\end{matrix} = \begin{matrix} \underbrace{a^{a^{.^{.^{.{a}}}}}} \\ b\end{matrix} = {^{b}a}$（中文读法为“b个a重幂”）

计算时是由右至左计的。

$$3 \uparrow \uparrow 2 = {^{2}3} = 3^3 = 27$$

$$3 \uparrow \uparrow 3 = {^{3}3} = 3^{3^3} = 3^{27} = 7,625,597,484,987$$

$$3 \uparrow \uparrow 4 = {^{4}3} = 3^{3^{3^3}} = 3^{7625597484987} \approx 1.2580143\times 10^{3638334640024}$$

$$3 \uparrow \uparrow 5 = {^{5}3} = 3^{3^{3^{3^3}}} = 3^{3^{7625597484987}} \approx 3^{1.2580143\times 10^{3638334640024}}$$

多于两个箭号时。

$$3 \uparrow\uparrow \uparrow 2 = 3 \uparrow\uparrow 3 = {^{3}3} = 3^{3^3} = 3^{27} = 7,625,597,484,987\,\!$$

$$3 \uparrow\uparrow \uparrow 3 = 3 \uparrow\uparrow 3 \uparrow\uparrow 3 = {^{^{3}3}3} = {^{7625597484987}3} = \begin{matrix} \underbrace{3^{3^{.^{.^{.{3}}}}}} \\ 7625597484987\end{matrix}$$

## 使用指数来解释高德纳箭号表示法

$a \uparrow \uparrow b$代表重复的幂，或迭代幂次，例如：

$$a \uparrow \uparrow 4 = a \uparrow (a \uparrow (a \uparrow a)) = a^{a^{a^a}}$$

当b为变量或过大时，重复的幂可以如下表示：

$$a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}$$

指数不只能解释两个箭号的运算，三个箭号也行。

$$a \uparrow \uparrow \uparrow 2 = a \uparrow \uparrow a = <pre> \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a}$$

$$a \uparrow \uparrow \uparrow 3 = a \uparrow \uparrow (a \uparrow \uparrow a) = <pre> \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }$$

$$a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow [a \uparrow \uparrow (a \uparrow \uparrow a)] = <pre> \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}$$

再次的，当b为变量或过大时，三个箭号的运算可以如下表示：

$$a \uparrow \uparrow \uparrow b = <pre> \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b$$

四个箭号可以如下表示：

$$a \uparrow \uparrow \uparrow \uparrow 2 = a \uparrow \uparrow \uparrow a = <pre> \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} a$$

$$a \uparrow \uparrow \uparrow \uparrow 3 = a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a) = <pre> \left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} a$$

$$a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow [a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a)] = <pre> \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} a$$

再次的一般化：

$$a \uparrow \uparrow \uparrow \uparrow b = <pre> \underbrace{ \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \cdots \right\} a }_{b}$$

这种方法可以用来表示任何能够用高德纳箭号表示法表示的数，但是会变得相当麻烦。

## 一般化

若要用多个箭号时，可用↑n表示，但有些数还是大得连这种表示法也不够用，例如葛立恒数。

这时可能用hyper运算符或康威链式箭号表示法方便一点。

$$<pre> \begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix}$$

## 定义

对于整数$a$、非负整数$b$和正整数$n$：

$a\uparrow^n b= \left\{ \begin{matrix} 1, \\ a^b, \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), \end{matrix} \right.$｜若$b=0$。

若$n=1$。

其他。

这个表示法符合向右结合律。

## 参考

- Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235-1242.
- Robert Munafo, Large Numbers