超运算

超运算序列是数学中一种二元运算的序列，前三项分别为加法、乘法、幂，一般来说，除了序列中第一项的加法运算之外，序列中每一项的运算都是重复的前一项的运算（例如乘法是重复的加法：$a \cdot b = \underbrace{a + a + a + \cdots + a}_b$，幂是重复的乘法：$a^b = \underbrace{a \cdot a \cdot a \cdot \ldots \cdot a}_b$）。这些运算通称为超运算（或称为hyper运算符）。序列中的第n项称为超-n运算或第n级的超运算，其符号为n。英文则由鲁宾·古德斯坦命名，当n≥4时，由n的希腊语前缀加上后缀-ation组成（例如超-4运算称为tetration，超-5运算称为pentation）。当n≥3 时，使用高德纳箭号表示法可将超-n运算的符号表示为(n-2)个箭头。

超运算可通过递归进行定义，对于所有正整数a，正整数b和正整数n：

$$a [1] b = a + b, \ \text{for} \ n > 1, \ a [n] b = \underbrace{a [n-1] (a [n-1] (a [n-1] \cdots (a [n-1] (a [n-1] a}_b)) \cdots ))$$

除这一最常见的定义之外，超运算还有其他的变体。（见下文）

## 定义

超运算序列是定义在自然数集$\mathbb{N}$上的一个序列，记为$H_n$。前三项为加法（n=1）、乘法（n=2）和幂（n=3）。高阶超运算的参数与幂运算相似，即a称为底数，b称为指数（或称超指数），而n则称为阶数。

用高德纳箭号表示法可以将超运算定义为

$$H_n(a,b)=a\uparrow^{n-2}b=a[n]b=\begin{cases} b+1&n=0\\ a&n=1\land b=0\\ 0&n=2\land b=0\\ 1&n\geq3\land b=0\\ H_{n-1}(a,H_n(a,b-1))&\text{otherwise} \end{cases}$$

注意到，对于序列的前三项有：

- $$a + b = 1 + (a + (b - 1))$$
- $$a \cdot b = a + (a \times (b - 1))$$
- $$a ^ b = a \cdot (a ^ {(b - 1)})$$

通过这样的递归能够定义出高阶运算，从而输入很小的数就可以产生非常大的数。

其实，某一超运算就是一种基于低一阶超运算而进行数的复合的方法。我们可以以加法、乘法与幂的概念为例来说明。加法运算就是将指定次数的1加到原本的数上从而得到最终的结果（如2+3是将1三次加到2上），乘法运算就是将指定次数的某数通加（如$2 \times 3$就是3个2相加），幂运算则是将指定次数的某数通乘（如$2^3$就是3个2相乘）。

## 实例

下表列出了前七个超运算：

n｜运算｜定义｜名称｜定义域

0｜$1+b$｜${ 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }$｜超-0运算、后继函数｜任意b

1｜$a+b$｜${ a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }$｜超-1运算、加法｜任意

2｜$a \cdot b$｜${ {\underbrace{a + a + a + \cdots + a}} \atop{b} }$｜超-2运算、乘法｜任意

3｜$a[3]b=a^b$｜${ {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b} }$｜超-3运算、幂｜$a > 0$，b为实数；或$a \not= 0$，b为整数（某些情况下可扩展为复数）

4｜$a[4]b={^{b}a}$｜${ {\underbrace{a[3](a[3](a[3](\cdots[3](a[3](a[3]a))\cdots)))}} \atop{b} }$｜超-4运算、迭代幂次（英文：tetration）｜$a > 0, b \ge -1$且为整数（某些情况下可扩展）

5｜$a[5]b={_{b}a}$｜${ {\underbrace{a[4](a[4](a[4](\cdots[4](a[4](a[4]a))\cdots)))}} \atop{b} }$｜超-5运算、五级运算（英文：pentation）｜a和b都为整数，且$a > 0, b \ge 0$

6｜$a [6] b$｜${ {\underbrace{a[5](a[5](a[5](\cdots[5](a[5](a[5]a))\cdots)))}} \atop{b} }$｜超-6运算（英文：hexation）｜a和b都为整数，且$a > 0, b \ge 0$

n｜$a [n] b$｜${ {\underbrace{a[n-1](a[n-1](a[n-1](\cdots[n-1](a[n-1](a[n-1]a))\cdots)))}} \atop{b} }$｜超-n运算（英文：hyper-n）｜a和b都为整数，且$a > 0, b \ge 0$

## 历史

1914年，阿尔伯特·贝内特（Albert Bennett）最早提出了超运算，他发展出了一套交换超运算（见下文）的理论。12年之后，威廉·阿克曼定义了函数$\phi(a, b, n)$，和超运算序列已经有了某种程度上的相似。最早的使用三个自变量的阿克曼函数使用了同样的递归法则，但有两点与现在的超运算不同。一是它定义了$n=0$时为加法、$n=1$时为乘法、$n=2$时为幂运算，二是由其对$\phi$初始条件的定义能得到$\phi(a, b, 3) = a [4] (b + 1)$，最后的运算结果与超运算不同。

1947年，鲁宾·古德斯坦提出现在所使用的超运算序列，只是那时他使用记号$G(n,a,b)$来表示，而非今天的$a [n] b$。在1947年的论文中，古德斯坦还引进了幂运算之后超运算的英文名称，即tetration、pentation、hexation等。

## 符号表示

下表列出了曾用来表示超运算的各种符号表示法：

名称｜符号表示｜注解

高德纳箭号表示法｜$a \uparrow^{n-2} b$｜高德纳使用（对于$n \ge 3$），也在相关参考书目中提及

古德斯坦表示法｜$G(n, a, b)$｜鲁宾·古德斯坦使用

初始阿克曼函数｜$A(a, b, n-1)$｜与超运算并不完全相同

现代阿克曼函数｜$A(n, b - 3) + 3 = 2 [n] b$｜和以2为底的超运算相同

南比尔表示法｜$a \otimes^{n-1} b$｜南比尔（K. K. Nambiar）使用（对于$n \ge 1$）

框表示法｜$a {\,\begin{array}{|c|}\hline{\!n\!}\\\hline\end{array}\,} b$｜鲁佐勃夫（C. A. Rubtsov）与罗莫里奥（G. F. Romerio）使用

上标表示法｜$a {}^{(n)} b$｜默纳福（Robert Munafo）使用

下标表示法｜$a {}_{(n)} b$｜默纳福用来表示低级超运算

方括号表示法｜$a[n]b$｜在一些在线论坛中使用，利于ASCII表示

康威链式箭号表示法｜$a \to b \to (n-2)$｜约翰·何顿·康威使用（对于$n \ge 3$）

### 从a开始的变体形式

1928年，威廉·阿克曼提出了一个三自变量的函数$\phi(a, b, n)$，后来发展为现有的两个自变量的阿克曼函数。初始的阿克曼函数与现在的超运算之间的区别更大，因为他当时使用了初始条件：对所有$n > 2$，有$\phi(a, 0, n) = a$。另外他还将$n = 0$指定为加法、$n = 1$为乘法、$n = 2$为幂。因而，幂运算及更高阶的运算就有了完全不同的结果。

n｜运算｜注释

0｜$F_0(a, b) = a + b$

1｜$F_1(a, b) = ab$

2｜$F_2(a, b) = a^b$

3｜$F_3(a, b) = a [4] (b + 1)$｜类似超-4运算，但其迭代函数比普通超-4运算更为复杂

4｜$F_4(a, b) = (x \mapsto a [4] (x + 1))^b(a)$｜不要与超-5运算相混淆

路莎·彼得（Rózsa Péter）还曾用$A(0, b) = 2 b + 1$作初始条件，但无法形成一个超运算等级。

### 从0开始的变体形式

1984年，C.W.克莱恩肖（C. W. Clenshaw）和F.W.J.奥立弗（F. W. J. Olver）开始讨论如何使用超运算以防止计算机浮点数溢出。此后，很多人都开始对于超运算在浮点数表示中的应用产生兴趣。在探讨超-4运算时，克莱恩肖等人曾令$F_n(a, 0) = 0$作为初始条件，这就产生了又一个超运算等级。

n｜运算｜注释

1｜$F_1(a, b) = a + b$

2｜$F_2(a, b) = ab = e^{\ln(a) + \ln(b)}$

3｜$F_3(a, b) = a^b = e^{b\ln(a)}$

4｜$F_4(a, b) = a [4] (b - 1)$｜类似超-4运算，但其迭代函数比普通超-4运算更为复杂

5｜$F_5(a, b) = (x \mapsto a [4] (x - 1))^b(0)$｜不要与超-5运算相混淆

### 交换超运算

1914年阿尔伯特·贝内特提出了超运算，很可能是关于超运算最早的尝试。交换超运算通过以下递归法则定义：

$$F_{n+1}(a, b) = \exp(F_n(\ln(a), \ln(b)))$$

由于a和b的对称性，意味着所有的超运算都是可交换的。但由于序列并不包括幂运算，因此也就不能成为一个超运算等级。

n｜运算｜注释

0｜$F_0(a, b) = \ln(e^{a} + e^{b})$

1｜$F_1(a, b) = a + b = \ln(e^{a}e^{b})$

2｜$F_2(a, b) = ab = e^{\ln(a) + \ln(b)}$｜由对数性质而来

3｜$F_3(a, b) = e^{\ln(a)\ln(b)}$｜幂运算的可交换形式

4｜$F_4(a, b) = e^{e^{\ln(\ln(a))\ln(\ln(b))}}$｜不要与超-4运算相混淆

### 均衡超运算

均衡超运算于1991年首先由克莱门特·弗拉皮耶（Clément Frappier）提出，这种超运算是基于函数$x^x$的，因而与斯坦豪斯-莫泽表示法（Steinhaus-Moser notation）有关。均衡超运算的递归法则是

$$F_{n+1}(a, b) = (x \to F_n(x, x))^{\log_2(b)}(a)$$

n｜运算｜注释

0｜不存在

1｜$F_1(a, b) = a + b$

2｜$F_2(a, b) = ab = a 2^{\log_2(b)}$

3｜$F_3(a, b) = a^b = a^{2^{\log_2(b)}}$｜就是幂运算

4｜$F_4(a, b) = (x \to x^x)^{\log_2(b)}(a)$｜不要与超-4运算相混淆

### 低级超运算

还有一种变化形式的特点是从左到右的顺序进行求值，即：

- $$a+b = (a+(b-1))+1$$
- $$a\times b = (a\times (b-1))+a$$
- $$a^b = (a^{(b-1)})\times a$$

令（通过°或下标）$a_{(n+1)}b = (a_{(n+1)}(b-1))_{(n)}a$，有初始条件$a_{(1)}b = a+b, a _ {(2)} 0 = 0$，且对所有$n>2$有$a _ {(n)} 0 = 1$。

这样所产生的一个问题是，在4阶时它就与通常的定义不同：$a_{(4)}b = a^{(a^{(b-1)})}$。出现这一问题的原因在于加法和乘法运算有一种称为结合律的对称性，但这在幂运算上并不成立。由于通过这种超运算所得到的结果在3阶以上都比普通的超运算更小，因而把这种超运算称为低级超运算。

n｜运算｜注释

0｜$a + 1$｜后继函数

1｜$F_1(a, b) = a + b$

2｜$F_2(a, b) = ab$

3｜$F_3(a, b) = a^b$｜幂运算

4｜$F_4(a, b) = a^{a^{(b-1)}}$｜不要与超-4运算相混淆

5｜$F_5(a, b) = (x \to x^{x^{(a-1)}})^{b-1}(a)$｜不要与超-5运算相混淆

### 其他变体

<image>

在取不同的初始条件或不同的递归法则时，就会产生不同的运算。一些数学家扩展出了超运算的许多变体。

通常，超运算等级（hyperoperation hierarchy）$(S,\,I,\,F)$是一个以集合$I$为索引集、基于集合$S$的二元运算族$(F_n)_{n \in I}$。对于$i, j, k \in I$，有：

- $F_i(a, b) = a + b$（加法）
- $F_j(a, b) = ab$（乘法）
- $F_k(a, b) = a^b$（幂）

如果不满足最后一个条件的话，就能将交换超运算包括在内。当然，也可以明确地定义每一个超运算，但这就超出了我们讨论的范围。大多数的变体形式只包含了对于后继函数（即加法）的定义，而乘法则由递归法则来进行定义。由于这属于对超运算等级的定义，而非等级本身的性质，很难给出形式上的定义。

对于超运算，除了古德斯坦给出的定义外，还有很多其他可能性。如果对$F_n(a, 0)$和$F_n(a, 1)$采用不同的初始条件，则产生的超运算在比幂运算更高阶时就会有不同的结果。现今的超运算定义的条件包括对所有$n \ge 3$有$F_n(a, 0) = 1$，而在其他形式中也有$F_n(a, 0) = a$或$F_n(a, 0) = 0$的情况。

关于超运算的一个未解决问题是超运算等级$(\mathbb{N}, \mathbb{N}, F)$是否能推广到$(\mathbb{R}, \mathbb{R}, F)$甚至$(\mathbb{C}, \mathbb{C}, F)$，以及$(\mathbb{C}, F_n)$是否能成为一个拟群。

## 使用超运算的记数系统

Q1191771使用超运算序列定义了一套能表达非负整数的记数系统。