Hiperoperación

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) ^{[1] [11] [13]} 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.) ^[5] 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:

${\displaystyle 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}$

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 :

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

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) . ^[14] ${\displaystyle 50[50]50}$

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: ${\displaystyle H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}}$ ${\displaystyle H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}}$

${\displaystyle H_{n}(a,b)=a[n]b={\begin{cases}b+1&{\text{if }}n=0\\a&{\text{if }}n=1{\text{ and }}b=0\\0&{\text{if }}n=2{\text{ and }}b=0\\1&{\text{if }}n\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{otherwise}}\end{cases}}}$

(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

${\displaystyle {\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}}}$

Las operaciones para n ≥ 3 se pueden escribir en la notación de flecha hacia arriba de Knuth . ${\displaystyle H_{n}}$

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. ${\displaystyle H_{2}(a,3)=a[2]3=a\times 3=a+a+a,}$ ${\displaystyle H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,}$ ${\displaystyle H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatorname {tetration} (a,3)=a^{a^{a}},}$

${\displaystyle {\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{ for }}n\geq 3,\\\ldots &\\\end{aligned}}}$

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:

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

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

${\displaystyle {\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}}}$

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; ^[15] entonces a es la base , b es el exponente (o hiperexponente ), ^[12] y n es el rango (o grado ), ^[6] 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". ${\displaystyle H_{n}(a,b)}$ ${\displaystyle H_{4}(7,9)}$ ${\displaystyle H_{123}(456,789)}$

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

${\displaystyle 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}}}$

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 ${\displaystyle x,n,a,b\geq 0,}$

${\displaystyle {\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 la iteración es asociativa , la última línea se puede reemplazar por

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

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.

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&H(0,a,b)&\rightarrow &S(b)\\{\text{(r2)}}&H(S(0),a,0)&\rightarrow &a\\{\text{(r3)}}&H(S(S(0)),a,0)&\rightarrow &0\\{\text{(r4)}}&H(S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r5)}}&H(S(n),a,S(b))&\rightarrow &H(n,a,H(S(n),a,b))\end{array}}}$

Para calcular se puede utilizar una pila , que inicialmente contiene los elementos . ${\displaystyle H_{n}(a,b)}$ ${\displaystyle \langle n,a,b\rangle }$

Luego, repetidamente hasta que ya no sea posible, se extraen tres elementos y se reemplazan según las reglas ^{[nb 2]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&a&,&b&\rightarrow &(b+1)\\{\text{(r2)}}&1&,&a&,&0&\rightarrow &a\\{\text{(r3)}}&2&,&a&,&0&\rightarrow &0\\{\text{(r4)}}&(n+3)&,&a&,&0&\rightarrow &1\\{\text{(r5)}}&(n+1)&,&a&,&(b+1)&\rightarrow &n&,&a&,&(n+1)&,&a&,&b\end{array}}}$

Esquemáticamente, a partir de : ${\displaystyle \langle n,a,b\rangle }$

MIENTRAS longitud de pila <> 1{ POP 3 elementos; EMPUJE 1 o 5 elementos según las reglas r1, r2, r3, r4, r5;}

Ejemplo

Calcular . ^[dieciséis] ${\displaystyle H_{2}(2,2)\rightarrow _{*}4}$

La secuencia de reducción es ^{[nb 2] [17]}

Cuando se implementa usando una pila, en la entrada ${\displaystyle \langle 2,2,2\rangle }$

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.

${\displaystyle {\begin{array}{lll}{\text{(r6)}}&H(S(0),0,a,b)&\rightarrow &S(b)\\{\text{(r7)}}&H(S(0),S(0),a,0)&\rightarrow &a\\{\text{(r8)}}&H(S(0),S(S(0)),a,0)&\rightarrow &0\\{\text{(r9)}}&H(S(0),S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r10)}}&H(S(0),S(n),a,S(b))&\rightarrow &H(S(b),n,a,H(S(0),S(n),a,0))\\{\text{(r11)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(0),n,a,H(S(x),n,a,b))\end{array}}}$

Como la iteración es asociativa , en lugar de la regla r11 se puede definir

${\displaystyle {\begin{array}{lll}{\text{(r12)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(x),n,a,H(S(0),n,a,b))\end{array}}}$

Como en la sección anterior, el cálculo de se puede implementar utilizando una pila. ${\displaystyle H_{n}(a,b)=H_{n}^{1}(a,b)}$

Inicialmente la pila contiene los cuatro elementos . ${\displaystyle \langle 1,n,a,b\rangle }$

Luego, hasta la terminación, se extraen y reemplazan cuatro elementos según las reglas ^{[nb 2]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r6)}}&1&,0&,a&,b&\rightarrow &(b+1)\\{\text{(r7)}}&1&,1&,a&,0&\rightarrow &a\\{\text{(r8)}}&1&,2&,a&,0&\rightarrow &0\\{\text{(r9)}}&1&,(n+3)&,a&,0&\rightarrow &1\\{\text{(r10)}}&1&,(n+1)&,a&,(b+1)&\rightarrow &(b+1)&,n&,a&,1&,(n+1)&,a&,0\\{\text{(r11)}}&(x+2)&,n&,a&,b&\rightarrow &1&,n&,a&,(x+1)&,n&,a&,b\end{array}}}$

Esquemáticamente, a partir de : ${\displaystyle \langle 1,n,a,b\rangle }$

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 . ${\displaystyle H_{3}(0,3)\rightarrow _{*}0}$

Al ingresar, se muestran las configuraciones de pila sucesivas. ${\displaystyle \langle 1,3,0,3\rangle }$

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r11}1,2,0,{\underline {2,2,0,1}}\rightarrow _{r11}1,2,0,1,2,0,{\underline {1,2,0,1}}\\&\rightarrow _{r10}1,2,0,1,2,0,1,1,0,{\underline {1,2,0,0}}\rightarrow _{r8}1,2,0,1,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0.\end{aligned}}}$

Las igualdades correspondientes son

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}(0,H_{2}^{2}(0,1))=H_{2}(0,H_{2}(0,H_{2}(0,1))\\&=H_{2}(0,H_{2}(0,H_{1}(0,H_{2}(0,0))))=H_{2}(0,H_{2}(0,H_{1}(0,0)))=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0.\end{aligned}}}$

Cuando la regla de reducción r11 se reemplaza por la regla r12, la pila se transforma de acuerdo con

${\displaystyle {\begin{array}{lllllllll}{\text{(r12)}}&(x+2)&,n&,a&,b&\rightarrow &(x+1)&,n&,a&,1&,n&,a&,b\end{array}}}$

Las configuraciones de pila sucesivas serán entonces

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r12}2,2,0,{\underline {1,2,0,1}}\rightarrow _{r10}2,2,0,1,1,0,{\underline {1,2,0,0}}\\&\rightarrow _{r8}2,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}{\underline {2,2,0,0}}\rightarrow _{r12}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0\end{aligned}}}$

Las igualdades correspondientes son

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}^{2}(0,H_{2}(0,1))=H_{2}^{2}(0,H_{1}(0,H_{2}(0,0)))\\&=H_{2}^{2}(0,H_{1}(0,0))=H_{2}^{2}(0,0)=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0\end{aligned}}}$

Observaciones

• ${\displaystyle H_{3}(0,3)=0}$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. ${\displaystyle H_{n}(a,b)}$ ${\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}$ ${\displaystyle H}$ ${\displaystyle H_{4}(2,4)}$
• 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. ${\displaystyle H^{n}(a,b)}$ ${\displaystyle H^{n-1}(a,H(a,b))}$ ${\displaystyle H_{4}(2,4)}$
• 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. ${\displaystyle H_{3}(0,3)}$

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 ^[6] 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 ^[20] que se parece un poco a la secuencia de hiperoperación. ${\displaystyle \phi (a,b,n)}$

En su artículo de 1947, ^[5] 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. ${\displaystyle G(n,a,b)=H_{n}(a,b)}$ ${\displaystyle \phi (a,b,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. ^{[7] [21] [22]} 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). ${\displaystyle \phi }$ ${\displaystyle \phi (a,b,n)}$ ${\displaystyle \phi }$ ${\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)}$ ${\displaystyle \phi (a,b,3)}$ ${\displaystyle a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}}$ ${\displaystyle a[4]b}$

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. ${\displaystyle \phi (a,b,n)}$ ${\displaystyle \phi }$ ${\displaystyle \phi (a,0,n)=a}$

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. ${\displaystyle A(0,b)=2b+1}$ ${\displaystyle a=2}$

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 . ^[29] Desde entonces, muchos otros autores ^{[30] [31] [32]} 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. ${\displaystyle F_{n}(a,0)=0}$

Hiperoperaciones más bajas

Una alternativa para estas hiperoperaciones se obtiene evaluando de izquierda a derecha. ^[9] Desde

${\displaystyle {\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{(b-1)}\right)\cdot a\end{aligned}}}$

definir (con ° o subíndice)

${\displaystyle a_{(n+1)}b=\left(a_{(n+1)}(b-1)\right)_{(n)}a}$

con

${\displaystyle {\begin{aligned}a_{(1)}b&=a+b\\a_{(2)}0&=0\\a_{(n)}1&=a&{\text{for }}n>2\\\end{aligned}}}$

Doner y Tarski ampliaron esto a los números ordinales, ^[33] mediante:

${\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\gamma }\beta &=\sup \limits _{\eta <\beta ,\xi <\gamma }(\alpha O_{\gamma }\eta )O_{\xi }\alpha \end{aligned}}}$

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? ]}

${\displaystyle aO_{n}b=a_{(n+1)}b}$

Pero esto sufre una especie de colapso, no logrando formar la "torre de energía" que tradicionalmente se espera de los hiperoperadores: ^{[34] [nb 6]}

${\displaystyle \alpha _{(4)}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.}$

Si α ≥ 2 y γ ≥ 2, ^{[28] [Corolario 33(i)] [nb 6]}

${\displaystyle \alpha _{(1+2\gamma +1)}\beta \leq \alpha _{(1+2\gamma )}(1+3\alpha \beta ).}$

Hiperoperaciones conmutativas

Las hiperoperaciones conmutativas fueron consideradas por Albert Bennett ya en 1914, ^[6] 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.

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

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 ^[5] 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 ₂ [1] x ₁

donde x _k , ..., x ₁ 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 ₂ [1] x ₁ ≤ 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 [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

• Números grandes

Notas

1. Históricamente , las secuencias similares a la secuencia de hiperoperación han recibido muchos nombres, entre ellos: la función de Ackermann ^[1] (3 argumentos), la jerarquía de Ackermann , ^[2] la jerarquía de Grzegorczyk ^{[3] [4]} (que es más general), la versión de Goodstein de la función de Ackermann , ^[5] operación de enésimo grado , ^[6] exponenciación iterada de x con y , ^[7] operaciones de flecha , ^[8] reihenalgebra ^[9] e hiper-n . ^{[1] [9] [10] [11] [12]}
2. Esto implementa la estrategia más interna a la izquierda (un paso) .
3. Para obtener más detalles, consulte Potencias de cero .
4. Para obtener más detalles, consulte Cero elevado a cero .
5. 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).
6. La suma ordinal no es conmutativa; ver aritmética ordinal para más información

Referencias

1. Geisler 2003.
2. Friedman 2001.
3. Campagnola, Moore y Félix Costa 2002.
4. Wirz 1999.
5. Goodstein 1947.
6. Bennett 1915.
7. Negro 2009.
8. Littlewood 1948.
9. Müller 1993.
10. Munafo 1999a.
11. Robbins 2005.
12. Galidakis 2003.
13. Rubtsov y Romerio 2005.
14. Townsend 2016.
15. Romerio 2008.
16. Bezem, Klop y De Vrijer 2003.
17. En cada paso se reescribe la redex subrayada .
18. 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)
19. BUCLE n VECES HACER H.
20. Ackermann 1928.
21. Munafo 1999b.
22. Cowles y Bailey 1988.
23. Knuth 1976.
24. Zwillinger 2002.
25. Weisstein 2003.
26. Hilbert 1926.
27. Nambiar 1995.
28. Doner y Tarski 1969.
29. Clenshaw y Olver 1984.
30. Holmes 1997.
31. Zimmermann 1997.
32. Pinkiewicz, Holmes y Jamil 2000.
33. Doner y Tarski 1969, Definición 1.
34. Doner y Tarski 1969, Teorema 3 (iii).

Bibliografía

• Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Annalen Matemáticas . 99 : 118-133. doi :10.1007/BF01459088. S2CID  123431274.

• 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.

• Negro, Paul E. (16 de marzo de 2009). "La función de Ackermann". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST) . Consultado el 29 de agosto de 2021 .

• 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.

• Meyer, Albert R .; Ritchie, Dennis MacAlistair (1967). La complejidad de los programas de bucle . ACM '67: Actas de la 22ª conferencia nacional de 1967. doi : 10.1145/800196.806014 .

• 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 .

• Perstein, Millard H. (1 de junio de 1962). "Algoritmo 93: Aritmética de orden general". Comunicaciones de la ACM . 5 (6). Ciudad de Nueva York : Asociación de Maquinaria de Computación : 344. doi : 10.1145/367766.368160 . ISSN  0001-0782.

• 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.