超運算
二元運算序列 / 維基百科,自由的 encyclopedia
超運算序列是數學中一種二元運算的序列,前三項分別為加法、乘法、冪,一般來說,除了序列中第一項的加法運算之外,序列中每一項的運算都是重複的前一項的運算(例如乘法是重複的加法:,冪是重複的乘法:
)。這些運算通稱為超運算(或稱為hyper運算符)。序列中的第n項稱為超-n運算或第n級的超運算,其符號為[n]。英文則由魯賓·古德斯坦(英語:Reuben Goodstein)命名,當n≥4時,由n的希臘語前綴加上後綴-ation組成(例如超-4運算稱為tetration,超-5運算稱為pentation(英語:pentation))。[1]當n≥3 時,使用高德納箭號表示法可將超-n運算的符號表示為(n-2)個箭頭。
超運算可通過遞歸進行定義,對於所有正整數a,正整數b和正整數n:
除這一最常見的定義之外,超運算還有其他的變體。(見下文)
定義
超運算序列是定義在自然數集上的一個序列,記為
。前三項為加法(n=1)、乘法(n=2)和冪(n=3)。高階超運算的參數與冪運算相似,[2]即a稱為底數,b稱為指數(或稱超指數[3]),而n則稱為階數。
用高德納箭號表示法可以將超運算定義為
注意到,對於序列的前三項有:
通過這樣的遞歸能夠定義出高階運算,從而輸入很小的數就可以產生非常大的數。
其實,某一超運算就是一種基於低一階超運算而進行數的複合的方法。我們可以以加法、乘法與冪的概念為例來說明。加法運算就是將指定次數的1加到原本的數上從而得到最終的結果(如2+3是將1三次加到2上),乘法運算就是將指定次數的某數通加(如就是3個2相加),冪運算則是將指定次數的某數通乘(如
就是3個2相乘)。
實例
下表列出了前七個超運算:
n | 運算 | 定義 | 名稱 | 定義域 |
---|---|---|---|---|
0 | 超-0運算、後繼函數 | 任意b | ||
1 | 超-1運算、加法 | 任意 | ||
2 | 超-2運算、乘法 | 任意 | ||
3 | 超-3運算、冪 | |||
4 | 超-4運算、迭代冪次(英文:tetration) | |||
5 | 超-5運算 五級運算(英文:pentation) | a和b都為整數,且 | ||
6 | 超-6運算(英文:hexation) | a和b都為整數,且 | ||
n | 超-n運算(英文:hyper-n) | a和b都為整數,且 |
歷史
1914年,阿爾伯特·貝內特(Albert Bennett)最早提出了超運算,他發展出了一套交換超運算(見下文)的理論。[4]12年之後,威廉·阿克曼定義了函數[5],和超運算序列已經有了某種程度上的相似。最早的使用三個自變量的阿克曼函數使用了同樣的遞歸法則,但有兩點與現在的超運算不同。一是它定義了
時為加法、
時為乘法、
時為冪運算,二是由其對
初始條件的定義能得到
,最後的運算結果與超運算不同。[6][7][8]
1947年,魯賓·古德斯坦[1]提出現在所使用的超運算序列,只是那時他使用記號來表示,而非今天的
。在1947年的論文中,古德斯坦還引進了冪運算之後超運算的英文名稱,即tetration、pentation、hexation等。
符號表示
下表列出了曾用來表示超運算的各種符號表示法:
名稱 | 符號表示 | 註解 |
---|---|---|
高德納箭號表示法 | 高德納使用(對於 | |
古德斯坦表示法 | 魯賓·古德斯坦使用[1] | |
初始阿克曼函數 | 與超運算並不完全相同 | |
現代阿克曼函數 | 和以2為底的超運算相同 | |
南比爾表示法 | 南比爾(K. K. Nambiar)使用(對於 | |
框表示法 | 魯佐勃夫(C. A. Rubtsov)與羅莫里奧(G. F. Romerio)使用[13][2] | |
上標表示法 | 默納福(Robert Munafo)使用[14] | |
下標表示法 | 默納福用來表示低級超運算[14] | |
方括號表示法 | 在一些在線論壇中使用,利於ASCII表示 | |
康威鏈式箭號表示法 | 約翰·何頓·康威使用(對於 |
從a開始的變體形式
1928年,威廉·阿克曼提出了一個三自變量的函數,後來發展為現有的兩個自變量的阿克曼函數。初始的阿克曼函數與現在的超運算之間的區別更大,因為他當時使用了初始條件:對所有
,有
。另外他還將
指定為加法、
為乘法、
為冪。因而,冪運算及更高階的運算就有了完全不同的結果。
路莎·彼得(Rózsa Péter)還曾用作初始條件,但無法形成一個超運算等級。
從0開始的變體形式
1984年,C.W.克萊恩肖(C. W. Clenshaw)和F.W.J.奧立弗(F. W. J. Olver)開始討論如何使用超運算以防止計算機浮點數溢出。[15]此後,很多人[16][17][18]都開始對於超運算在浮點數表示中的應用產生興趣。在探討超-4運算時,克萊恩肖等人曾令作為初始條件,這就產生了又一個超運算等級。
交換超運算
1914年阿爾伯特·貝內特提出了超運算,很可能是關於超運算最早的嘗試。交換超運算通過以下遞歸法則定義:
由於a和b的對稱性,意味着所有的超運算都是可交換的。但由於序列並不包括冪運算,因此也就不能成為一個超運算等級。
均衡超運算
均衡超運算於1991年首先由克萊門特·弗拉皮耶(Clément Frappier)提出[19],這種超運算是基於函數的,因而與斯坦豪斯-莫澤表示法(Steinhaus-Moser notation)有關。均衡超運算的遞歸法則是
n | 運算 | 註釋 |
---|---|---|
0 | 不存在 | |
1 | ||
2 | ||
3 | 就是冪運算 | |
4 | 不要與超-4運算相混淆 |
低級超運算
還有一種變化形式的特點是從左到右的順序進行求值,即:
令(通過°或下標),有初始條件
,且對所有
有
。
這樣所產生的一個問題是,在4階時它就與通常的定義不同:。出現這一問題的原因在於加法和乘法運算有一種稱為結合律的對稱性,但這在冪運算上並不成立。由於通過這種超運算所得到的結果在3階以上都比普通的超運算更小,因而把這種超運算稱為低級超運算。
n | 運算 | 註釋 |
---|---|---|
0 | 後繼函數 | |
1 | ||
2 | ||
3 | 冪運算 | |
4 | 不要與超-4運算相混淆 | |
5 | 不要與超-5運算相混淆 |
其他變體
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/Hyperoperation_3_and_3_with_real_number.svg/640px-Hyperoperation_3_and_3_with_real_number.svg.png)
在取不同的初始條件或不同的遞歸法則時,就會產生不同的運算。一些數學家擴展出了超運算的許多變體。
通常,超運算等級(hyperoperation hierarchy)是一個以集合
為索引集、基於集合
的二元運算族
。對於
,有:
(加法)
(乘法)
(冪)
如果不滿足最後一個條件的話,就能將交換超運算包括在內。當然,也可以明確地定義每一個超運算,但這就超出了我們討論的範圍。大多數的變體形式只包含了對於後繼函數(即加法)的定義,而乘法則由遞歸法則來進行定義。由於這屬於對超運算等級的定義,而非等級本身的性質,很難給出形式上的定義。
對於超運算,除了古德斯坦給出的定義外,還有很多其他可能性。如果對和
採用不同的初始條件,則產生的超運算在比冪運算更高階時就會有不同的結果。現今的超運算定義的條件包括對所有
有
,而在其他形式中也有
或
的情況。
關於超運算的一個未解決問題是超運算等級是否能推廣到
[21]:5甚至
,以及
是否能成為一個擬群。
使用超運算的記數系統
魯賓·古德斯坦(英語:Reuben Goodstein)使用超運算序列定義了一套能表達非負整數的記數系統[1]。
參考文獻
- R. L. Goodstein. Transfinite Ordinals in Recursive Number Theory. Journal of Symbolic Logic. Dec 1947, 12 (4): 123–129 [2009-04-17]. doi:10.2307/2266486. (原始內容存檔於2016-03-03).
- G. F. Romerio. Hyperoperations Terminology. Tetration Forum. 2008-01-21 [2009-04-21]. (原始內容存檔於2011-10-02). 外部連結存在於
|publisher=
(幫助) - I. N. Galidakis. Mathematics. 2003 [2009-04-17]. (原始內容存檔於2009-04-20).
- Albert A. Bennett. Note on an Operation of the Third Grade. Annals of Mathematics, Second Series. Dec 1915, 17 (2): 74–75 [2009-04-17]. (原始內容存檔於2016-09-17).
- Wilhelm Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen. 1928, 99: 118–133. doi:10.1007/BF01459088.
- 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]. (原始內容存檔於2009-04-22). 外部連結存在於
|work=
(幫助) - Robert Munafo. Versions of Ackermann's Function. Large Numbers at MROB. 1999-11-03 [2009-04-17]. (原始內容存檔於2008-12-21).
- 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]. (原始內容存檔於2008-10-04).
- Donald E. Knuth. Mathematics and Computer Science: Coping with Finiteness. Science. Dec 1976, 194 (4271): 1235–1242 [2009-04-21]. PMID 17797067. doi:10.1126/science.194.4271.1235. (原始內容存檔於2008-12-08).
- Daniel Zwillinger. CRC standard mathematical tables and formulae, 31st Edition. CRC Press. 2002: 4. ISBN 1584882913.
- Eric W. Weisstein. CRC concise encyclopedia of mathematics, 2nd Edition. CRC Press. 2003: 127–128. ISBN 1584883472.
- 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. (原始內容存檔於2008-12-08).
- C. A. Rubtsov and G. F. Romerio. Ackermann's Function and New Arithmetical Operation. 2005-12 [2009-04-17]. (原始內容存檔於2008-05-29).
- Robert Munafo. Inventing New Operators and Functions. Large Numbers at MROB. 1999-11 [2009-04-17]. (原始內容存檔於2009-08-06).
- C.W. Clenshaw and F.W.J. Olver. Beyond floating point. Journal of the ACM. Apr 1984, 31 (2): 319–328 [2009-04-21]. doi:10.1145/62.322429.
- W. N. Holmes. Composite Arithmetic: Proposal for a New Standard. Computer. Mar 1997, 30 (3): 65–73 [2009-04-21]. doi:10.1109/2.573666.
- R. Zimmermann. Computer Arithmetic: Principles, Architectures, and VLSI Design (PDF). Lecture notes, Integrated Systems Laboratory, ETH Zürich. 1997 [2009-04-17]. (原始內容 (PDF)存檔於2013-08-17).
- 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].
- C. Frappier. Iterations of a kind of exponentials. Fibonacci Quarterly. 1991, 29 (4): 351–361.
- José Crespo, Francisco Javier Montáns. Fractional Mathematical Operators and Their Computational Approximation. Mathematical Problems in Engineering. 2016, 2016: 1–11 [2021-06-12]. ISSN 1024-123X. doi:10.1155/2016/4356371. (原始內容存檔於2021-05-06) (英語).
- Constantin A. Rubtsov and G. Romerio, Ackermann's Function and New Arithmetical Operation, 2004 [2021-10-02], (原始內容存檔於2021-10-02)