Hiperoperação

Na matemática , as hiperoperações (ou hiperoperadores ) constituem uma série infinita de operações que logicamente estende a série das seguintes operações aritméticas elementares:

adição (n = 1): ${\ displaystyle {{H_ {1} (a, b) = a + b} \ em cima \,} {= \ em cima \,} {a \, + \ em cima \,} {{\ underbrace {1 + 1 + \ cdots +1}} \ atop b {\ text {terms}}}}$
multiplicação (n = 2): ${\ displaystyle {{H_ {2} (a, b) = a \ times b = \} \ atop {\}} {{\ underbrace {a + a + \ cdots + a}} \ atop b {\ text { termos}}}}$
exponenciação (n = 3): ${\ displaystyle {{H_ {3} (a, b) = a ^ {b} = \} \ atop {\}} {{\ underbrace {a \ times a \ times \ cdots \ times a}} \ atop b {\ text {fatores}}}}$

Reuben Goodstein propôs batizar as operações além da exponenciação usando prefixos gregos: tetration ( n = 4), pentation ( n = 5), hexation ( n = 6), etc. A hiperoperação na ordem n pode ser observada usando uma seta de Knuth na classificação n - 2 . ${\ displaystyle H_ {n} (a, b) = a \ uparrow ^ {n-2} b}$

A flecha de Knuth no posto m é recursivamente definida por: e ${\ displaystyle a \ uparrow ^ {- 1} b = a + b \,}$ ${\ displaystyle a \ uparrow ^ {m} b = \ underbrace {a \ uparrow ^ {m-1} \ left (a \ uparrow ^ {m-1} \ left [a \ uparrow ^ {m-1} \ left (\ ldots \ left [a \ uparrow ^ {m-1} \ left (a \ uparrow ^ {m-1} a \ right) \ right] \ ldots \ right) \ right] \ right)} _ {\ displaystyle b {\ mbox {cópias de}} a}, \ quad m \ geq 0}$

Ele também pode ser definido usando a regra . Cada um cresce mais rápido que o anterior. ${\ displaystyle a \ uparrow ^ {m} b = a \ uparrow ^ {m-1} \ left (a \ uparrow ^ {m} (b-1) \ right)}$

Suítes semelhantes carregaram historicamente vários nomes, como função de Ackermann (3 pontos), a hierarquia de Ackermann , a hierarquia Grzegorczyk (mais geralmente), a versão de Goodstein da função de Ackermann , hiper- n .

Definição

A sequência do hiperoperador é a sequência de operações binárias indexadas por , definidas recursivamente da seguinte forma: ${\ displaystyle H_ {n}: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N}}$ $n \ in \ N$

{\ displaystyle H_ {n} (a, b) = {\ begin {cases} b + 1 & {\ text {si}} n = 0 \\ a & {\ text {si}} n = 1, b = 0 \ \ 0 & {\ text {si}} n = 2, b = 0 \\ 1 & {\ text {si}} n \ geq 3, b = 0 \\ H_ {n-1} (a, H_ {n} (a, b-1)) & {\ text {caso contrário}} \ end {casos}}}

(Nota: para n = 0, podemos ignorar o primeiro argumento, porque então o hiperoperador consiste simplesmente em incrementar o segundo argumento em uma unidade: sucessão.)

Para n = 0, 1, 2, 3, esta definição reproduz as operações aritméticas elementares, na ordem: sucessão, adição, multiplicação, exponenciação. Por convenção, portanto, as operações aritméticas elementares também devem ser consideradas como hiperoperadores.

Para n ≥ 4, esta sequência continua com novas operações.

Aqui está a lista das 7 primeiras hiperoperações:

não	$H_n$	Cirurgia	Definição	Nomes	Áreas de validade
0	$H_ {0} (a, b)$	$b + 1$	${1 + {\ underbrace {1 + 1 + 1 + \ cdots +1} _ {{b}}}}$	sucessor , "zeração"	b real
1	$H_ {1} (a, b)$	$a + b$	${a + {\ underbrace {1 + 1 + 1 + \ cdots +1} _ {{b}}}}$	Adição	a e b reais
2	$H_ {2} (a, b)$	$a \ cdot b$	${{\ underbrace {a + a + a + \ cdots + a}} \ atop {b}}$	multiplicação	a e b reais
3	$H_ {3} (a, b)$	$a \ uparrow b = a ^ {b}$	${{\ underbrace {a \ cdot a \ cdot a \ cdot a \ cdot \ ldots \ cdot a}} \ atop {b}}$	exponenciação	a > 0, b real, ou um não-zero, b um inteiro. Extensões no conjunto de números complexos .
4	$H_ {4} (a, b)$	${\ displaystyle a \ uparrow \ uparrow b = \ ^ {b} a}$	${{\ underbrace {a \ uparrow a \ uparrow a \ uparrow \ cdots \ uparrow a}} \ atop {b}}$	tetração	a > 0, b inteiro ≥ −1 (extensões propostas)
5	$H_ {5} (a, b)$	$a \ uparrow \ uparrow \ uparrow b$ ou $a \ uparrow ^ {3} b$	${{\ underbrace {a \ uparrow \ uparrow a \ uparrow \ uparrow \ cdots \ uparrow \ uparrow a}} \ atop {b}}$	pentation	a e b inteiros, a > 0, b ≥ 0
6	$H_ {6} (a, b)$	$a \ uparrow ^ {4} b$	${{\ underbrace {a \ uparrow ^ {3} a \ uparrow ^ {3} \ cdots \ uparrow ^ {3} a}} \ atop {b}}$	hexação	a e b inteiros, a > 0, b ≥ 0

Casos especiais

H n (0, b ) =

0, onde n = 2, ou n = 3, b ≥ 1, ou n ≥ 4, b ímpar (≥ −1) 1, onde n = 3, b = 0 ou n ≥ 4, b mesmo (≥ 0) b , onde n = 1 b + 1, onde n = 0

H n ( a , 0) =

0, onde n = 2 1, onde n = 0 ou n ≥ 3 a , onde n = 1

H n ( a , -1) =

0, onde n = 0 ou n ≥ 4 a - 1, onde n = 1 - a , onde n = 2

1 / no

, onde n = 3

H n ( 2, 2 ) =

3, onde n = 0 4, onde n ≥ 1, facilmente demonstrável por indução.

História

Uma das primeiras discussões em torno dos hiperoperadores foi a de Albert Bennet em 1914, que desenvolveu a teoria das hiperoperações comutativas .

12 anos depois, Wilhelm Ackermann define a função que se aproxima da sequência de hiperoperadores. ${\ displaystyle \ phi (a, b, n)}$

Em seu artigo de 1947, Reuben Goodstein introduziu a sequência de operações agora chamadas de hiperoperações e sugeriu os nomes de tetração , pentação , etc. para operações além da exponenciação (porque correspondem aos índices 4, 5, etc. abaixo). É uma função com três argumentos :, a sequência de hiperoperações pode ser comparada à função de Ackermann . A função de Ackermann original usa a mesma regra recursiva de Goodstein, mas difere dela de duas maneiras: primeiro, define uma série de operações começando da adição ( n = 0) ao invés da sucessão. Então, as condições iniciais para são diferentes daquelas de hiperoperações além da exponenciação. O significado de b + 1 na expressão anterior é = , onde b conta o número de operadores em vez do número de operandos a , assim como b em , etc, para operações de nível superior (consulte a função Ackermann para obter mais detalhes). ${\ displaystyle G (n, a, b) = H_ {n} (a, b)}$ ${\ displaystyle \ phi (a, b, n)}$ $\ phi$ ${\ displaystyle \ phi (a, b, n)}$ $\ phi$ ${\ displaystyle \ phi (a, b, 3) = a \ uparrow \ uparrow (b + 1)}$ ${\ displaystyle \ phi (a, b, 3)}$ ${\ displaystyle a ^ {a ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {a}}}}}}$ ${\ displaystyle a \ uparrow \ uparrow b}$

Notações

Muitas notações foram desenvolvidas e são aplicáveis a hiperoperadores.

Sobrenome	Notação equivalente a ${\ displaystyle H_ {n} (a, b)}$	Comente
Notação de flechas de Knuth	${\ displaystyle a \ uparrow ^ {n-2} b}$	Usado por Knuth (para n ≥ 2) e encontrado em vários trabalhos.
Notação de Goodstein	${\ displaystyle G (n, a, b)}$	Usado por Reuben Goodstein .
Função Ackermann original	${\ displaystyle {\ begin {matrix} \ phi (a, b, n-1) \ {\ text {for}} 1 \ leq n \ leq 3 \\\ phi (a, b-1, n-1) \ {\ text {para}} n> 3 \ end {matriz}}}$	Usado por Wilhelm Ackermann .
Função de Ackermann - Peido	${\ displaystyle A (n, b-3) +3 \ {\ text {for}} a = 2}$	Isso corresponde às hiperoperações de base 2 ( ). ${\ displaystyle H_ {n} (2, b)}$
Notação Nambiar	${\ displaystyle a \ otimes ^ {n} b}$	Usado por Nambiar
Notação de caixa	${\ displaystyle a {\, {\ begin {array} {\| c \|} \ hline {\! n \!} \\\ hline \ end {array}} \,} b}$	Usado por Rubtsov e Romerio.
Notação expoente	${\ displaystyle a {} ^ {(n)} b}$	Usado por Robert Munafo.
Avaliação do índice	${\ displaystyle a {} _ {(n)} b}$	Usado por John Donner e Alfred Tarski (para n ≥ 1).
Parênteses de notação	${\ displaystyle a [n] b}$	Usado em fóruns, para simplificar.
Notação de setas em cadeia de Conway	${\ displaystyle a \ rightarrow b \ rightarrow (n-2)}$	Usado por John Horton Conway (para n ≥ 3).
Notação de Bowers	${\ displaystyle \ {a, b, n, 1 \}}$	Usado por Jonathan Bowers (para n ≥ 1).

Variante inicial de um

Em 1928, Wilhelm Ackermann definiu uma função de 3 argumentos que gradualmente evoluiu para uma função de 2 argumentos conhecida como função de Ackermann . A função de Ackermann original era menos semelhante às hiperoperações modernas, uma vez que suas condições iniciais começam com para todo n > 2. Além disso , a adição é atribuída a n = 0, a multiplicação para n = 1 e a exponenciação para n = 2., de modo que o as condições iniciais produzem operações muito diferentes da tetração e das hiperoperações subsequentes. ${\ displaystyle \ phi (a, b, n)}$ $\ phi$ ${\ displaystyle \ phi (a, 0, n) = a}$

não	Cirurgia	Comente
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)}$	A iteração desta operação é diferente da iteração da tetração.
4	${\ displaystyle F_ {4} (a, b) = (x \ mapsto a \ uparrow \ uparrow (x + 1)) ^ {b} (a)}$	Não deve ser confundido com pentation .

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

Variante inicial de 0

Em 1984, CW Clenshaw e FWJ Olver começaram a discutir o uso de hiperoperações para evitar um erro de computador de ponto flutuante . Desde então, muitos outros autores tiveram interesse na aplicação de hiperoperações para representação de ponto flutuante (porque H n ( a , b ) são todos definidos para b = –1). Ao discutir a tetração , Clenshaw et al. suportado a condição inicial , e executada Ainda outro hierarquia de hiperoperação. Como na variante anterior, a quarta operação é muito semelhante à tetração, mas é diferente dela. ${\ displaystyle F_ {n} (a, 0) = 0}$

não	Cirurgia	Comente
0	${\ displaystyle F_ {0} (a, b) = b + 1}$
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)}$	A iteração desta operação é diferente da iteração da tetration.
5	${\ displaystyle F_ {5} (a, b) = \ left (x \ mapsto a \ uparrow \ uparrow (x-1) \ right) ^ {b} (0) = 0 {\ text {si}} a> 0}$	Não deve ser confundido com Pentation .

Veja também

Referências

( fr ) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Hyperoperation " ( veja a lista de autores ) .

(en) Daniel Geisler, “ o que está além exponenciação? " ,2003(acessado em 17 de abril de 2009 ) .
(em) AJ Robbins, " Home of tetration " ,novembro de 2005(acessado em 17 de abril de 2009 )
(en) CA Rubtsov e GF Romerio, " Função de Ackermann e Nova Operação Aritmética " ,dezembro de 2005(acessado em 17 de abril de 2009 ) .
(en) RL Goodstein, “ Transfinite ordinals in recursive number theory ” , Journal of Symbolic Logic , vol. 12, n o 4,1947, p. 123-129 ( DOI 10.2307 / 2266486 , JSTOR 2266486 ).
(em) Harvey Friedman, " Long Finite Sequences " , Journal of Combinatorial Theory, Series A , vol. 95, n o 1,2001, p. 102-144 ( DOI 10.1006 / jcta.2000.3154 , ler online , acessado em 17 de abril de 2009 ).
.
(em) Marc Wirz, " Characterizing the Grzegorczyk hierarchy by safe recursion " , CiteSeer,1999(acessado em 21 de abril de 2009 ) .
(em) Markus Müller, " Reihenalgebra " ,1993(acessado em 17 de abril de 2009 )
(en) Robert Munafo, " Inventing New Operators and Functions " , Large Numbers at MROB ,Novembro de 1999(acessado em 17 de abril de 2009 ) .
(em) IN Galidakis, " Matemática " ,2003(acessado em 17 de abril de 2009 ) .
(em) Albert Bennett, " one year Note Operation of the Third Grade " , Annals of Mathematics , 2 série E , vol. 17, n o 2Dezembro de 1915, p. 74-75 ( JSTOR 2007124 ).
(de) Wilhelm Ackermann, " Zum Hilbertschen Aufbau der reellen Zahlen ' " , Mathematische Annalen , vol. 99,1928, p. 118-133 ( DOI 10.1007 / BF01459088 ).
(in) Paul E. Black, " Ackermann's function " ( Arquivo • Wikiwix • Archive.is • Google • O que fazer? ) , Dicionário de Algoritmos e Estruturas de Dados , Instituto Nacional de Padrões e Tecnologia dos EUA (NIST)16 de março de 2009(acessado em 17 de abril de 2009 ) .
(em) Robert Munafo, " Versions of Ackermann's Function " , Large Numbers at MROB ,3 de novembro de 1999(acessado em 17 de abril de 2009 ) .
(em) J. Cowles e T. Bailey, " Várias versões da Função de Ackermann " , Dept. de Ciência da Computação, Universidade de Wyoming, Laramie, WY,30 de setembro de 1988(acessado em 17 de abril de 2009 ) .
(em) Donald E. Knuth, " Mathematics and Computer Science: Coping with finiteness " , Science , vol. 194, n o 4271,Dezembro de 1976, p. 1235-1242 ( PMID 17797067 , DOI 10.1126 / science.194.4271.1235 , ler online , acessado em 21 de abril de 2009 ).
(in) Daniel Zwillinger, CRC Standard Mathematical Tables and Formulas , Boca Raton, CRC Press ,2002, 31 th ed. ( ISBN 978-1-58488-291-6 ) , p. 4.
(em) Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics , Boca Raton, CRC Press ,2003, 2 nd ed. , 3242 p. ( ISBN 978-1-58488-347-0 , LCCN 2002074126 ) , p. 127-128.
(em) KK Nambiar, " Ackermann Functions and Transfinite ordinals " , Applied Mathematics Letters , vol. 8, n o 6,1995, p. 51-53 ( DOI 10.1016 / 0893-9659 (95) 00084-4 , lido online , acessado em 21 de abril de 2009 ).
(em) John Donner e Alfred Tarski, " Uma aritmética estendida dos números ordinais " , Fundamenta Mathematicae , vol. 65,1969, p. 95-127.
(em) CW Clenshaw e FWJ Olver, " Beyond floating point " , Journal of the ACM , vol. 31, n o 2 Abril de 1984, p. 319-328 ( DOI 10.1145 / 62.322429 , ler online ).
(em) WN Holmes, " Composite Arithmetic: Proposal for a New Standard " , Computer , vol. 30, n o 3, Março de 1997, p. 65-73 ( DOI 10.1109 / 2.573666 , ler online , acessado em 21 de abril de 2009 ).
(in) R. Zimmermann, " Computer Arithmetic: Principles, Architecture, and VLSI Design " , notas da aula, Laboratório de Sistemas Integrados, ETH Zürich, 1997(acessado em 17 de abril de 2009 ) .
(em) T. Pinkiewicz N. Holmes e T. Jamil, " Projeto de uma unidade aritmética composta para números racionais " , Proceedings of the IEEE,2000(acessado em 17 de abril de 2009 ) ,p. 245-252.