查看“超运算”的源代码

'''超運算序列'''是[[数学]]中一种[[二元运算]]的[[序列]]，前三[[表示式|项]]分别为[[加法]]、[[乘法]]、[[幂]]，一般來說，除了序列中第一項的加法運算之外，序列中每一項的運算都是重複的前一項的運算（例如乘法是重複的加法：<math>a \cdot b = \underbrace{a + a + a + \cdots + a}_b</math>，冪是重複的乘法：<math>a^b = \underbrace{a \cdot a \cdot a \cdot \ldots \cdot a}_b</math>）。这些运算通称为'''超运算'''（或稱為'''hyper運算符'''）。序列中的第''n''项称为'''超-''n''运算'''或'''第''n''級的超運算'''，其符號為'''[''n'']'''。英文則由{{en-link|鲁賓·古德斯坦|Reuben Goodstein}}命名，當''n''≥4時，由''n''的[[希腊语]][[前缀]]加上[[后缀]]-ation组成（例如[[超-4运算]]称为tetration，{{le|超-5运算|Pentation}}称为pentation）。<ref name=goodstein>{{cite journal 
  | author= R. L. Goodstein
  | title= Transfinite Ordinals in Recursive Number Theory 
  | journal= Journal of Symbolic Logic
  | volume= 12
  | issue= 4
  | pages= 123–129 
  | url= http://www.jstor.org/stable/2266486
  | accessdate=2009-04-17 
  | doi= 10.2307/2266486|date=Dec  1947}}</ref>當''n''≥3 時，使用[[高德纳箭号表示法]]可将超-''n''运算的符號表示为(''n''-2)个箭头。

超运算可通过[[递归]]进行定义，對於所有[[正整數]]''a''，正整數''b''和正整數''n''：

:<math>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 ))</math>

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

== 定义 ==
超运算序列是定义在[[自然数]]集<math>\mathbb{N}</math>上的一个序列，记为<math>H_n</math>。前几项为[[加法]]（n=1）、[[乘法]]（n=2）和[[幂]]（n=3）。高阶超运算的参数与幂运算相似，<ref name=romerioTerms>
{{cite web 
| author= G. F. Romerio
| title= Hyperoperations Terminology
| url= http://math.eretrandre.org/tetrationforum/attachment.php?aid=208
| publisher= [http://math.eretrandre.org/tetrationforum/ Tetration Forum]
| date= 2008-01-21
| accessdate=2009-04-21}}</ref>即a称为底数，b称为指数（或称超指数<ref name=galidakis>{{cite web
 |author=I. N. Galidakis 
 |title=Mathematics 
 |url=http://ioannis.virtualcomposer2000.com/math/index.html 
 |date=2003 
 |accessdate=2009-04-17 
 |deadurl=yes 
 |archiveurl=https://web.archive.org/web/20090420132250/http://ioannis.virtualcomposer2000.com/math/index.html 
 |archivedate=2009-04-20 
}}</ref>），而n则称为阶数。

用[[高德纳箭号表示法]]可以将超运算定义为
:<math> 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}</math>

注意到，对于序列的前三项有：
* <math>a + b = 1 + (a + (b - 1))</math>
* <math>a \cdot b = a + (a \times (b - 1))</math>
* <math>a ^ b = a \cdot (a ^ {(b - 1)})</math>

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

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

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

{| class="wikitable"
|-
! ''n''
! 运算
! 定义
! 名称
! 定义域
|-
! 0
| <math>1 + b</math>
| <math>{ 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }</math>
| 超-0运算、[[原始递归函数#定义|后继函数]]
| 任意b
|-
! 1
| <math>a + b</math>
| <math>{ a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }</math>
| 超-1运算、[[加法]]
| 任意
|-
! 2
| <math>ab</math>
| <math>{ {\underbrace{a + a + a + \cdots + a}} \atop{b} }</math>
| 超-2运算、[[乘法]]
| 任意
|-
! 3
| <math>a [3] b = a^b</math>
| <math>{ {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b} }</math>
| 超-3运算、[[幂]]
| <math>a > 0</math>，b为实数；或<math>a \not= 0</math>，b为整数（某些情况下可扩展为复数）
|-
! 4
| <math>a [4] b</math>
| <math>{ {\underbrace{a [3] a [3] a [3] \cdots [3] a}} \atop{b} }</math>
| 超-4运算、[[迭代冪次]]（英文：tetration）
| <math>a > 0, b \ge -1</math>且为整数（某些情况下可扩展）
|-
! 5
| <math>a [5] b</math>
| <math>{ {\underbrace{a [4] a [4] a [4] \cdots [4] a}} \atop{b} }</math>
| 超-5运算（英文：pentation）
| a和b都为整数，且<math>a > 0, b \ge 0</math>
|-
! 6
| <math>a [6] b</math>
| <math>{ {\underbrace{a [5] a [5] a [5] \cdots [5] a}} \atop{b} }</math>
| 超-6运算（英文：hexation）
| a和b都为整数，且<math>a > 0, b \ge 0</math>
|-
! n
| <math>a [n] b</math>
| <math>{ {\underbrace{a [n-1] a [n-1] a [n-1] \cdots [n-1] a}} \atop{b} }</math>
| 超-n运算（英文：hyper-n）
| a和b都为整数，且<math>a > 0, b \ge 0</math>
|}

== 历史 ==
1914年，阿尔伯特·贝内特（Albert Bennett）最早提出了超运算，他发展出了一套交换超运算（[[#交换超运算|见下文]]）的理论。<ref name=bennett>{{cite journal 
  | author= Albert A. Bennett
  | title= Note on an Operation of the Third Grade 
  | journal= Annals of Mathematics, Second Series
  | volume= 17
  | issue= 2
  | pages= 74–75
  | url= http://www.jstor.org/stable/2007124
  | accessdate=2009-04-17|date=Dec  1915}}</ref>12年之后，[[威廉·阿克曼]]定义了函数<math>\phi(a, b, n)</math><ref name=ackOrig>{{cite journal 
| author=Wilhelm Ackermann 
| journal=Mathematische Annalen 
| title=''Zum Hilbertschen Aufbau der reellen Zahlen'' 
| year=1928 | volume=99 | pages=118–133 
| doi=10.1007/BF01459088}}</ref>，和超运算序列已经有了某种程度上的相似。最早的使用三个自变量的[[阿克曼函数]]使用了同样的递归法则，但有两点与现在的超运算不同。一是它定义了<math>n=0</math>时为加法、<math>n=1</math>时为乘法、<math>n=2</math>时为幂运算，二是由其对<math>\phi</math>初始条件的定义能得到<math>\phi(a, b, 3) = a [4] (b + 1)</math>，最后的运算结果与超运算不同。<ref name=black>{{cite web
 |author       = Paul E. Black
 |title        = Ackermann's function
 |url          = http://www.itl.nist.gov/div897/sqg/dads/HTML/ackermann.html
 |work         = [http://www.itl.nist.gov/div897/sqg/dads/ Dictionary of Algorithms and Data Structures]
 |publisher    = U.S. National Institute of Standards and Technology (NIST)
 |date         = 2009-03-16
 |accessdate   = 2009-04-17
 |archive-url  = https://web.archive.org/web/20090422062535/http://www.itl.nist.gov/div897/sqg/dads/HTML/ackermann.html
 |archive-date = 2009-04-22
 |dead-url     = yes
}}</ref><ref>{{cite web 
| author= Robert Munafo
| title= Versions of Ackermann's Function
| url= http://www.mrob.com/pub/math/ln-2deep.html
| work= Large Numbers at MROB
| date= 1999-11-03
| accessdate=2009-04-17}}</ref><ref>{{cite web 
| author= J. Cowles and T. Bailey
| title= Several Versions of Ackermann's Function
| url= http://www.cs.utexas.edu/users/boyer/ftp/nqthm/nqthm-1992/examples/basic/peter.events
| publisher= Dept. of Computer Science, University of Wyoming, Laramie, WY
| date= 1988-09-30
| accessdate=2009-04-17}}</ref>

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

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

{| class="wikitable"
|-
! 名称
! 符号表示
! 注解
|-
| [[高德纳箭号表示法]]
| <math>a \uparrow^{n-2} b</math>
| [[高德纳]]使用（對於<math>n \ge 3</math>）<ref name=knuth>{{cite journal 
| author= Donald E. Knuth
| title= Mathematics and Computer Science: Coping with Finiteness 
| journal= Science
| volume= 194
| issue= 4271
| pages= 1235–1242
| url= http://www.sciencemag.org/cgi/content/abstract/194/4271/1235
| accessdate=2009-04-21 
| doi= 10.1126/science.194.4271.1235 
| pmid= 17797067|date=Dec  1976}}</ref>，也在相关参考书目中提及<ref>{{cite book
| author = Daniel Zwillinger
| title = CRC standard mathematical tables and formulae, 31st Edition
| publisher = CRC Press
| year = 2002
| pages= 4
| isbn = 1584882913 }}</ref><ref>{{cite book
| author = Eric W. Weisstein
| title = CRC concise encyclopedia of mathematics, 2nd Edition
| publisher = CRC Press
| year = 2003
| pages= 127–128
| isbn = 1584883472 }}</ref>
|-
| 古德斯坦表示法
| <math>G(n, a, b)</math>
| [[鲁宾·古德斯坦]]使用<ref name=goodstein />
|-
| 初始[[阿克曼函数]]
| <math>A(a, b, n-1)</math>
| 与超运算并不完全相同
|-
| 现代[[阿克曼函数]]
| <math>A(n, b - 3) + 3 = 2 [n] b</math>
| 和以2为底的超运算相同
|-
| 南比尔表示法
| <math>a \otimes^{n-1} b</math>
| 南比尔（K. K. Nambiar）使用（對於<math>n \ge 1</math>）<ref>{{cite journal 
| author= K. K. Nambiar
| title= Ackermann Functions and Transfinite Ordinals
| journal= Applied Mathematics Letters
| year= 1995
| volume= 8
| issue= 6
| pages= 51–53
| url= http://www.sciencemag.org/cgi/content/abstract/194/4271/1235
| accessdate=2009-04-21 
| doi= 10.1016/0893-9659(95)00084-4}}</ref>
|-
| 框表示法
| <math>a {\,\begin{array}{|c|}\hline{\!n\!}\\\hline\end{array}\,} b</math>
| 鲁佐勃夫（C. A. Rubtsov）与罗莫里奥（G. F. Romerio）使用<ref name=romerioAck>{{cite web 
  | author= C. A. Rubtsov and G. F. Romerio
  | title= Ackermann's Function and New Arithmetical Operation
  | url= http://forum.wolframscience.com/showthread.php?s=&threadid=956
  | date= 2005-12
  | accessdate=2009-04-17}}</ref><ref name=romerioTerms/>
|-
| 上标表示法
| <math>a {}^{(n)} b</math>
| 默纳福（Robert Munafo）使用<ref name=munafo>{{cite web 
  | author= Robert Munafo
  | title= Inventing New Operators and Functions
  | url= http://www.mrob.com/pub/math/largenum-3.html
  | work= Large Numbers at MROB
  | date= 1999-11
  | accessdate=2009-04-17}}</ref>
|-
| 下标表示法
| <math>a {}_{(n)} b</math>
| 默纳福用来表示低级超运算<ref name=munafo/>
|-
| 方括号表示法
| <math>a[n]b</math>
| 在一些在线论坛中使用，利于[[ASCII]]表示
|-
| [[康威鏈式箭號表示法]]
| <math>a \to b \to (n-2) </math>
| [[約翰·何頓·康威]]使用（對於<math>n \ge 3</math>）
|}

== 一般化 ==
[[File:Hyperoperation 3 and 3 with real number.svg|thumb|超運算等級推廣至[[實數]]的可能結果，當<math>F_n(3, 3)</math>的n為實數時。<sup>[<nowiki/>[[Template:来源请求|來源請求]]<nowiki>]</nowiki></sup>]]
在取不同的初始条件或不同的递归法则时，就会产生不同的运算。一些数学家扩展出了超运算的许多变体。

通常，超运算等级（hyperoperation hierarchy）<math>(S,\,I,\,F)</math>是一个以集合<math>I</math>为[[索引集]]、基于集合<math>S</math>的[[二元运算]][[加标族|族]]<math>(F_n)_{n \in I}</math>。对于<math>i, j, k \in I</math>，有：
* <math>F_i(a, b) = a + b</math>（加法）
* <math>F_j(a, b) = ab</math>（乘法）
* <math>F_k(a, b) = a^b</math>（幂）

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

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

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

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

{| class="wikitable"
|-
! ''n''
! 运算
! 注释
|-
! 0
| <math>F_0(a, b) = a + b</math>
|
|-
! 1
| <math>F_1(a, b) = ab</math>
|
|-
! 2
| <math>F_2(a, b) = a^b</math>
|
|-
! 3
| <math>F_3(a, b) = a [4] (b + 1)</math>
| 类似超-4运算，但其[[迭代函数]]比普通超-4运算更为复杂
|-
! 4
| <math>F_4(a, b) = (x \mapsto a [4] (x + 1))^b(a)</math>
| 不要与超-5运算相混淆
|}

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

=== 从0开始的变体形式 ===
1984年，C.W.克莱恩肖（C. W. Clenshaw）和F.W.J.奥立弗（F. W. J. Olver）开始讨论如何使用超运算以防止计算机[[浮点数]]溢出。<ref name=clenshawolver>{{cite journal 
| author= C.W. Clenshaw and F.W.J. Olver
| title= Beyond floating point
| journal= Journal of the ACM
| volume= 31
| issue= 2
| pages= 319–328
| url= http://portal.acm.org/citation.cfm?id=62.322429
| accessdate=2009-04-21 
| doi= 10.1145/62.322429|date=Apr  1984}}</ref>此后，很多人<ref name=holmes>{{cite journal 
| author= W. N. Holmes
| title= Composite Arithmetic: Proposal for a New Standard
| journal= Computer
| volume= 30
| issue= 3
| pages= 65–73
| url= http://portal.acm.org/citation.cfm?id=620661
| accessdate=2009-04-21 
| doi= 10.1109/2.573666|date=Mar  1997}}</ref><ref>{{cite web
| author= R. Zimmermann
| title= Computer Arithmetic: Principles, Architectures, and VLSI Design
| url= http://www.iis.ee.ethz.ch/~zimmi/publications/comp_arith_notes.pdf
| publisher= Lecture notes, Integrated Systems Laboratory, ETH Zürich
| date= 1997
| accessdate= 2009-04-17
| archive-url= https://web.archive.org/web/20130817164526/http://www.iis.ee.ethz.ch/~zimmi/publications/comp_arith_notes.pdf
| archive-date= 2013-08-17
| dead-url= yes
}}</ref><ref>{{cite web 
| author= T. Pinkiewicz and N. Holmes and T. Jamil
| title= Design of a composite arithmetic unit for rational numbers
| url= http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=845571
| publisher= Proceedings of the IEEE
| date= 2000
| pages= 245–252
| accessdate=2009-04-17}}</ref>都开始对于超运算在浮点数表示中的应用产生兴趣。在探讨超-4运算时，克莱恩肖等人曾令<math>F_n(a, 0) = 0</math>作为初始条件，这就产生了又一个超运算等级。

{| class="wikitable"
|-
! ''n''
! 运算
! 注释
|-
! 1
| <math>F_1(a, b) = a + b</math>
|
|-
! 2
| <math>F_2(a, b) = ab = e^{\ln(a) + \ln(b)}</math>
|
|-
! 3
| <math>F_3(a, b) = a^b = e^{b\ln(a)}
</math>
|
|-
! 4
| <math>F_4(a, b) = a [4] (b - 1)</math>
| 类似超-4运算，但其[[迭代函数]]比普通超-4运算更为复杂
|-
! 5
| <math>F_5(a, b) = (x \mapsto a [4] (x - 1))^b(0)</math>
| 不要与超-5运算相混淆
|}

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

:<math>F_{n+1}(a, b) = \exp(F_n(\ln(a), \ln(b)))</math>

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

{| class="wikitable"
|-
! ''n''
! 运算
! 注释
|-
! 0
| <math>F_0(a, b) = \ln(e^{a} + e^{b})</math>
|
|-
! 1
| <math>F_1(a, b) = a + b = \ln(e^{a}e^{b})</math>
|
|-
! 2
| <math>F_2(a, b) = ab = e^{\ln(a) + \ln(b)}</math>
| 由[[对数]]性质而来
|-
! 3
| <math>F_3(a, b) = e^{\ln(a)\ln(b)}</math>
| 幂运算的可交换形式
|-
! 4
| <math>F_4(a, b) = e^{e^{\ln(\ln(a))\ln(\ln(b))}}</math>
| 不要与超-4运算相混淆
|}

=== 均衡超运算 ===
均衡超运算于1991年首先由克莱门特·弗拉皮耶（Clément Frappier）提出<ref name=frappier>{{cite journal 
| author= C. Frappier
| title= Iterations of a kind of exponentials
| journal= Fibonacci Quarterly
| year= 1991
| volume= 29
| issue= 4
| pages= 351–361}}</ref>，这种超运算是基于函数<math>x^x</math>的，因而与[[斯坦豪斯-莫泽表示法]]（Steinhaus-Moser notation）有关。均衡超运算的递归法则是

:<math>F_{n+1}(a, b) = (x \to F_n(x, x))^{\log_2(b)}(a)</math>

{| class="wikitable"
|-
! ''n''
! 运算
! 注释
|-
! 0
| 
| 不存在
|-
! 1
| <math>F_1(a, b) = a + b</math>
|
|-
! 2
| <math>F_2(a, b) = ab = a 2^{\log_2(b)}</math>
|
|-
! 3
| <math>F_3(a, b) = a^b = a^{2^{\log_2(b)}}</math>
| 就是幂运算
|-
! 4
| <math>F_4(a, b) = (x \to x^x)^{\log_2(b)}(a)</math>
| 不要与超-4运算相混淆
|}

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

* <math>a+b = (a+(b-1))+1</math>
* <math>a\times b = (a\times (b-1))+a</math>
* <math>a^b = (a^{(b-1)})\times a</math>

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

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

{| class="wikitable"
|-
! ''n''
! 运算
! 注释
|-
! 0
| <math>a + 1</math>
| 后继函数
|-
! 1
| <math>F_1(a, b) = a + b</math>
| 
|-
! 2
| <math>F_2(a, b) = ab</math>
|
|-
! 3
| <math>F_3(a, b) = a^b</math>
| 幂运算
|-
! 4
| <math>F_4(a, b) = a^{a^{(b-1)}}</math>
| 不要与超-4运算相混淆
|-
! 5
| <math>F_5(a, b) = (x \to x^{x^{(a-1)}})^{b-1}(a)</math>
| 不要与超-5运算相混淆
|}

== 参考文献 ==
{{Reflist}}

{{-}}
{{大数}}

[[Category:二元运算]]
[[Category:超运算| ]]
[[Category:算术]]
[[Category:大数]]