超运算

维基百科,自由的百科全书
跳转至: 导航搜索

超运算序列,是数学中一种二元运算的序列,前几项分别为加法乘法,这些运算通称为超运算(或稱為hyper運算符)。序列的第n项称为超-n运算。英文则由鲁宾·古德斯坦(Reuben Goodstein)命名,由n的希腊语前缀加上后缀-ation组成(例如超-4运算称为tetration,超-5运算称为pentation)。[1]使用高德纳箭号表示法可将超运算算子表示为(n-2)个箭头。

超运算可通过递归进行定义,使用阿克曼函数的递归法则可以得到定义(部分):

a \uparrow^n b = a \uparrow^{n-1} \left(a \uparrow^n (b-1)\right).

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

定义[编辑]

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

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

 H_n(a, b) = a \uparrow^{n-2} b = 
   \begin{cases}
    b + 1   \\
    a  \\
    0  \\
    1  \\
    H_{n-1}(a, H_n(a, b - 1)) 
   \end{cases} \quad 如果 n = 0
如果  n = 1, b = 0
如果  n = 2, b = 0
如果  n \ge 3, b = 0
其它情况。

注意到,对于序列的前三项有:

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

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

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

实例[编辑]

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

n 运算 定义 名称 定义域
0 b + 1 { 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } 超-0运算、后继函数 任意b
1 a + b { a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } 超-1运算、加法 任意
2 ab { {\underbrace{a + a + a + \cdots + a}} \atop{b} } 超-2运算、乘法 任意
3 a \uparrow 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 \uparrow\uparrow b { {\underbrace{a \uparrow a \uparrow a \uparrow \cdots \uparrow a}} \atop{b} } 超-4运算、迭代冪次(英文:tetration) a > 0, b \ge -1且为整数(某些情况下可扩展)
5 a \uparrow\uparrow\uparrow b or a \uparrow^3 b { {\underbrace{a \uparrow\uparrow a \uparrow\uparrow \cdots \uparrow\uparrow a}} \atop{b} } 超-5运算(英文:pentation) a和b都为整数,且a > 0, b \ge 0
6 a \uparrow^4 b { {\underbrace{a \uparrow^3 a \uparrow^3 \cdots \uparrow^3 a}} \atop{b} } 超-6运算(英文:hexation) a和b都为整数,且a > 0, b \ge 0

以2為底的情形[编辑]

H_m(2,n)的值:

m\n 0 1 2 3 4 5 6 ...
0 1 2 3 4 5 6 7 ...
1 2 3 4 5 6 7 8 ...
2 0 2 4 6 8 10 12 ...
3 1 2 4 8 16 32 64 ...
4 1 2 4 16 65536 265536 2265536 ...
5 1 2 4 65536 2222...2(共65536個2) ...
6 1 2 4 2222...2(共65536個2) ...
... ...

历史[编辑]

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

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

符号表示[编辑]

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

名称 符号表示 注解
标准高德纳箭号表示法 a \uparrow^{n-2} b = H_n(a, b) 高德纳使用[9],也在相关参考书目中提及[10][11]
古德斯坦表示法 G(n, a, b) 鲁宾·古德斯坦使用[1]
初始阿克曼函数 A(a, b, n-1) = H_n(a, b) 与超运算并不完全相同
现代阿克曼函数 A(n, b - 3) + 3 = H_n(2, b) 以2为底时与超运算相同
南比尔表示法 a \otimes^n b 南比尔(K. K. Nambiar)使用[12]
框表示法 a {\,\begin{array}{|c|}\hline{\!n\!}\\\hline\end{array}\,} b 鲁佐勃夫(C. A. Rubtsov)与罗莫里奥(G. F. Romerio)[13][2]
上标表示法 a {}^{(n)} b 默纳福(Robert Munafo)使用[14]
下标表示法 a {}_{(n)} b 默纳福用来表示低级超运算[14]
方括号表示法 a[n]b 在一些在线论坛中使用,利于ASCII表示

一般化[编辑]

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

通常,超运算等级(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 3F_n(a, 0) = 1,而在其他形式中也有F_n(a, 0) = aF_n(a, 0) = 0的情况。

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

从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 \uparrow\uparrow (b + 1) 类似超-4运算,但其迭代函数比普通超-4运算更为复杂
4 F_4(a, b) = (x \to a \uparrow\uparrow (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)开始讨论如何使用超运算以防止计算机浮点数溢出。[15]此后,很多人[16][17][18]都开始对于超运算在浮点数表示中的应用产生兴趣。在探讨超-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
4 F_4(a, b) = a \uparrow\uparrow (b - 1) 类似超-4运算,但其迭代函数比普通超-4运算更为复杂
5 F_5(a, b) = (x \to a \uparrow\uparrow (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
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)提出[19],这种超运算是基于函数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>2a _ {(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运算相混淆

参考文献[编辑]

  1. ^ 1.0 1.1 1.2 R. L. Goodstein. Transfinite Ordinals in Recursive Number Theory. Journal of Symbolic Logic. 1947.Dec., 12 (4): 123–129 [2009-04-17]. doi:10.2307/2266486. 
  2. ^ 2.0 2.1 G. F. Romerio. Hyperoperations Terminology. Tetration Forum. 2008-01-21 [2009-04-21]. 
  3. ^ I. N. Galidakis. Mathematics. 2003 [2009-04-17]. 
  4. ^ Albert A. Bennett. Note on an Operation of the Third Grade. Annals of Mathematics, Second Series. 1915.Dec., 17 (2): 74–75 [2009-04-17]. 
  5. ^ Wilhelm Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen. 1928, 99: 118–133. doi:10.1007/BF01459088. 
  6. ^ Paul E. Black. Ackermann's function. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). 2009-03-16 [2009-04-17]. 
  7. ^ Robert Munafo. Versions of Ackermann's Function. Large Numbers at MROB. 1999-11-03 [2009-04-17]. 
  8. ^ J. Cowles and T. Bailey. Several Versions of Ackermann's Function. Dept. of Computer Science, University of Wyoming, Laramie, WY. 1988-09-30 [2009-04-17]. 
  9. ^ Donald E. Knuth. Mathematics and Computer Science: Coping with Finiteness. Science. 1976.Dec., 194 (4271): 1235–1242 [2009-04-21]. doi:10.1126/science.194.4271.1235. PMID 17797067. 
  10. ^ Daniel Zwillinger. CRC standard mathematical tables and formulae, 31st Edition. CRC Press. 2002: 4. ISBN 1584882913. 
  11. ^ Eric W. Weisstein. CRC concise encyclopedia of mathematics, 2nd Edition. CRC Press. 2003: 127–128. ISBN 1584883472. 
  12. ^ K. K. Nambiar. Ackermann Functions and Transfinite Ordinals. Applied Mathematics Letters. 1995, 8 (6): 51–53 [2009-04-21]. doi:10.1016/0893-9659(95)00084-4. 
  13. ^ C. A. Rubtsov and G. F. Romerio. Ackermann's Function and New Arithmetical Operation. 2005-12 [2009-04-17]. 
  14. ^ 14.0 14.1 Robert Munafo. Inventing New Operators and Functions. Large Numbers at MROB. 1999-11 [2009-04-17]. 
  15. ^ C.W. Clenshaw and F.W.J. Olver. Beyond floating point. Journal of the ACM. 1984.Apr., 31 (2): 319–328 [2009-04-21]. doi:10.1145/62.322429. 
  16. ^ W. N. Holmes. Composite Arithmetic: Proposal for a New Standard. Computer. 1997.Mar., 30 (3): 65–73 [2009-04-21]. doi:10.1109/2.573666. 
  17. ^ R. Zimmermann. Computer Arithmetic: Principles, Architectures, and VLSI Design. Lecture notes, Integrated Systems Laboratory, ETH Zürich. 1997 [2009-04-17]. 
  18. ^ T. Pinkiewicz and N. Holmes and T. Jamil. Design of a composite arithmetic unit for rational numbers. Proceedings of the IEEE. 245–252. 2000 [2009-04-17]. 
  19. ^ C. Frappier. Iterations of a kind of exponentials. Fibonacci Quarterly. 1991, 29 (4): 351–361.