Generalización de la suma, multiplicación, exponenciación, tetración, etc.
En matemáticas , la secuencia de hiperoperaciones [nb 1] es una secuencia infinita de operaciones aritméticas (llamadas hiperoperaciones en este contexto) que comienza con una operación unaria (la función sucesora con n = 0). La secuencia continúa con las operaciones binarias de suma ( n = 1), multiplicación ( n = 2) y exponenciación ( n = 3).
Después de eso, la secuencia continúa con más operaciones binarias que se extienden más allá de la exponenciación, usando asociatividad por la derecha . Para las operaciones más allá de la exponenciación, Reuben Goodstein nombra el enésimo miembro de esta secuencia después del prefijo griego de n con el sufijo -ación (como tetración ( n = 4), pentación ( n = 5), hexación ( n = 6). ), etc.) y se puede escribir usando n − 2 flechas en la notación de flecha hacia arriba de Knuth . Cada hiperoperación puede entenderse recursivamente en términos de la anterior mediante:
También se puede definir según la parte de la definición de la regla de recursividad, como en la versión de flecha hacia arriba de la función de Ackermann de Knuth :
Esto se puede usar para mostrar fácilmente números mucho más grandes que los que puede mostrar la notación científica , como el número de Skewes y el googolplexplex (por ejemplo, es mucho mayor que el número de Skewes y el googolplexplex), pero hay algunos números que ni siquiera ellos pueden mostrar fácilmente, como el de Graham. número y ÁRBOL(3) .
Esta regla de recursividad es común a muchas variantes de hiperoperaciones.
Definición
Definición, más común
La secuencia de hiperoperación es la secuencia de operaciones binarias , definida recursivamente de la siguiente manera:
(Tenga en cuenta que para n = 0, la operación binaria esencialmente se reduce a una operación unaria ( función sucesora ) al ignorar el primer argumento).
Para n = 0, 1, 2, 3, esta definición reproduce las operaciones aritméticas básicas de sucesor (que es una operación unaria), suma , multiplicación y exponenciación , respectivamente, como
Las operaciones para n ≥ 3 se pueden escribir en la notación de flecha hacia arriba de Knuth .
Entonces, ¿cuál será la siguiente operación después de la exponenciación? Definimos la multiplicación de modo que y definimos la exponenciación de modo que parece lógico definir la siguiente operación, tetración, de modo que con una torre de tres 'a'. De manera análoga, la pentación de (a, 3) será tetración (a, tetración (a, a)), con tres "a" en ella.
La notación de Knuth podría extenderse a índices negativos ≥ −2 de tal manera que concuerde con toda la secuencia de hiperoperación, excepto por el retraso en la indexación:
Por tanto, las hiperoperaciones pueden verse como una respuesta a la pregunta "¿qué sigue" en la secuencia : sucesor , suma , multiplicación , exponenciación , etc. Señalando que
Se ilustra la relación entre las operaciones aritméticas básicas, lo que permite definir las operaciones superiores de forma natural como se indicó anteriormente. A veces se hace referencia a los parámetros de la jerarquía de hiperoperación mediante su término de exponenciación análogo; entonces a es la base , b es el exponente (o hiperexponente ), y n es el rango (o grado ), y además, se lee como "la b enésima n -ación de a " , por ejemplo, se lee como "la novena tetración de 7", y se lee como "la 789.a 123-ación de 456".
En términos comunes, las hiperoperaciones son formas de combinar números que aumentan en crecimiento en función de la iteración de la hiperoperación anterior. Los conceptos de sucesor, suma, multiplicación y exponenciación son todos hiperoperaciones; la operación sucesora (producir x + 1 a partir de x ) es la más primitiva, el operador de suma especifica el número de veces que se suma 1 a sí mismo para producir un valor final, la multiplicación especifica el número de veces que se suma un número en sí mismo, y la exponenciación se refiere al número de veces que un número debe multiplicarse por sí mismo.
Definición, usando iteración.
Defina la iteración de una función f de dos variables como
La secuencia de hiperoperación se puede definir en términos de iteración, de la siguiente manera. Para todos los números enteros define
Como la iteración es asociativa , la última línea se puede reemplazar por
Cálculo
Las definiciones de secuencia de hiperoperación pueden naturalmente transponerse al término sistemas de reescritura (TRS) .
TRS basado en la definición sub 1.1
La definición básica de la secuencia de hiperoperación se corresponde con las reglas de reducción.
Para calcular se puede utilizar una pila , que inicialmente contiene los elementos .
Luego, repetidamente hasta que ya no sea posible, se extraen tres elementos y se reemplazan según las reglas [nb 2]
Esquemáticamente, a partir de :
MIENTRAS longitud de pila <> 1{ POP 3 elementos; EMPUJE 1 o 5 elementos según las reglas r1, r2, r3, r4, r5;}
Ejemplo
Calcular .
La secuencia de reducción es [nb 2] [17]
Cuando se implementa usando una pila, en la entrada
TRS basado en la definición sub 1.2
La definición que utiliza iteración conduce a un conjunto diferente de reglas de reducción.
Como la iteración es asociativa , en lugar de la regla r11 se puede definir
Como en la sección anterior, el cálculo de se puede implementar utilizando una pila.
Inicialmente la pila contiene los cuatro elementos .
Luego, hasta la terminación, se extraen y reemplazan cuatro elementos según las reglas [nb 2]
Esquemáticamente, a partir de :
MIENTRAS longitud de pila <> 1{ POP 4 elementos; EMPUJE 1 o 7 elementos según las reglas r6, r7, r8, r9, r10, r11;}
Ejemplo
Calcular .
Al ingresar, se muestran las configuraciones de pila sucesivas.
Las igualdades correspondientes son
Cuando la regla de reducción r11 se reemplaza por la regla r12, la pila se transforma de acuerdo con
Las configuraciones de pila sucesivas serán entonces
Las igualdades correspondientes son
Observaciones
- es un caso especial. Vea abajo. [nota 3] [nota 4]
- El cálculo de acuerdo con las reglas {r6 - r10, r11} es muy recursivo. El culpable es el orden en que se ejecuta la iteración: . El primero desaparece sólo después de que se ha desarrollado toda la secuencia. Por ejemplo, converge a 65536 en 2863311767 pasos, la profundidad máxima de recursividad [18] es 65534.
- El cálculo según las reglas {r6 - r10, r12} es más eficaz a este respecto. La implementación de la iteración imita la ejecución repetida de un procedimiento H. [19] La profundidad de la recursividad, (n+1), coincide con el anidamiento del bucle. Meyer y Ritchie (1967) formalizaron esta correspondencia. El cálculo de acuerdo con las reglas {r6-r10, r12} también necesita 2863311767 pasos para converger en 65536, pero la profundidad máxima de recursividad es solo 5, ya que la tetración es el quinto operador en la secuencia de hiperoperación.
- Las consideraciones anteriores se refieren únicamente a la profundidad de la recursividad. Cualquier forma de iteración conduce al mismo número de pasos de reducción, que involucran las mismas reglas (cuando las reglas r11 y r12 se consideran "iguales"). Como muestra el ejemplo, la reducción de converge en 9 pasos: 1 X r7, 3 X r8, 1 X r9, 2 X r10, 2 X r11/r12. El modus iterandi sólo afecta al orden en que se aplican las reglas de reducción.
Ejemplos
A continuación se muestra una lista de las primeras siete (0.ª a 6.ª) hiperoperaciones ( 0⁰ se define como 1).
Casos especiales
H norte (0, segundo ) =
- b + 1, cuando n = 0
- b , cuando n = 1
- 0, cuando n = 2
- 1, cuando n = 3 y b = 0 [nb 3] [nb 4]
- 0, cuando n = 3 y b > 0 [nb 3] [nb 4]
- 1, cuando n > 3 y b es par (incluido 0)
- 0, cuando n > 3 y b es impar
H norte (1, b ) =
- b , cuando n = 2
- 1, cuando n ≥ 3
H norte ( a , 0) =
- 0, cuando n = 2
- 1, cuando n = 0, o n ≥ 3
- a , cuando n = 1
H norte ( a , 1 ) =
- a, cuando n ≥ 2
H norte ( a , a ) =
- H n+1 ( a , 2), cuando n ≥ 1
H norte ( a , −1) = [nb 5]
- 0, cuando n = 0, o n ≥ 4
- a − 1, cuando n = 1
- − a , cuando n = 2
- 1/a, cuando n = 3
H norte (2, 2) =
- 3, cuando n = 0
- 4, cuando n ≥ 1, fácilmente demostrable de forma recursiva.
Historia
Una de las primeras discusiones sobre hiperoperaciones fue la de Albert Bennett en 1914, quien desarrolló parte de la teoría de las hiperoperaciones conmutativas (ver más abajo). Aproximadamente 12 años después, Wilhelm Ackermann definió la función que se parece un poco a la secuencia de hiperoperación.
En su artículo de 1947, Reuben Goodstein introdujo la secuencia específica de operaciones que ahora se llaman hiperoperaciones , y también sugirió los nombres griegos tetración , pentación, etc., para las operaciones extendidas más allá de la exponenciación (porque corresponden a los índices 4, 5, etcétera). Como función de tres argumentos, por ejemplo , la secuencia de hiperoperación en su conjunto se considera una versión de la función original de Ackermann ( recursiva pero no recursiva primitiva ) modificada por Goodstein para incorporar la función sucesora primitiva junto con las otras tres funciones básicas. operaciones de aritmética ( suma , multiplicación , exponenciación ) y hacer una extensión más fluida de estas más allá de la exponenciación.
La función original de Ackermann de tres argumentos utiliza la misma regla de recursividad que la versión de Goodstein (es decir, la secuencia de hiperoperación), pero difiere de ella en dos formas. Primero, define una secuencia de operaciones a partir de la suma ( n = 0) en lugar de la función sucesora , luego la multiplicación ( n = 1), la exponenciación ( n = 2), etc. En segundo lugar, las condiciones iniciales para el resultado son , por lo que difieren de las hiperoperaciones más allá de la exponenciación. El significado de b + 1 en la expresión anterior es que = , donde b cuenta el número de operadores (exponenciaciones), en lugar de contar el número de operandos ("a") como lo hace el b en , y así sucesivamente para las operaciones de nivel superior. (Consulte el artículo sobre la función de Ackermann para obtener más detalles).
Notaciones
Esta es una lista de notaciones que se han utilizado para hiperoperaciones.
Variante a partir de un
En 1928, Wilhelm Ackermann definió una función de 3 argumentos que gradualmente evolucionó hasta convertirse en una función de 2 argumentos conocida como función de Ackermann . La función de Ackermann original era menos similar a las hiperoperaciones modernas, porque sus condiciones iniciales comienzan con para todo n > 2. También asignó la suma a n = 0, la multiplicación a n = 1 y la exponenciación a n = 2, por lo que las condiciones iniciales producen muy diferentes operaciones para tetración y más.
Otra condición inicial que se ha utilizado es (donde la base es constante ), debido a Rózsa Péter , que no forma una jerarquía de hiperoperaciones.
Variante a partir de 0
En 1984, CW Clenshaw y FWJ Olver comenzaron a discutir el uso de hiperoperaciones para evitar desbordamientos de punto flotante en la computadora .
Desde entonces, muchos otros autores han renovado el interés en la aplicación de hiperoperaciones a la representación de punto flotante . (Dado que H n ( a , b ) están todos definidos para b = -1.) Mientras analiza la tetración , Clenshaw et al. asumió la condición inicial , lo que crea otra jerarquía de hiperoperación. Al igual que en la variante anterior, la cuarta operación es muy similar a la tetración , pero compensada en uno.
Hiperoperaciones más bajas
Una alternativa para estas hiperoperaciones se obtiene evaluando de izquierda a derecha. Desde
definir (con ° o subíndice)
con
Doner y Tarski ampliaron esto a los números ordinales, mediante:
De la Definición 1(i), el Corolario 2(ii) y el Teorema 9 se deduce que, para a ≥ 2 y b ≥ 1, que [ ¿investigación original? ]
Pero esto sufre una especie de colapso, no logrando formar la "torre de energía" que tradicionalmente se espera de los hiperoperadores: [nb 6]
Si α ≥ 2 y γ ≥ 2, [Corolario 33(i)] [nb 6]
Hiperoperaciones conmutativas
Las hiperoperaciones conmutativas fueron consideradas por Albert Bennett ya en 1914, lo que posiblemente sea la observación más temprana sobre cualquier secuencia de hiperoperación. Las hiperoperaciones conmutativas están definidas por la regla de recursividad.
que es simétrico en a y b , lo que significa que todas las hiperoperaciones son conmutativas. Esta secuencia no contiene exponenciación y, por lo tanto, no forma una jerarquía de hiperoperaciones.
Sistemas de numeración basados en la secuencia de hiperoperación.
RL Goodstein utilizó la secuencia de hiperoperadores para crear sistemas de numeración para los números enteros no negativos. La llamada representación hereditaria completa del número entero n , en el nivel k y en base b , se puede expresar de la siguiente manera usando solo los primeros k hiperoperadores y usando como dígitos solo 0, 1, ..., b − 1, junto con la base b mismo:
- Para 0 ≤ n ≤ b − 1, n se representa simplemente por el dígito correspondiente.
- Para n > b − 1, la representación de n se encuentra recursivamente, representando primero n en la forma
- segundo [ k ] x k [ k − 1] x k − 1 [ k - 2] ... [2] x 2 [1] x 1
- donde x k , ..., x 1 son los números enteros más grandes que satisfacen (a su vez)
- segundo [ k ] x k ≤ norte
- segundo [ k ] x k [ k − 1] x k − 1 ≤ norte
- ...
- segundo [ k ] x k [ k − 1] x k − 1 [ k - 2] ... [2] x 2 [1] x 1 ≤ n
- Cualquier x i que exceda b − 1 se reexpresa de la misma manera, y así sucesivamente, repitiendo este procedimiento hasta que la forma resultante contenga solo los dígitos 0, 1, ..., b − 1, junto con la base b .
Se pueden evitar paréntesis innecesarios dando mayor prioridad a los operadores de nivel superior en el orden de evaluación; de este modo,
- las representaciones de nivel 1 tienen la forma b [1] X, siendo X también de esta forma;
- las representaciones de nivel 2 tienen la forma b [2] X [1] Y, siendo X , Y también de esta forma;
- las representaciones de nivel 3 tienen la forma b [3] X [2] Y [1] Z, siendo X , Y , Z también de esta forma;
- las representaciones de nivel 4 tienen la forma b [4] X [3] Y [2] Z [1] W, siendo X , Y , Z , W también de esta forma;
etcétera.
En este tipo de representación hereditaria en base b , la propia base aparece en las expresiones, así como los "dígitos" del conjunto {0, 1, ..., b − 1}. Esto se compara con la representación ordinaria de base 2 cuando esta última se escribe en términos de base b ; por ejemplo, en notación ordinaria de base 2, 6 = (110) 2 = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, mientras que la representación hereditaria de nivel 3 base 2 es 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [ 1] 0). Las representaciones hereditarias se pueden abreviar omitiendo cualquier instancia de [1] 0, [2] 1, [3] 1, [4] 1, etc.; por ejemplo, la representación de nivel 3 base 2 anterior de 6 se abrevia a 2 [3] 2 [1] 2.
Ejemplos: Las representaciones únicas en base 2 del número 266 , en los niveles 1, 2, 3, 4 y 5 son las siguientes:
- Nivel 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (con 133 2s)
- Nivel 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)
- Nivel 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2
- Nivel 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2
- Nivel 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2
Ver también
Wikimedia Commons tiene medios relacionados con Hiperoperaciones .
Notas
- ^ Históricamente , las secuencias similares a la secuencia de hiperoperación han recibido muchos nombres, entre ellos: la función de Ackermann (3 argumentos), la jerarquía de Ackermann , la jerarquía de Grzegorczyk (que es más general), la versión de Goodstein de la función de Ackermann , operación de enésimo grado , exponenciación iterada de x con y , operaciones de flecha , reihenalgebra e hiper-n .
- ^ abc Esto implementa la estrategia más interna a la izquierda (un paso) .
- ^ abc Para obtener más detalles, consulte Potencias de cero .
- ^ abc Para obtener más detalles, consulte Cero elevado a cero .
- ^ abc Sea x = a [ n ](−1). Según la fórmula recursiva, a [ n ]0 = a [ n − 1]( a [ n ](−1)) ⇒ 1 = a [ n − 1] x . Una solución es x = 0, porque a [ n − 1]0 = 1 por definición cuando n ≥ 4. Esta solución es única porque a [ n − 1] b > 1 para todo a > 1, b > 0 (prueba por recursión).
- ^ ab La suma ordinal no es conmutativa; ver aritmética ordinal para más información
Referencias
- ^ En cada paso se reescribe la redex subrayada .
- ^ La profundidad máxima de recursividad se refiere al número de niveles de activación de un procedimiento que existen durante la llamada más profunda del procedimiento. Cornelio y Kirby (1975)
- ^ BUCLE n VECES HACER H.
Bibliografía
- Bennett, Albert A. (diciembre de 1915). "Nota sobre una operación de tercer grado". Anales de Matemáticas . Segunda Serie. 17 (2): 74–75. doi :10.2307/2007124. JSTOR 2007124.
- Bezem, Marc; Klop, Jan Willem; De Vrijer, Roel (2003). "Sistemas de reescritura de términos de primer orden". Sistemas de reescritura de términos por "Terese" . Prensa de la Universidad de Cambridge. págs. 38–39. ISBN 0-521-39115-6.
- Campagnola, Manuel Lameiras; Moore, Cristopher ; Félix Costa, José (diciembre de 2002). "Ordinales transfinitos en teoría de números recursivos". Revista de Complejidad . 18 (4): 977–1000. doi : 10.1006/jcom.2002.0655 .
- Clenshaw, CW; Olver, FWJ (abril de 1984). "Más allá del punto flotante". Revista de la ACM . 31 (2): 319–328. doi : 10.1145/62.322429 . S2CID 5132225.
- Cornelio, BJ; Kirby, GH (1975). "Profundidad de recursividad y función de Ackermann". BIT Matemáticas Numéricas . 15 (2): 144-150. doi :10.1007/BF01932687. S2CID 120532578.
- Cowles, J.; Bailey, T. (30 de septiembre de 1988). "Varias versiones de la función de Ackermann". Departamento de Ciencias de la Computación, Universidad de Wyoming, Laramie, WY . Consultado el 29 de agosto de 2021 .
- Döner, John; Tarski, Alfred (1969). "Una aritmética ampliada de números ordinales". Fundamentos Mathematicae . 65 : 95-127. doi : 10.4064/fm-65-1-95-127 .
- Friedman, Harvey M. (julio de 2001). "Secuencias finitas largas". Revista de teoría combinatoria . Serie A. 95 (1): 102–144. doi : 10.1006/jcta.2000.3154 .
- Galidakis, IN (2003). "Matemáticas". Archivado desde el original el 20 de abril de 2009 . Consultado el 17 de abril de 2009 .
- Geisler, Daniel (2003). "¿Qué hay más allá de la exponenciación?" . Consultado el 17 de abril de 2009 .
- Goodstein, Reuben Louis (diciembre de 1947). "Ordinales transfinitos en teoría de números recursivos". Revista de Lógica Simbólica . 12 (4): 123–129. doi :10.2307/2266486. JSTOR 2266486. S2CID 1318943.
- Hilbert, David (1926). "Über das Unendliche". Annalen Matemáticas . 95 : 161-190. doi :10.1007/BF01206605. S2CID 121888793.
- Holmes, WN (marzo de 1997). "Aritmética compuesta: propuesta de un nuevo estándar". Computadora . 30 (3): 65–73. doi : 10.1109/2.573666 . Consultado el 21 de abril de 2009 .
- Knuth, Donald Ervin (diciembre de 1976). "Matemáticas e Informática: afrontar la finitud". Ciencia . 194 (4271): 1235-1242. Código Bib : 1976 Ciencia... 194.1235K. doi : 10.1126/ciencia.194.4271.1235. PMID 17797067. S2CID 1690489 . Consultado el 21 de abril de 2009 .
- Littlewood, JE (julio de 1948). "Números grandes". Gaceta Matemática . 32 (300): 163-171. doi :10.2307/3609933. JSTOR 3609933. S2CID 250442130.
- Müller, Markus (1993). "Reihenalgebra" (PDF) . Consultado el 6 de noviembre de 2021 .
- Munafo, Robert (1999a). "Versiones de la función de Ackermann". Grandes números en MROB . Consultado el 28 de agosto de 2021 .
- Munafo, Robert (1999b). "Inventar nuevos operadores y funciones". Grandes números en MROB . Consultado el 28 de agosto de 2021 .
- Nambiar, KK (1995). "Funciones de Ackermann y ordinales transfinitos". Letras de Matemática Aplicada . 8 (6): 51–53. doi : 10.1016/0893-9659(95)00084-4 .
- Pinkiewicz, T.; Holmes, N.; Jamil, T. (2000). "Diseño de una unidad aritmética compuesta para números racionales". Actas de IEEE Southeast Con 2000. 'Preparándose para el nuevo milenio' (Cat. No.00CH37105) . Actas del IEEE. págs. 245-252. doi :10.1109/SECON.2000.845571. ISBN 0-7803-6312-4. S2CID 7738926.
- Robbins, AJ (noviembre de 2005). "Hogar de la Tetración". Archivado desde el original el 13 de junio de 2015 . Consultado el 17 de abril de 2009 .
- Romerio, GF (21 de enero de 2008). "Terminología de hiperoperaciones". Foro de tetración . Consultado el 21 de abril de 2009 .
- Rubtsov, California; Romerio, GF (diciembre de 2005). "Función de Ackermann y nueva operación aritmética" . Consultado el 17 de abril de 2009 .
- Townsend, Adam (12 de mayo de 2016). "Nombres para grandes números". Revista Polvo de tiza .
- Weisstein, Eric W. (2003). Enciclopedia concisa de matemáticas CRC, segunda edición . Prensa CRC. págs. 127-128. ISBN 1-58488-347-2.
- Wirz, Marc (1999). "Caracterización de la jerarquía de Grzegorczyk mediante recursividad segura" (PDF) . Berna: Institut für Informatik und angewandte Mathematik. CiteSeerX 10.1.1.42.3374 . S2CID 117417812.
- Zimmermann, R. (1997). "Aritmética informática: principios, arquitecturas y diseño VLSI" (PDF) . Apuntes de conferencias, Laboratorio de Sistemas Integrados, ETH Zürich. Archivado desde el original (PDF) el 17 de agosto de 2013 . Consultado el 17 de abril de 2009 .
- Zwillinger, Daniel (2002). Tablas y fórmulas matemáticas estándar CRC, 31.ª edición . Prensa CRC. pag. 4.ISBN 1-58488-291-3.