Hiperoperação

Em matemática, a seqüencia de hiperoperações é uma seqüencia de operações binárias que iniciam com a adição, multiplicação e exponenciação, chamadas hiperoperações[1][2] em geral. O n-ésimo membro desta seqüencia foi nomeado por Reuben Goodstein seguindo o prefixo grego de n acrescido do sufixo -ção (como em tetração, pentação) [3] e pode ser escrito usando ${\displaystyle (n-2)}$ setas na Notação de Knuth.

Cada hiperoperação é definida recursivamente em termos da anterior, como é o caso com a notação de seta para cima de Knuth. A parte da definição que faz isso é a regra recursiva da função de Ackermann:

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

que é comum a muitas variantes de hiperoperações (ver abaixo).

Definição

A seqüencia de hiperoperação é uma seqüência ${\displaystyle H_{n}}$ de operações binárias em ${\displaystyle \mathbb {N} }$, indexadas por ${\displaystyle \mathbb {N} }$, que começa com a adição (n = 1), multiplicação (n = 2) e exponenciação ${\displaystyle (n=3)}$. Os parâmetros da hierarquia de hiperoperações saõ referenciados por seus termos exponenciais análogos[4]; assim a é a base, b é o expoente (ou hiperexpoente[5]), e n é o rank (ou grade[6]).

Usando a notação de seta para cima de Knuth nós podemos definir hiperoperações como

${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b={\begin{cases}b+1&{\text{se }}n=0\\a&{\text{se }}n=1,b=0\\0&{\text{se }}n=2,b=0\\1&{\text{se }}n\geq 3,b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{em outro caso}}\end{cases}}}$

Pode ser visto como uma resposta à pergunta "Qual é o próximo" na sequência: adição, multiplicação, exponenciação, e assim por diante. Notando que

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

Isso produz uma relação natural entre as hiperoperações, e permite que operações maiores sejam definidas, que produzem um grande número de entradas de pequeno porte, como explicado no artigo separado sobre tetração.

Em termos comuns, hiperoperações são maneiras de combinar os números que aumentam em crescimento com base na iteração da hiperoperação anterior. Os conceitos de adição, multiplicação e exponenciação são todos hiperoperações; o operador de adição especifica o número de vezes que um deve ser adicionado a si mesmo para produzir um valor final, a multiplicação especifica o número de vezes que um número deve ser adicionado a si mesmo, e exponenciação se refere ao número de vezes que um número deve ser multiplicado por si mesmo.

Exemplos

Esta é uma lista dos sete primeiras hiperoperações.

n	Operação	Definição	Nomes	Domínio
0	${\displaystyle b+1}$	${\displaystyle {1+{\underbrace {1+1+1+\cdots +1} _{b}}}}$	hiper0, incremento, sucessor, zeração	b arbitrário
1	${\displaystyle a+b}$	${\displaystyle {a+{\underbrace {1+1+1+\cdots +1} _{b}}}}$	hiper1, adição	arbitrário
2	${\displaystyle ab}$	${\displaystyle {{\underbrace {a+a+a+\cdots +a} } \atop {b}}}$	hiper2, multiplicação	arbitrário
3	${\displaystyle a\uparrow b=a^{b}}$	${\displaystyle {{\underbrace {a\cdot a\cdot a\cdot a\cdot \ldots \cdot a} } \atop {b}}}$	hiper3, exponenciação	a > 0, b real, ou a não-zero, b um inteiro, com algumas extensões multivaloradas para números complexos
4	${\displaystyle a\uparrow \uparrow b}$	${\displaystyle {{\underbrace {a\uparrow a\uparrow a\uparrow \cdots \uparrow a} } \atop {b}}}$	hiper4, tetração	a > 0, b um inteiro ≥ −1 (com algumas extensões propostas)
5	${\displaystyle a\uparrow \uparrow \uparrow b}$ or ${\displaystyle a\uparrow ^{3}b}$	${\displaystyle {{\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} } \atop {b}}}$	hiper5, pentação	a e b inteiros, a > 0, b ≥ 0
6	${\displaystyle a\uparrow ^{4}b}$	${\displaystyle {{\underbrace {a\uparrow ^{3}a\uparrow ^{3}\cdots \uparrow ^{3}a} } \atop {b}}}$	hiper6, hexação	a e b inteiros, a > 0, b ≥ 0

História

Uma das primeiras discussões sobre hiperoperações foi a de Albert Bennett[6] em 1914, que desenvolveu parte da teoria de hiperoperações comutativas(ver abaixo). Cerca de 12 anos mais tarde, Wilhelm Ackermann, definiu a função ${\displaystyle \phi (a,b,n)}$[7] que lembra de alguma forma a seqüência de hiperoperações. A função de Ackermann original, com três argumentos usa a mesma regra de recursão, mas ela difere da moderna hiperoperação em pelo menos duas maneiras. Em primeiro lugar, atribuí adição para ${\displaystyle n=0}$, a multiplicação para ${\displaystyle n=1}$ e exponenciação para ${\displaystyle n=2}$. Em segundo lugar, as condições iniciais do ${\displaystyle \phi }$ indicam que ${\displaystyle \phi (a,b,3)=a\uparrow \uparrow (b+1)}$, produz valores muito diferentes de hiperoperações sobre exponenciação[8][9][10].

Em 1947, Reuben Goodstein[3] definiu a seqüencia de hiperoperaçõescomo é conhecida hoje, onde ele usou a notação ${\displaystyle G(n,a,b)}$ para o que seria escrito como ${\displaystyle a\uparrow ^{n-2}b}$ na notação de seta para cima de Knuth. No seu artigo de 1947, Goodstein introduziu os nomes "tetração", "pentação", "hexação", etc., para os sucessivos operadores além da exponenciação.

Notações

Esta é uma lista de notações que foram utilizados para hiperoperações.

Nome	Notação	Comentário
Notação padrão de seta de Knuth	${\displaystyle a\uparrow ^{n-2}b=H_{n}(a,b)}$	Usada por Knuth,[11] e encontrado em vários livros de referência.[12][13]
Notação de Goodstein	${\displaystyle G(n,a,b)}$	Usada por Reuben Goodstein.[3]
Função original de Ackermann	${\displaystyle A(a,b,n-1)=H_{n}(a,b)}$	Esta não é o mesmo que hiperoperações.
Função moderna de Ackermann	${\displaystyle A(n,b-3)+3=H_{n}(2,b)}$	Esta é o mesmo que hiperoperações para a base 2.
Notação de Nambiar	${\displaystyle a\otimes ^{n}b}$	Usada por Nambiar[14]
Notação de Caixa	${\displaystyle a{\,{\begin{array}{|c|}\hline {\!n\!}\\\hline \end{array}}\,}b}$	Usada por Rubtsov e Romerio.[2][4]
Notação de Sobrescrito	${\displaystyle a{}^{(n)}b}$	Usada por Robert Munafo.[9]
Subscript notation	${\displaystyle a{}_{(n)}b}$	Usada para hyperoperações inferiores em Robert Munafo.[9]
Notação de colchetes	a[n]b	Usado em muitos fóruns online; conveniente para ASCII.

Generalização

Para condições iniciais diferentes ou regras de recursão diferentes, operações muito diferentes podem ocorrer. Alguns matemáticos referem-se a todas as variantes, como exemplos de hiperoperações.

No sentido geral, uma hierarquia de hiperoperações ${\displaystyle (S,\,I,\,F)}$ é uma família ${\displaystyle (F_{n})_{n\in I}}$ de operações binárias em ${\displaystyle S}$, indexada por um conjunto ${\displaystyle I}$, tal que existe ${\displaystyle i,j,k\in I}$ onde

• ${\displaystyle F_{i}(a,b)=a+b}$ (adição),
• ${\displaystyle F_{j}(a,b)=ab}$ (multiplicação), e
• ${\displaystyle F_{k}(a,b)=a^{b}}$ (exponenciação).

Além disso, se a última condição é relaxada (ou seja, não há exponenciação), então nós também podemos incluir as hiperoperações comutativas, descritas abaixo. Embora se possa listar cada hiperoperação explicitamente, este não é geralmente o caso. A maioria das variantes incluem apenas as funções sucessoras (ou adição) em sua definição e redefinem a multiplicação (e além), com base em uma regra de recursão única que se aplica a todas as categorias. Uma vez que esta é parte da definição da hierarquia, e não uma propriedade da hierarquia em si, é difícil definir formalmente.

Existem muitas possibilidades para hiperoperações que são diferentes da versão de Goodstein. Por meio de diferentes condições iniciais para ${\displaystyle F_{n}(a,0)}$ ou ${\displaystyle F_{n}(a,1)}$, as iterações destas condições podem produzir diferentes hiperoperações acima da exponenciação, enquanto ainda correspondendo à adição e multiplicação. A definição moderna de hiperoperações inclui ${\displaystyle F_{n}(a,0)=1}$ para todo ${\displaystyle n\geq 3}$, considerando que as variantes abaixo incluem ${\displaystyle F_{n}(a,0)=a}$, e ${\displaystyle F_{n}(a,0)=0}$.

Um problema em aberto na pesquisa sobre hiperoperações é saber se a hierarquia de hiperoperações ${\displaystyle (\mathbb {N} ,\mathbb {N} ,F)}$ pode ser generalizada para ${\displaystyle (\mathbb {C} ,\mathbb {C} ,F)}$, e se ${\displaystyle (\mathbb {C} ,F_{n})}$ forma um quasigrupo (com domínios restritos).

Variante a partir de ${\displaystyle a}$

Ver artigo principal: Função de Ackermann

Em 1928, Wilhelm Ackermann definiu uma função 3-argumentos ${\displaystyle \phi (a,b,n)}$ que evoluiu gradualmente para uma função de dois argumentos, conhecida como a função de Ackermann. A função de Ackermann original ${\displaystyle \phi }$ era menos semelhante as modernas hiperoperações, porque suas condições iniciais começavam com ${\displaystyle \phi (a,0,n)=a}$ para todo ${\displaystyle n>2}$. Ele também atribuiu adição a ${\displaystyle (n=0)}$, multiplicação a ${\displaystyle (n=1)}$ e exponenciação a ${\displaystyle (n=2)}$, assim as condições iniciais produzem operações muito diferentes para Tetração e além.

n	Operação	Comentário
0	${\displaystyle F_{0}(a,b)=a+b}$
1	${\displaystyle F_{1}(a,b)=a\cdot b}$
2	${\displaystyle F_{2}(a,b)=a^{b}}$
3	${\displaystyle F_{3}(a,b)=a\uparrow \uparrow (b+1)}$	Uma forma de deslocar a tetração. A iteração dessa operação é muito diferente da iteração da tetração.
4	${\displaystyle F_{4}(a,b)=(x\to a\uparrow \uparrow (x+1))^{b}(a)}$	Não deve ser confundida com pentação.

Outra condição inicial que tem sido utilizada é ${\displaystyle A(0,b)=2b+1}$ (onde a base é constante ${\displaystyle a=2}$), devido à Rózsa Péter, o que não forma uma hierarquia de hiperoperações.

Variante a partir de 0

Em 1984, C. W. Clenshaw e F. W. J. Olver iniciaram a discussão do uso de hiperoperações para evitar overflow em operações de ponto-flutuante em computadores[15]. Desde então, muitos outros autores[16][17][18] têm um interesse renovado na aplicação de hiperoperações para representação de ponto-flutuante.

Enquanto discutindo tetração, Clenshaw et al. assumiram a condição inicial ${\displaystyle F_{n}(a,0)=0}$, o que faz ainda outra hierarquia de hiperoperações. Assim como na variante anterior, a quarta operação é muito semelhante a tetração, mas deslocada por um.

n	Operação	Comentário
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a\uparrow \uparrow (b-1)}$	Uma forma deslocada de tetração. A iteração desta operação é muito diferente do que a iteração da tetração.
5	${\displaystyle F_{5}(a,b)=(x\to a\uparrow \uparrow (x-1))^{b}(0)}$	Não deve ser confundida com pentação.

Hiperoperações comutativas

Hiperoperações comutativas foram considerados por Albert Bennett tão cedo quanto 1914,[6] que é possivelmente a mais antiga observação sobre qualquer seqüência de hiperoperações. Hiperoperações comutativas são definidas pela regra de recursão

${\displaystyle F_{n+1}(a,b)=\exp(F_{n}(\ln(a),\ln(b)))}$

que é simétrica em a e b, significando que todas as hiperoperações são comutativas. Esta seqüência não contém exponenciação, e assim não formam uma hierarquia de hiperoperações.

n	Operação	Comentário
0	${\displaystyle F_{0}(a,b)=\ln(e^{a}+e^{b})}$
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$	Isto é devido as propriedades do logaritmo.
3	${\displaystyle F_{3}(a,b)=e^{\ln(a)\ln(b)}}$	Uma forma comutativa de exponenciação.
4	${\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}$	Não deve ser confundida com a tetração.

Hiperoperações balanceadas

Hiperoperações balanceadas, em primeiro lugar consideradas por Clément Frappier, em 1991,[19] são baseadas na iteração da função ${\displaystyle x^{x}}$, e são, portanto, relacionados com a notação de Steinhaus-Moser. A regra de recursão usada em hiperoperações balanceadas é

${\displaystyle F_{n+1}(a,b)=(x\to F_{n}(x,x))^{\log _{2}(b)}(a)}$

que exige contínuas iterações, mesmo para o inteiro b.

n	Operação	Comentário
0		A categoria 0 não existe.[nb 1]
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=a2^{\log _{2}(b)}}$
3	${\displaystyle F_{3}(a,b)=a^{b}=a^{2^{\log _{2}(b)}}}$	Esta é exponenciação.
4	${\displaystyle F_{4}(a,b)=(x\to x^{x})^{\log _{2}(b)}(a)}$	Não deve ser confundida com a tetração.

Hiperoperações baixas

Uma alternativa para estas hiperoperações é obtida pela avaliação da esquerda para a direita. Uma vez que

• ${\displaystyle a+b=(a+(b-1))+1}$
• ${\displaystyle a\cdot b=(a\cdot (b-1))+a}$
• ${\displaystyle a^{b}=(a^{(b-1)})\cdot a}$

define (com ° ou subscrito) ${\displaystyle a_{(n+1)}b=(a_{(n+1)}(b-1))_{(n)}a}$ com ${\displaystyle a_{(1)}b=a+b}$, ${\displaystyle a_{(2)}0=0}$, and ${\displaystyle a_{(n)}0=1}$ para ${\displaystyle n>2}$

Mas este sofre uma espécie de colapso, falhando em formar uma "torre de potências" tradicionalmente esperada de hyper4: ${\displaystyle a_{(4)}b=a^{(a^{(b-1)})}}$

Como pode ${\displaystyle a^{(n)}b}$ ser tão diferente de ${\displaystyle a_{(n)}b}$ para n>3? Isto se deve a uma simetria chamada associatividade que está definida dentro do + e do × (ver corpo) mas que falta no ^. É mais apto dizer que os dois (n)s foram decretados ser o mesmo para n<4. (Por outro lado, pode-se objetar que as operações de corpo foram definidas para imitar o que tinha sido "observado na natureza" e perguntar por que a "natureza" de repente, cria objeção para que a simetria...)

Os outros graus não colapsam desta forma, e por isso esta família tem algum interesse próprio em si como hiperoperações baixas (talvez menores ou inferiores). Com hiperfunções superiores a três, é também baixo no sentido de que as respostas que você recebe são, na verdade, muitas vezes muito mais baixas do que as respostas que você obtém quando se usa o método padrão.

n	Operação	Comentário
0	${\displaystyle b+1}$	incremento, sucessor, zeração
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$	Esta é a exponenciação.
4	${\displaystyle F_{4}(a,b)=a^{a^{(b-1)}}}$	Não deve ser confundida com a tetração.
5	${\displaystyle F_{5}(a,b)=(x\to x^{x^{(a-1)}})^{b-1}(a)}$	Não deve ser confundida com a pentação.

Notas

1. Se houvesse uma hiperoperação balanceada categoria 0 ${\displaystyle f(a,b)}$, então a adição seria ${\displaystyle a+b=(x\to f(x,x))^{\log _{2}(b)}(a)}$. Substituindo ${\displaystyle b=1}$ nesta equação dá ${\displaystyle a+1=(x\to f(x,x))^{0}(a)=a}$ o que é uma contradição.

Referências

1. «What lies beyond exponentiation?». 2003. Consultado em 17 de abril de 2009 
2. «Ackermann's Function and New Arithmetical Operation». 2005. Consultado em 17 de abril de 2009 
3. R. L. Goodstein (dezembro de 1947). «Transfinite Ordinals in Recursive Number Theory». Journal of Symbolic Logic. 12 (4): 123-129. doi:10.2307/2266486. Consultado em 17 de abril de 2009 
4. G. F. Romerio (21 de janeiro de 2008). «Hyperoperations Terminology». Tetration Forum. Consultado em 21 de abril de 2009 
5. I. N. Galidakis (2003). «Mathematics». Consultado em 17 de abril de 2009. Arquivado do original em 20 de abril de 2009 
6. Albert A. Bennett (dezembro de 1915). «Note on an Operation of the Third Grade». Annals of Mathematics, Second Series. 17 (2): 74-75. Consultado em 17 de abril de 2009 
7. Wilhelm Ackermann (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Mathematische Annalen. 99: 118-133. doi:10.1007/BF01459088 
8. Paul E. Black (30 de setembro de 1988). «Ackermann's function». Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Consultado em 17 de abril de 2009. Arquivado do original em 22 de abril de 2009 
9. Robert Munafo (3 de novembro de 1999). «Versions of Ackermann's Function». Large Numbers at MROB. Consultado em 17 de abril de 2009 
10. J. Cowles and T. Bailey (30 de setembro de 1988). «Several Versions of Ackermann's Function». Dept. of Computer Science, University of Wyoming, Laramie, WY. Consultado em 17 de abril de 2009 
11. Donald E. Knuth (1976). «Mathematics and Computer Science: Coping with Finiteness». Science. 194 (4271). pp. 1235–1242. PMID 17797067. doi:10.1126/science.194.4271.1235. Consultado em 21 de abril de 2009 
12. Zwillinger, Daniel (2002). CRC standard mathematical tables and formulae 31ª ed. [S.l.]: CRC Press. p. 4. ISBN 1-58488291-3 
13. Weisstein, Eric W. (2003). CRC concise encyclopedia of mathematics 2ª ed. [S.l.]: CRC Press. pp. 127–128. ISBN 1-58488347-2 
14. K. K. Nambiar (1995). «Ackermann Functions and Transfinite Ordinals». Applied Mathematics Letters. 8 (6). pp. 51–53. doi:10.1016/0893-9659(95)00084-4. Consultado em 21 de abril de 2009 
15. CLENSHAW, C. W.; OLIVER, F.W.J. (1984). «Beyond floating point». Journal of the ACM. 31 (2). pp. 319–328. doi:10.1145/62.322429. Consultado em 21 de abril de 2009  !CS1 manut: Nomes múltiplos: lista de autores (link)
16. HOLMES, W. N. (1997). «Composite Arithmetic: Proposal for a New Standard». Computer. 30 (3). pp. 65–73. doi:10.1109/2.573666. Consultado em 21 de abril de 2009 
17. ZIMMERMANN, R. (1997). «Computer Arithmetic: Principles, Architectures, and VLSI Design» (PDF). Lecture notes, Integrated Systems Laboratory, ETH Zürich. Consultado em 17 de abril de 2009 
18. PINKIEWICZ, T.; HOLMES, N.; JAMIL, T. (2000). «Design of a composite arithmetic unit for rational numbers». Proceedings of the IEEE. pp. 245–252. Consultado em 17 de abril de 2009  !CS1 manut: Nomes múltiplos: lista de autores (link)
19. FRAPPIER, C. (1991). «Iterations of a kind of exponentials». Fibonacci Quarterly. 29 (4). pp. 351–361