Hiperoperación

Enmatemáticas,asecuencia de hiperoperaciónsé unhasecuenciainfinita de operacións aritméticas (chamadashiperoperaciónsneste contexto) que comeza cunha operación unitaria (a función sucesora conn= 0). A secuencia continúa coasoperacións binariasdesuma(n= 1),multiplicación(n= 2) epotenciación(n= 3).

Despois diso, a secuencia continúa con operacións binarias que se estenden máis aló da potenciación, tendo en conta que non son asociativas (por exemplo, atetraciónque procede da potenciación ${}^{3}3=3^{(3^{3})}=3^{9}\neq 9^{3}=(3^{3})^{3}$ ). Para as operacións máis aló da potenciación, o membron-ésimo desta secuencia é nomeado porReuben Goodsteindespois doprefixogrego densufixado con-ación(comotetración(n= 4),pentación(n= 5), hexación (n= 6). ), etc.)^[1]e pódese escribir usandon− 2 frechas nanotación de frecha cara arriba de Knuth.Cada hiperoperación pódese entenderrecursivamenteen función da anterior por:

a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots [n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a},\quad n\geq 2

Tamén se pode definir segundo unha regra recursiva parte da definición, como aparece na versión de Knuth con frecha cara arriba dafunción de Ackermann:

a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1

Isto pódese empregar para mostrar facilmente números moito máis grandes que os que pode facer mediantea notación científica,comoo número de Skeweseo googolplexplex(p. ex. $50[50]50$ é moito maior que o número de Skewes e o googolplex), pero hai algúns números que nin as hiperoperación pódenos mostrar facilmente, comoo número de GrahameTREE(3).^[2]

Esta regra de recursión é común a moitas variantes das hiperoperacións.

Definición

Definición (a máis común)

ASecuencia de hiperoperación $H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}$ é asecuenciadeoperacións binarias $H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}$ ,definidorecursivamentecomo segue:

H_{n}(a,b)=a[n]b={\begin{cases}b+1&{\text{se }}n=0\\a&{\text{se }}n=1{\text{ e }}b=0\\0&{\text{se }}n=2{\text{ e }}b=0\\1&{\text{se }}n\geq 3{\text{ e }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{senón}}\end{cases}}

(Teña en conta que paran= 0, aoperación binariaredúcese esencialmente a unha operación unitaria (función sucesora) ignorando o primeiro argumento.)

Paran= 0, 1, 2, 3, esta definición reproduce as operacións aritméticas básicas da sucesión (que é unha operación unitaria),suma,multiplicacióneexponenciación,respectivamente, como

{\begin{aligned}H_{0}(a,b)&=1+b,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a\uparrow {b}=a^{b}.\end{aligned}}

As $H_{n}$ operacións paran≥ 3 pódense escribir nanotación de frecha cara arriba de Knuth.

Entón, cal será a seguinte operación despois da exponenciación? Definimos a multiplicación para que $H_{2}(a,3)=a[2]3=a\times 3=a+a+a,$ e definiuse a potenciación para que $H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,$ polo que parece lóxico definir a seguinte operación, a tetración, para que $H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3={\text{tetración}}(a,3)=a^{a^{a}}$ cunha torre de tres 'a'. De xeito análogo, a pentación de (a, 3) será tetración(a, tetración(a, a)), con tres "a" nela.

{\begin{aligned}H_{4}(a,b)&=a\uparrow \uparrow {b},\\H_{5}(a,b)&=a\uparrow \uparrow \uparrow {b},\\\ldots &\\H_{n}(a,b)&=a\uparrow ^{n-2}b{\text{ para }}n\geq 3,\\\ldots &\\\end{aligned}}

A notación de Knuth podería estenderse a índices negativos ≥ −2 de tal xeito que concorde con toda a secuencia de hiperoperacións, excepto para o atraso na indexación:

H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ para }}n\geq 0.

Así, as hiperoperacións pódense ver como unha resposta á pregunta "que segue" nasecuencia:sucesor,suma,multiplicación,potenciación,etc. Observando iso

{\begin{aligned}a+b&=1+(a+(b-1))\\a\cdot b&=a+(a\cdot (b-1))\\a^{b}&=a\cdot \left(a^{(b-1)}\right)\\a[4]b&=a^{a[4](b-1)}\end{aligned}}

a relación entre as operacións aritméticas básicas está ilustrada, permitindo que as operacións superiores se definan de forma natural como se realizou anteriormente. Os parámetros da xerarquía de hiperoperación son ás veces referidos polo seu termo de exponenciación análogo;^[3]polo queaé abase,bé oexpoñente(ouhiperexpoñente),^[4]ené orango(ougrao),^[5]e ademais, $H_{n}(a,b)$ léase como "ab-ésimon-ación dea",p. ex $H_{4}(7,9)$ lese como "a novena tetración de 7", e $H_{123}(456,789)$ lese como "a 789a 123-ación de 456".

En termos comúns, as hiperoperacións son formas de combinar números que aumentan o crecemento en función da iteración da hiperoperación anterior. Os conceptos de sucesor, suma, multiplicación e potenciación son hiperoperacións; a operación sucesora (producindox+ 1 a partir dex) é a máis primitiva, o operador de suma especifica o número de veces que 1 se debe engadir a si mesmo para producir un valor final, a multiplicación especifica o número de veces que se lle debe engadir un número a si mesmo, e a exponenciación refírese ao número de veces que se debe multiplicar un número por si mesmo.

Definición, mediante iteración

Defínese aiteracióndunha función $f$ de dúas variables como

f^{x}(a,b)={\begin{cases}f(a,b)&{\text{if }}x=1\\f(a,f^{x-1}(a,b))&{\text{if }}x>1\end{cases}}

A secuencia de hiperoperación pódese definir en termos de iteración, como segue. Para todos os números enteiros $x,n,a,b\geq 0,$ definir

{\begin{array}{lcl}H_{0}(a,b)&=&b+1\\H_{1}(a,0)&=&a\\H_{2}(a,0)&=&0\\H_{n+3}(a,0)&=&1\\H_{n+1}(a,b+1)&=&H_{n}^{b+1}(a,H_{n+1}(a,0))\\H_{n}^{x+2}(a,b)&=&H_{n}(a,H_{n}^{x+1}(a,b))\end{array}}

Como a iteración éasociativa,a última liña pódese substituír por

{\begin{array}{lcl}H_{n}^{x+2}(a,b)&=&H_{n}^{x+1}(a,H_{n}(a,b))\end{array}}

Exemplos

A continuación móstrase unha lista das sete primeiras hiperoperacións (da 0 á 6) ( ou 0⁰ defínese como 1).

n	Operación, H_n(a,b)	Definición	Nomes	Dominio
0	$1+b$ ou $a[0]b$	$1+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copias de 1}}}$	Incremento, succesor, hyper0	Arbitrario
1	$a+b$ ou $a[1]b$	$a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copias de 1}}}$	Adicion,hyper1
2	$a\times {b}$ ou $a[2]b$	$\underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copias de }}a}$	Multiplicación,hyper2
3	$a^{b}$ ou $a[3]b$	$\underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copias de }}a}$	Potentiation,hyper3	breal, con algunas extensiones a determinadosnúmeros complexos
4	$^{b}a$ ou $a[4]b$	$\underbrace {a[3](a[3](a[3](\cdots [3](a[3](a[3]a))\cdots )))} _{\displaystyle b{\mbox{ copias de }}a}$	Tetración,hyper4	a≥ 0 ou enteiro,bun enteiro ≥ −1 (con algunhas propostas de extensión)
5	$_{b}a$ ou $a[5]b$	$\underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copias de }}a}$	Pentación,hyper5	a,benteiros ≥ −1
6	$a[6]b$	$\underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copias de }}a}$	Hexación, hyper6	a,benteiros ≥ −1

Casos especiais

H_n(0,b) =

b+ 1, candon= 0

b,candon= 1

0, candon= 2

1, candon= 3 eb= 0^{[nb 1]}

0, candon= 3 eb> 0^{[nb 1]}

1, candon> 3 ebé par (incluíndo 0)

0, candon> 3 ebé impar

H_n(1,b) =

b,candon= 2

1, candon≥ 3

H_n(a,1) =

0, candon= 2

1, candon= 0, oun≥ 3

a,candon= 1

H_n(a,a) =

a, candon≥ 2

H_n(a,a) =

H_n+1(a,2), candon≥ 1

H_n(a,−1) =

0, candon= 0, oun≥ 4

a- 1, candon= 1

−a,candon= 2

{\frac {1}{a}}

,cando n= 3

H_n(2, 2) =

3, candon= 0

4, candon≥ 1, facilmente demostrable recursivamente.

Notacións

Esta é unha lista de notacións que se utilizaron para hiperoperacións.

Nome	Notación equivalente a $H_{n}(a,b)$	Comentario
Notación de frecha cara arriba de Knuth	$a\uparrow ^{n-2}b$	Empregada porKnuth^[6](paran≥ 3), e aparece en moitos libros de referencia.^[7]^[8]
Notación de Hilbert	$\phi _{n}(a,b)$	Empregada porDavid Hilbert.^[9]
Notación de Goodstein	$G(n,a,b)$	Empregada porReuben Goodstein.^[1]
A orixinal daFunción de Ackermann	${\begin{matrix}\phi (a,b,n-1)\ {\text{ para }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ para }}n\geq 4\end{matrix}}$	Empregada porWilhelm Ackermann(paran≥ 1)^[10]
Función de Ackermann–Péter	$A(n,b-3)+3\ {\text{para }}a=2$	Para as hiperoperación de base a = 2
Notación de Nambiar	$a\otimes ^{n-1}b$	Empregada por Nambiar (paran≥ 1)^[11]
Notación Superscript	$a{}^{(n)}b$	Empregada porRobert Munafo.^[12]
Notación de corchetes	$a[n]b$	Empregada por foros online; conveniente paraASCII.
Notación de frechas en cadena de Conway	$a\to b\to (n-2)$	Empregada porJohn Horton Conway(paran≥ 3)

Notas

↑^1,0^1,1Para máis detalle, verpotenciación con expoñente cero.

Véxase tamén

Bibliografía

Ackermann, Wilhelm(1928)."Zum Hilbertschen Aufbau der reellen Zahlen".Mathematische Annalen99:118–133.doi:10.1007/BF01459088.
Bennett, Albert A. (Dec 1915). "Note on an Operation of the Third Grade".Annals of Mathematics.Second Series17(2): 74–75.JSTOR 2007124.doi:10.2307/2007124.
Bezem, Marc; Klop, Jan Willem; De Vrijer, Roel (2003). "First-order term rewriting systems".Term Rewriting Systems by "Terese".Cambridge University Press. pp. 38–39.ISBN 0-521-39115-6.
Black, Paul E. (2009-03-16)."Ackermann's function".Dictionary of Algorithms and Data Structures.U.S. National Institute of Standards and Technology (NIST).Consultado o2021-08-29.
Campagnola, Manuel Lameiras;Moore, Cristopher;Félix Costa, José (Dec 2002). "Transfinite Ordinals in Recursive Number Theory".Journal of Complexity18(4): 977–1000.doi:10.1006/jcom.2002.0655.
Clenshaw, C.W.; Olver, F.W.J. (Apr 1984). "Beyond floating point".Journal of the ACM31(2): 319–328.doi:10.1145/62.322429.
Cornelius, B.J.; Kirby, G.H. (1975). "Depth of recursion and the ackermann function".BIT Numerical Mathematics15(2): 144–150.doi:10.1007/BF01932687.
Cowles, J.; Bailey, T. (1988-09-30)."Several Versions of Ackermann's Function".Dept. of Computer Science, University of Wyoming, Laramie, WY.Consultado o2021-08-29.
Doner, John;Tarski, Alfred(1969). "An extended arithmetic of ordinal numbers".Fundamenta Mathematicae65:95–127.doi:10.4064/fm-65-1-95-127.
Friedman, Harvey M. (Jul 2001). "Long Finite Sequences".Journal of Combinatorial Theory.Series A95(1): 102–144.doi:10.1006/jcta.2000.3154.
Galidakis, I. N. (2003)."Mathematics".Arquivado dendeo orixinalo April 20, 2009.Consultado o2009-04-17.
Geisler, Daniel (2003)."What lies beyond exponentiation?".Consultado o2009-04-17.
Goodstein, Reuben Louis (Dec 1947)."Transfinite Ordinals in Recursive Number Theory"(PDF).Journal of Symbolic Logic12(4): 123–129.JSTOR 2266486.doi:10.2307/2266486.
Hilbert, David (1926)."Über das Unendliche".Mathematische Annalen95:161–190.doi:10.1007/BF01206605.
Holmes, W. N. (Mar 1997)."Composite Arithmetic: Proposal for a New Standard".Computer30(3): 65–73.doi:10.1109/2.573666.Consultado o2009-04-21.
Knuth, Donald Ervin (Dec 1976)."Mathematics and Computer Science: Coping with Finiteness".Science194(4271): 1235–1242.Bibcode:1976Sci...194.1235K.PMID 17797067.doi:10.1126/science.194.4271.1235.Consultado o2009-04-21.
Littlewood, J. E. (July 1948)."Large Numbers".Mathematical Gazette32(300): 163–171.JSTOR 3609933.doi:10.2307/3609933.
Meyer, Albert R.;Ritchie, Dennis MacAlistair(1967).The complexity of loop programs.ACM '67: Proceedings of the 1967 22nd national conference.doi:10.1145/800196.806014.
Müller, Markus (1993)."Reihenalgebra"(PDF).Arquivado dendeo orixinal(PDF)o 2013-12-02.Consultado o2021-11-06.
Munafo, Robert (1999a)."Versions of Ackermann's Function".Large Numbers at MROB.Consultado o2021-08-28.
Munafo, Robert (1999b)."Inventing New Operators and Functions".Large Numbers at MROB.Consultado o2021-08-28.
Nambiar, K. K. (1995)."Ackermann Functions and Transfinite Ordinals".Applied Mathematics Letters8(6): 51–53.doi:10.1016/0893-9659(95)00084-4.
Perstein, Millard H. (1 June 1962). "Algorithm 93: General order arithmetic".Communications of the ACM(New York City:Association for Computing Machinery)5(6): 344.ISSN 0001-0782.doi:10.1145/367766.368160.
Pinkiewicz, T.; Holmes, N.; Jamil, T. (2000). "Design of a composite arithmetic unit for rational numbers".Proceedings of the IEEE SoutheastCon2000. 'Preparing for the New Millennium' (Cat. No.00CH37105).Proceedings of the IEEE. pp. 245–252.ISBN 0-7803-6312-4.doi:10.1109/SECON.2000.845571.
Robbins, A. J. (November 2005)."Home of Tetration".Arquivado dendeo orixinalo 13 June 2015.Consultado o2009-04-17.
Romerio, G. F. (2008-01-21)."Hyperoperations Terminology".Tetration Forum.Consultado o2009-04-21.
Rubtsov, C. A.; Romerio, G. F. (December 2005)."Ackermann's Function and New Arithmetical Operation".Consultado o2009-04-17.
Townsend, Adam (12 May 2016)."Names for large numbers".Chalkdust magazine.
Weisstein, Eric W. (2003).CRC concise encyclopedia of mathematics, 2nd Edition.CRC Press. pp. 127–128.ISBN 1-58488-347-2.
Wirz, Marc (1999)."Characterizing the Grzegorczyk hierarchy by safe recursion"(PDF).Bern: Institut für Informatik und angewandte Mathematik.
Zimmermann, R. (1997)."Computer Arithmetic: Principles, Architectures, and VLSI Design"(PDF).Lecture notes, Integrated Systems Laboratory, ETH Zürich. Arquivado dendeo orixinal(PDF)o 2013-08-17.Consultado o2009-04-17.
Zwillinger, Daniel (2002).CRC standard mathematical tables and formulae, 31st Edition.CRC Press. p. 4.ISBN 1-58488-291-3.

Outros artigos

Pentación.

[FOOTNOTEGoodstein1947-1] 1,0^1,1Goodstein 1947.

[FOOTNOTETownsend2016-2] Townsend 2016.

[FOOTNOTERomerio2008-3] Romerio 2008.

[FOOTNOTEGalidakis2003-4] Galidakis 2003.

[FOOTNOTEBennett1915-5] Bennett 1915.

[FOOTNOTEKnuth1976-7] Knuth 1976.

[FOOTNOTEZwillinger2002-8] Zwillinger 2002.

[FOOTNOTEWeisstein2003-9] Weisstein 2003.

[FOOTNOTEHilbert1926-10] Hilbert 1926.

[FOOTNOTEAckermann1928-11] Ackermann 1928.

[FOOTNOTENambiar1995-12] Nambiar 1995.

[FOOTNOTEMunafo1999b-13] Munafo 1999b.

[corona1-6] 1,0^1,1Para máis detalle, verpotenciación con expoñente cero.

[1]

[2]

[3]

[4]

[5]

[nb 1]

[6]

[7]

[8]

[9]

[10]

[11]

[12]