Hiperoperació
En matemàtiques, la successió d'hiperoperació[nb 1] és una successió infinita d'operacions aritmètiques (anomenades hiperoperacions en aquest context)[1][11][13] que comença amb una operació unària (la funció successor amb n = 0). La successió continua amb les operacions binàries d'addició (n = 1), multiplicació (n = 2) i potenciació (n = 3).
Després d'això, la successió continua amb altres operacions binàries que s'estenen més enllà de la potenciació, utilitzant l'associativitat d'operadors. Per a les operacions més enllà de la potenciació, el n-èssim membre d'aquesta successió rep el nom creat per Reuben Goodstein, a partir del prefix grec de n i afegint el sufix -ció (com per exemple, tetració (n = 4), pentació (n = 5), hexació (n = 6), etc.).[5]
Es pot entendre recursivament cada hiperoperació en termes de l'anterior per:
i es pot escriure utilitzant n-2 fletxes de la notació de fletxa de Knuth.
També es pot definir segons la regla de recursivitat de la definició en la versió de fletxa de Knuth de la funció d'Ackermann:
o
Es pot utilitzar per mostrar fàcilment nombres molt més grans dels que es poden representar amb una notació científica (com ara el nombre de Skewes i el googolplex). Per exemple, és molt més gran que el nombre de Skewes i el googolplex. Però hi ha alguns números que fins i tot no es poden mostrar fàcilment, com ara el número de Graham i TREE(3).
Aquesta regla de recursió és comuna a moltes variants d'hiperoperacions.
Definició
La successió d'hiperoperació és la successió d'operacions binàries , definida recursivament de la manera següent:
(Vegeu que per a n = 0, l'operació binària es redueix essencialment a una operació unària (funció successor) ignorant el primer argument.)
Per a n = 0, 1, 2, 3, aquesta definició reprodueix les operacions aritmètiques bàsiques del successor (que és una operació unària), addició, multiplicació i potenciació, respectivament, com
Les operacions H per a n ≥ 3 també es poden escriure amb la notació de Knuth com
- Quina serà la propera operació després de la potenciació? S'ha definit la multiplicació de manera que i la potenciació de manera que pel que sembla lògic definir la següent operació, la tetració, de manera que amb una «torre» de tres «a». Anàlogament, la pentació de (a, 3) serà la tetració (a, tetració (a, a)), amb tres «a» en ella.
- La notació de Knuth es pot estendre a índexs negatius ≥ −2 de manera que estigui d'acord amb tota la successió d'hiperoperació, tret del retard de la indexació:
- Així, les hiperoperacions es poden veure com una resposta a la pregunta «què hi ha a continuació» de la successió: successor, addició, multiplicació, potenciació, etc. Anotant això
- es mostra la relació entre les operacions aritmètiques bàsiques que permeten definir les operacions superiors de manera natural com anterior. De vegades es fa referència als paràmetres de la jerarquia de la hiperoperació amb el seu terme de potenciació anàloga;[14] així a és la base, b és l'exponent (o hiperexponent),[12] i n és el rang (o grau) i, a més,[6] es llegeix com «b-a n-ció d'a», per exemple. es llegeix com la «9a tetració de 7», i es llegeix com la «789a 123-ació de 456».
En termes senzills, les hiperoperacions són formes de compondre els números que augmenten amb el seu creixement a partir de la iteració de la hiperoperació anterior. Els conceptes de successor, addició, multiplicació i potenciació són hiperoperacions; l'operació successora (produint x+1 a partir de x) és la més primitiva, l'operador d'addició especifica el nombre de vegades que s'ha d'afegir 1 per produir un valor final, la multiplicació especifica el nombre de vegades que un nombre s'ha se sumar a si mateix, i la potenciació es refereix al nombre de vegades que un nombre s'ha de multiplicar per si mateix.
Exemples
A continuació, es mostra una llista de les set primeres hiperoperacions (del H0 al H₆) (0⁰ es defineix com a 1).
n | Operació, Hn(a, b) | Definició | Noms | Domini |
---|---|---|---|---|
0 | hiper0, successor, increment, zeració | Arbitrari | ||
1 | hiper1, addició | Arbitrari | ||
2 | hiper2, multiplicació | Arbitrari | ||
3 | hiper3, potenciació | b real, amb algunes extensions multivaluades a nombres complexos | ||
4 | hiper4, tetració | a ≥ 0 o un nombre enter, b o un nombre enter ≥ −1[nb 2] (amb algunes extensions proposades) | ||
5 | hiper5, pentació | a, b enters ≥ −1[nb 2] | ||
6 | hiper6, hexació | a, b enters ≥ −1[nb 2] |
Casos especials
Hn(0, b) |
|
Hn(1, b) | 1, quan n ≥ 3 |
Hn(a, 0) |
|
Hn(a, 1) | a, quan n ≥ 2 |
Hn(a, a) | Hn+1(a, 2), quan n ≥ 1 |
Hn(a, −1)[nb 2] |
|
Hn(2, 2) |
|
Història
Una de les primeres discussions sobre hiperoperacions va ser la d'Albert Bennett el 1914,[6] que va desenvolupar una mica la teoria de les hiperoperacions commutatives (vegeu més avall). Uns dotze anys després, Wilhelm Ackermann va definir la funció que s'assembla una mica a la successió d'hiperoperació.
En el seu treball de 1947,[5] Reuben L. Goodstein va introduir la seqüència específica d'operacions que actualment s'anomenen «hiperoperacions», i també va suggerir els noms amb sufixes grecs (tetració, pentació, etc.), per a les operacions esteses més enllà de la potenciació (perquè corresponen als índexs 4, 5, etc. .). Com a funció de tres arguments, per exemple, , la successió d'hiperoperació en el seu conjunt és una versió de la funció original d'Ackermann (recursiva, però no recursiva primitiva) modificada per Goodstein per incorporar la funció successor primitiva juntament amb les altres tres operacions bàsiques de l'aritmètica (addició, multiplicació, potenciació) i per fer una extensió més perfecta d'aquestes més enllà de la potenciació.
La funció original de tres arguments d'Ackermann utilitza la mateixa regla de recursió que la versió de Goodstein (és a dir, la seqüència d'hiperoperació), però es diferencia d'ella de dues maneres. Primer, defineix una successió d'operacions a partir de l'addició (n = 0) en lloc de la funció successora, després la multiplicació (n = 1), la potenciació (n = 2), etc. En segon lloc, les condicions inicials per a es transforma en , diferenciant-se així de les hiperoperacions més enllà de la potenciació.[7][15][16] La importància de b + 1 a l'expressió anterior és que = , on b compta el nombre d'operants (exponents), en comptes de comptar el nombre d'operadors (a) com ho fa amb la b en (o ) i així successivament per a les operacions de nivell superior. (Vegeu l'article de la funció d'Ackermann per obtenir més detalls).
Notacions
Aquesta és una llista de notacions que s'han utilitzat per a les hiperoperacions.
Nom | Notació equivalent a | Comentari |
---|---|---|
Notació de Bowers | Jonathan Bowers (per a n ≥ 1). | |
Notació de caixa | Usat per Rubtsov i Romerio.[17] | |
Notació claudàtor | S'utilitza en molts fòrums en línia; convenient per a ASCII. | |
Notació de Goodstein | Usat per Reuben Goodstein.[5] | |
Notació de Hilbert | Usat per David Hilbert.[18] | |
Notació de Knuth | Usat per Knuth[19] (per a n ≥ 3), i es troba en diversos llibres de referència.[20][21] | |
Notació de Nambiar | Usat per Nambiar (per a n ≥ 1).[22] | |
Notació operador (per a «operacions esteses») | Usat per a hiperoperacions inferiors per John Donner i Alfred Tarski (per a n ≥ 1).[23] | |
Notació superíndex | Usat per Robert Munafo.[10] | |
Notació subíndex (per a hiperoperacions inferiors) | Usat per a hiperoperacions inferiors per Robert Munafo.[10] | |
Notació de fletxa encadenada de Conway | Usat per John Horton Conway (per a n ≥ 3). | |
Funció original d'Ackermann | Usat per Wilhelm Ackermann (per a n ≥ 1).[24] | |
Funció d'Ackermann-Péter | Això correspon a les hiperoperacions de base 2 (a = 2). |
Variant a partir de a
El 1928, Wilhelm Ackermann va definir una funció de tres arguments que progressivament va evolucionar cap a una funció de dos arguments coneguda com a funció d'Ackermann. La funció original d'Ackermann s'assemblava menys a les hiperoperacions modernes, ja que comencen les seves condicions inicials per a tots n> 2. També va assignar l'addició a n = 0, la multiplicació a n = 1 i la potenciació a n = 2, de manera que les condicions inicials produeixen operacions molt diferents per a la tetració i més enllà.
n | Operació | Comentari |
---|---|---|
0 | ||
1 | ||
2 | ||
3 | Una forma compensada de tetració. La iteració d'aquesta operació és diferent de la iteració de la tetració. | |
4 | No s'ha de confondre amb la pentació. |
Una altra condició inicial que s'ha utilitzat és (on la base és constant, ), es deu a Rózsa Péter, que no forma una jerarquia d'hiperoperació.
Variant a partir de 0
El 1984, C. W. Clenshaw i F. W. J. Olver van iniciar la discussió sobre l'ús d'hiperoperacions per evitar desbordaments de comes flotants als ordinadors.[25] Des d'aleshores, molts altres autors han renovat l'interès per l'aplicació d'hiperoperacions a la representació en coma flotant.[26][27][28] (com que Hn(a, b) estan definits per a b = -1). Mentre es discuteix la tetració, Clenshaw et al. va assumir la condició inicial , que converteix en una altra jerarquia d'hiperoperació. Igual que en la variant anterior, la quarta operació és molt similar a la tetració, però es compensa per una.
n | Operació | Comentari |
---|---|---|
0 | ||
1 | ||
2 | ||
3 | ||
4 | Una forma compensada de tetració. La iteració d'aquesta operació és diferent de la iteració de la tetració.. | |
5 | No s'ha de confondre amb la pentació. |
Hiperoperacions inferiors
Una alternativa per a aquestes hiperoperacions s'obté mitjançant l'avaluació d'esquerra a dreta. A partir de
es defineix (amb ° o subíndex)
amb
Donner i Tarski es van estendre als nombres ordinals,[23][Definició 1] per :
Es deriva de la definició 1 (i), el corol·lari 2 (ii) i el teorema 9, que, per a ≥ 2 i b ≥ 1, s'obté
Però això pateix una espècie de col·lapse, al no poder formar la «torre d'exponents» tradicionalment esperada pels hiperoperadors:[23][Teorema 3(iii)][nb 5]
Si α ≥ 2 i γ ≥ 2,[23][Corol·lari 33(i)][nb 5]
n | Operació | Comentari |
---|---|---|
0 | increment, successor, zeració | |
1 | ||
2 | ||
3 | ||
4 | No s'ha de confondre amb la tetració. | |
5 | No s'ha de confondre amb la pentació. Semblant a la tetració |
Hiperoperacions commutatives
Albert Bennett va tenir en compte les hiperoperacions commutatives ja des del 1914,[6] que possiblement va ser el primer comentari sobre qualsevol successió d'hiperoperació. Les hiperoperacions commutatives estan definides per la regla de la recursió
que és simètrica en a i b, és a dir, totes les hiperoperacions són commutatives. Aquesta seqüència no conté la potenciació, per tant no forma una jerarquia d'hiperoperació.
n | Operació | Comentari |
---|---|---|
0 | Màxim regularitzat | |
1 | ||
2 | Això es deu a les propietats del logaritme. | |
3 | ||
4 | No s'ha de confondre amb la tetració. |
Notes
- ↑ Han existit successions semblants a la successió d'hiperoperació, com la funció d'Ackermann[1] (3-argument), la jerarquia d'Ackermann,[2] la jerarquia de Grzegorczyk[3][4] (que és més general), la versió de Goodstein de la funció d'Ackermann,[5] operació de n-èsim grau,[6] potenciació de z-plec de x amb y, [7] operacions amb fletxes,[8] reihenalgebra[9] i hiper-n.[1][9][10][11][12]
- ↑ 2,0 2,1 2,2 2,3 Sigui x = a[n](−1). Per a la fórmula de recursivitat, a[n]0 = a[n − 1](a[n](−1)) ⇒ 1 = a[n − 1]x. Una solució és x = 0, ja que tenim a[n − 1]0 = 1 per definició quan n ≥ 4. Aquesta solució és única perquè a[n − 1]b > 1 per a tot a > 1, b > 0 (prova mitjançant recursivitat).
- ↑ 3,0 3,1 Per a més detalls, vegeu Potències de 0.
- ↑ 4,0 4,1 Per a més detalls, vegeu Zero elevat a zero.
- ↑ 5,0 5,1 L'addició ordinal no és commutativa; vegeu aritmètica ordinal per obtenir més informació.
Referències
- ↑ 1,0 1,1 1,2 Geisler, Daniel. «What lies beyond exponentiation?» (en anglès), 2003.
- ↑ Friedman, Harvey M. «Long Finite Sequences» (en anglès). Journal of Combinatorial Theory, Series A, 95(1), juliol 2001, pàg. 102–144. DOI: 10.1006/jcta.2000.3154.
- ↑ Lameiras Campagnola, Manuel; Moore, Cris; Costa, José Félix «Transfinite Ordinals in Recursive Number Theory» (en anglès). Journal of Complexity, 18(4), desembre 2002, pàg. 977–1000. DOI: 10.1006/jcom.2002.0655.
- ↑ Wirz, Marc «Characterizing the Grzegorczyk hierarchy by safe recursion» (en anglès). CiteSeer, 1999.
- ↑ 5,0 5,1 5,2 5,3 Goodstein, R. L «Transfinite Ordinals in Recursive Number Theory» (en anglès). Journal of Symbolic Logic, 12(4), desembre 1947, pàg. 123–129. DOI: 10.2307/2266486. JSTOR: 2266486.
- ↑ 6,0 6,1 6,2 6,3 Bennett, Albert A. «Note on an Operation of the Third Grade» (en anglès). Annals of Mathematics, 17(2), desembre 1915, pàg. 74–75. DOI: 10.2307/2007124. JSTOR: 2007124.
- ↑ 7,0 7,1 Black, Paul E. «Ackermann's function» (en anglès). Dictionary of Algorithms and Data Structures (U.S. National Institute of Standards and Technology - NIST), 16-03-2009.
- ↑ Littlewood, J. E. «Large Numbers» (en anglès). Mathematical Gazette, 32(300), juliol 1948, pàg. 163–171. DOI: 10.2307/3609933. JSTOR: 3609933.
- ↑ 9,0 9,1 Müller, Markus. «Reihenalgebra» (
PDF) (en anglès), 1993. Arxivat de l'original el 2013-12-02. [Consulta: 23 maig 2020].
- ↑ 10,0 10,1 10,2 Munafo, Robert. «Inventing New Operators and Functions» (en anglès). Large Numbers at MROB, novembre 1999.
- ↑ 11,0 11,1 Robbins, A. J. «Home of Tetration» (en anglès), novembre 2005. Arxivat de l'original el 2015-06-13. [Consulta: 23 maig 2020].
- ↑ 12,0 12,1 Galidakis, I. N. «Mathematics» (en anglès), 2003. Arxivat de l'original el 2009-04-20. [Consulta: 23 maig 2020].
- ↑ Rubtsov, C. A; Romerio, G. F. «Ackermann's Function and New Arithmetical Operation» (en anglès), desembre 2005.
- ↑ Romerio, G. F. «Hyperoperations Terminology» (en anglès). Tetration Forum, 21-01-2008.
- ↑ Munafo, Robert. «Versions of Ackermann's Function» (en anglès). Large Numbers at MROB, 03-11-1999.
- ↑ Cowles, J.; Bailey, T. «Several Versions of Ackermann's Function» (en anglès). Dept. of Computer Science, University of Wyoming, Laramie, WY, 30-09-1988.
- ↑ Rubtsov, C. A; Romerio, G. F. «Ackermann's Function and New Arithmetical Operation» (en anglès), desembre 2005.
- ↑ Hilbert, David «Über das Unendliche» (en alemany). Mathematische Annalen, 95, 1926, pàg. 161-190. DOI: 10.1007/BF01206605.
- ↑ Knuth, Donald E «Mathematics and Computer Science: Coping with Finiteness» (en anglès). Science, 194(4271), desembre 1976, pàg. 1235–1242. Bibcode: 1976Sci...194.1235K. DOI: 10.1126/science.194.4271.1235. PMID: 17797067.
- ↑ Zwillinger, Daniel. CRC standard mathematical tables and formulae (en anglès). CRC Press, 2002, p. 4. ISBN 1-58488-291-3.
- ↑ Weisstein, Eric W. CRC concise encyclopedia of mathematics (en anglès). CRC Press, 2003, p. 127–128. ISBN 1-58488-347-2.
- ↑ Nambiar, K. K «Ackermann Functions and Transfinite Ordinals» (en anglès). Applied Mathematics Letters, 8(6), 1995, pàg. 51–53. DOI: 10.1016/0893-9659(95)00084-4.
- ↑ 23,0 23,1 23,2 23,3 Donner, John; Tarski, Alfred «An extended arithmetic of ordinal numbers» (en anglès). Fundamenta Mathematicae, 65, pàg. 95–127. DOI: 10.4064/fm-65-1-95-127.
- ↑ Ackermann, Wilhelm «Zum Hilbertschen Aufbau der reellen Zahlen» (en alemany). Mathematische Annalen, 99, 1928, pàg. 118–133. DOI: 10.1007/BF01459088.
- ↑ Clenshaw, C.W; Olver, F.W.J «Beyond floating point» (en anglès). Journal of the ACM, 31(2), abril 1984, pàg. 319–32. DOI: 10.1145/62.322429.
- ↑ Holmes, W. N «Composite Arithmetic: Proposal for a New Standard» (en anglès). Computer, 30(3), març 1997, pàg. 65–73. DOI: 10.1109/2.573666.
- ↑ Zimmermann, R. «Computer Arithmetic: Principles, Architectures, and VLSI Design» (
PDF) (en anglès). Lecture notes, Integrated Systems Laboratory, ETH Zürich, 1997. Arxivat de l'original el 2013-08-17. [Consulta: 23 maig 2020].
- ↑ Pinkiewicz, T; Holmes, N; Jamil, T. «Design of a composite arithmetic unit for rational numbers». A: Proceedings of the IEEE Southeast Con 2000. 'Preparing for the New Millennium' (Cat. No.00CH37105) (en anglès). Proceedings of the IEEE, 2000, p. 245–252. DOI 10.1109/SECON.2000.845571. ISBN 0-7803-6312-4.