Hiperoperación

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 adición ( n = 1), multiplicación ( n = 2) y exponenciación ( n = 3).

Después de eso, la secuencia procede con más operaciones binarias que se extienden más allá de la exponenciación, utilizando asociatividad derecha . Para las operaciones más allá de la exponenciación, el n- ésimo miembro de esta secuencia es nombrado por Reuben Goodstein después del prefijo griego n con el sufijo -ación (como tetración ( n = 4), pentación ( n = 5), hexación ( n = 6), etc.) ^[5] y puede escribirse como 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 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{ copias de }}a},\quad n\geq 2

También puede definirse de acuerdo con la parte de la regla de recursión de la definición, como en la versión de flecha hacia arriba de Knuth de la función de Ackermann :

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

Esto se puede utilizar para mostrar fácilmente números mucho más grandes que los que la notación científica puede mostrar, como el número de Skewes y el googolplexplex (por ejemplo, es mucho más grande que el número de Skewes y el googolplexplex), pero hay algunos números que ni siquiera ellos pueden mostrar fácilmente, como el número de Graham y TREE(3) . ^[14] $50[50]50$

Esta regla de recursión es común a muchas variantes de hiperoperaciones.

Definición

Definición, más común

La secuencia de hiperoperaciones es la secuencia de operaciones binarias , definida recursivamente de la siguiente manera: $H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}$ $H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}$

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 se reduce esencialmente 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

{\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 . $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, por lo que parece lógico definir la siguiente operación, la tetración, de modo que con una torre de tres "a". Análogamente, la pentación de (a, 3) será tetración(a, tetración(a, a)), con tres "a" en ella. $H_{2}(a,3)=a[2]3=a\times 3=a+a+a,$ $H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,$ $H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatorname {tetration} (a,3)=a^{a^{a}},$

{\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 hiperoperaciones, excepto por el desfase en la indexación:

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

Las hiperoperaciones pueden verse entonces como una respuesta a la pregunta "¿qué sigue?" en la secuencia : sucesor , adición , multiplicación , exponenciación , etc. Observando que

{\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 hiperoperaciones mediante su término de exponenciación análogo; ^[15] por lo que 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 ésima n -ación de a ", por ejemplo, se lee como "la 9.ª tetración de 7", y se lee como "la 789.ª 123-ación de 456". $H_{n}(a,b)$ $H_{4}(7,9)$ $H_{123}(456,789)$

En términos comunes, las hiperoperaciones son formas de componer números que aumentan en crecimiento en función de la iteración de la hiperoperación anterior. Los conceptos de sucesor, adición, 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 adición especifica el número de veces que se debe sumar 1 a sí mismo para producir un valor final, la multiplicación especifica el número de veces que se debe sumar un número a sí mismo y la exponenciación se refiere al número de veces que se debe multiplicar un número por sí mismo.

Definición, utilizando iteración

Definir la iteración de una función $f$ de dos 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}}

La secuencia de hiperoperaciones se puede definir en términos de iteración, de la siguiente manera. Para todos los números enteros, defina $x,n,a,b\geq 0,$

{\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

{\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 la secuencia de hiperoperación pueden transponerse naturalmente a sistemas de reescritura de términos (TRS) .

TRS basado en la definición sub 1.1

La definición básica de la secuencia de hiperoperaciones se corresponde con las reglas de reducción

{\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 el cálculo se puede utilizar una pila , que inicialmente contiene los elementos . $H_{n}(a,b)$ $\langle n,a,b\rangle$

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

{\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, partiendo de : $\langle n,a,b\rangle$

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

Ejemplo

Calcular . ^[16] $H_{2}(2,2)\rightarrow _{*}4$

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

Cuando se implementa utilizando una pila, en la entrada $\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.

{\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

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

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

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

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

{\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, partiendo de : $\langle 1,n,a,b\rangle$

MIENTRAS longitud de pila <> 1{ POP 4 elementos; PUSH 1 o 7 elementos según las reglas r6, r7, r8, r9, r10, r11;}

Ejemplo

Calcular . $H_{3}(0,3)\rightarrow _{*}0$

En la entrada, las configuraciones de pila sucesivas son $\langle 1,3,0,3\rangle$

{\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

{\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

{\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

{\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

{\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

$H_{3}(0,3)=0$ es un caso especial. Véase más abajo. ^{[nb 3]}^{[nb 4]}
El cálculo de según las reglas {r6 - r10, r11} es muy recursivo. El culpable es el orden en el que se ejecuta la iteración: . La primera desaparece solo después de que se desarrolla toda la secuencia. Por ejemplo, converge a 65536 en 2863311767 pasos, la profundidad máxima de recursión ^[18] es 65534. $H_{n}(a,b)$ $H^{n}(a,b)=H(a,H^{n-1}(a,b))$ $H$ $H_{4}(2,4)$
El cálculo según las reglas {r6 - r10, r12} es más eficiente en ese sentido. La implementación de la iteración como imita la ejecución repetida de un procedimiento H. ^[19] La profundidad de recursión, (n+1), coincide con la anidación de bucles. 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 recursión es solo 5, ya que la tetración es el quinto operador en la secuencia de hiperoperación. $H^{n}(a,b)$ $H^{n-1}(a,H(a,b))$ $H_{4}(2,4)$
Las consideraciones anteriores se refieren únicamente a la profundidad de recursión. Cualquiera de las dos formas de iteración conduce a la misma cantidad de pasos de reducción, que implican 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 solo afecta el orden en el que se aplican las reglas de reducción. $H_{3}(0,3)$

Ejemplos

A continuación se muestra una lista de las primeras siete hiperoperaciones (de la 0.ª a la 6.ª) ( 0⁰ se define como 1).

Casos especiales

H _n (0, b ) =

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 _n (1, b ) =

b , cuando n = 2

1, cuando n ≥ 3

H _n ( a , 0) =

0, cuando n = 2

1, cuando n = 0, o n ≥ 3

a , cuando n = 1

H _n ( a , 1) =

a, cuando n ≥ 2

H _n ( a , a ) =

H _n+1 ( a , 2), cuando n ≥ 1

H _n ( a , −1) = ^{[nb 5]}

0, cuando n = 0, o n ≥ 4

a − 1, cuando n = 1

− a , cuando n = 2

⁠1a⁠ , cuando n = 3

H _n (2, 2) =

3, cuando n = 0

4, cuando n ≥ 1, fácilmente demostrable recursivamente.

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 (véase más adelante). Unos 12 años después, Wilhelm Ackermann definió la función ^[20] que se parece un poco a la secuencia de hiperoperaciones. $\phi (a,b,n)$

En su artículo de 1947, ^[5] Reuben Goodstein introdujo la secuencia específica de operaciones que ahora se denominan 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.). Como función de tres argumentos, por ejemplo, , la secuencia de hiperoperaciones en su conjunto se considera una versión de la función Ackermann original ( recursiva pero no recursiva primitiva ) modificada por Goodstein para incorporar la función sucesora primitiva junto con las otras tres operaciones básicas de la aritmética ( suma , multiplicación , exponenciación ) y para hacer una extensión más fluida de estas más allá de la exponenciación. $G(n,a,b)=H_{n}(a,b)$ $\phi (a,b,n)$

La función Ackermann original de tres argumentos utiliza la misma regla de recursión que la versión de Goodstein (es decir, la secuencia de hiperoperaciones), pero difiere de ella en dos formas. Primero, define una secuencia de operaciones que comienzan con 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 dan como resultado , por lo que difieren de las hiperoperaciones más allá de la exponenciación. ^[7]^[21]^[22] La importancia 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 b en , y así sucesivamente para las operaciones de nivel superior. (Consulte el artículo sobre la función Ackermann para obtener más detalles). $\phi$ $\phi (a,b,n)$ $\phi$ $\phi (a,b,3)=G(4,a,b+1)=a[4](b+1)$ $\phi (a,b,3)$ $a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}$ $a[4]b$

Notaciones

Esta es una lista de notaciones que se han utilizado para hiperoperaciones.

Variante a partir dea

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 operaciones muy diferentes para la tetración y más allá. $\phi (a,b,n)$ $\phi$ $\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. $A(0,b)=2b+1$ $a=2$

Variante que comienza desde 0

En 1984, CW Clenshaw y FWJ Olver comenzaron la discusión sobre 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). Al discutir la tetración , Clenshaw et al. asumieron la condición inicial , lo que crea otra jerarquía de hiperoperaciones. Al igual que en la variante anterior, la cuarta operación es muy similar a la tetración , pero compensada por uno. $F_{n}(a,0)=0$

Hiperoperaciones inferiores

Una alternativa para estas hiperoperaciones se obtiene mediante la evaluación de izquierda a derecha. ^[9] Dado que

{\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)

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

con

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

Esto fue extendido a los números ordinales por Doner y Tarski, ^[33] mediante:

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

aO_{n}b=a_{(n+1)}b

Pero esto sufre una especie de colapso, al no formar la "torre de poder" tradicionalmente esperada de los hiperoperadores: ^[34]^{[nb 6]}

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

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

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

Hiperoperaciones conmutativas

Albert Bennett ya había considerado las hiperoperaciones conmutativas en 1914, ^[6] lo que posiblemente sea la observación más antigua sobre cualquier secuencia de hiperoperaciones. Las hiperoperaciones conmutativas se definen mediante la regla de recursión

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

que es simétrica 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 hiperoperaciones

RL Goodstein ^[5] utilizó la secuencia de hiperoperadores para crear sistemas de numeración para los números enteros no negativos. La denominada representación hereditaria completa del entero n , en el nivel k y base b , se puede expresar de la siguiente manera utilizando sólo los primeros k hiperoperadores y utilizando como dígitos sólo 0, 1, ..., b − 1, junto con la propia base b :

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

b [ k ] x [ k ₋₁ ] x [ _k₋₁ ]…[2] x2 [ 1 _]x1

donde x _k , ..., x ₁ son los números enteros más grandes que satisfacen (a su vez)

b [ k ] xk≤n

b [ k ] xk [ k ₋ 1] xk ₋₁ ≤ n

...

b [ k ] x [ k ₋ 1 ] x [ _k₋ 1] ...[ 2 ] x2 [ ₁_]x1≤n

Cualquier x _i que exceda b − 1 se vuelve a expresar 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 a los operadores de nivel superior mayor precedencia en el orden de evaluación; por lo tanto,

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, con X , Y también de esta forma;

Las representaciones de nivel 3 tienen la forma b [3] X [2] Y [1] Z, con 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, con X , Y , Z , W también de esta forma;

etcétera.

En este tipo de representación hereditaria de base b , la base misma aparece en las expresiones, así como "dígitos" del conjunto {0, 1, ..., b − 1}. Esto se compara con la representación de base 2 ordinaria cuando esta última se escribe en términos de la base b ; por ejemplo, en la notación de base 2 ordinaria, 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 base 2 de nivel 3 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 base 2 de nivel 3 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 2)

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

Véase también

Wikifunctions tiene una función de hiperoperación .

Grandes números

Notas

^ Las secuencias similares a la secuencia de hiperoperaciones han sido históricamente denominadas con muchos nombres, incluyendo: 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 del grado n , ^[6] exponenciación iterada z-fold de x con y , ^[7] operaciones de flecha , ^[8] reihenalgebra ^[9] e hiper-n . ^[1]^[9]^[10]^[11]^[12]
^ abc Esto implementa la estrategia más a la izquierda-más al interior (un paso) .
^ abc Para más detalles, véase Potencias de cero .
^ abc Para obtener más detalles, consulte Cero elevado a cero .
^ abc Sea x = a [ n ](−1). Por 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; véase aritmética ordinal para obtener más información

Referencias

^ abc Geisler 2003.
^ Friedman 2001.
^ Campagnola, Moore y Félix Costa 2002.
^ Virginia 1999.
^ abcde Goodstein 1947.
^abcdBennett 1915.
^ desde Negro 2009.
^ Littlewood 1948.
^abc Müller 1993.
^ Munafo 1999a.
^ por Robbins 2005.
^Por Galidakis 2003.
^ Rubtsov y Romerio 2005.
^ Townsend 2016.
^ Romero 2008.
^ Bezem, Klop y De Vrijer 2003.
^ En cada paso se reescribe el redex subrayado .
^ La profundidad máxima de recursión se refiere al número de niveles de activación de un procedimiento que existen durante la llamada más profunda del procedimiento. Cornelius y Kirby (1975)
^ BUCLE n VECES H.
^Por Ackermann 1928.
^Abc Munafo 1999b.
^ Cowles y Bailey 1988.
^ Knuth 1976.
^ Zwillinger 2002.
^ Weisstein 2003.
^ Hilbert 1926.
^ Nambiar 1995.
^ por Doner y Tarski 1969.
^ Clenshaw y Olver 1984.
^ Holmes 1997.
^ Zimmermann 1997.
^ Pinkiewicz, Holmes y Jamil 2000.
^ Doner y Tarski 1969, Definición 1.
^ 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.

Black, Paul E. (16 de marzo de 2009). «Función de Ackermann». Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología (NIST) de EE. UU . . 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.

Cornelius, BJ; Kirby, GH (1975). "Profundidad de recursión y la función de Ackermann". BIT Numerical Mathematics . 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 .

Doner, John; Tarski, Alfred (1969). "Una aritmética extendida de números ordinales". Fundamenta Mathematicae . 65 : 95–127. doi : 10.4064/fm-65-1-95-127 .

Friedman, Harvey M. (julio de 2001). "Secuencias finitas largas". Journal of Combinatorial Theory . 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 la teoría de números recursivos" (PDF) . Journal of Symbolic Logic . 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 para un nuevo estándar". Computer . 30 (3): 65–73. doi :10.1109/2.573666 . Consultado el 21 de abril de 2009 .

Knuth, Donald Ervin (diciembre de 1976). "Matemáticas y ciencias de la computación: cómo lidiar con la finitud". Science . 194 (4271): 1235–1242. Bibcode :1976Sci...194.1235K. doi :10.1126/science.194.4271.1235. PMID 17797067. S2CID 1690489 . Consultado el 21 de abril de 2009 .

Littlewood, JE (julio de 1948). "Números grandes". Mathematical Gazette . 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) . Archivado desde el original (PDF) el 2 de diciembre de 2013 . 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). "Inventando nuevos operadores y funciones". Large Numbers en MROB . Consultado el 28 de agosto de 2021 .

Nambiar, KK (1995). "Funciones de Ackermann y ordinales transfinitos". Applied Mathematics Letters . 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 : Association for Computing Machinery : 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 la IEEE Southeast Con 2000. 'Preparación para el nuevo milenio' (Cat. No.00CH37105). Actas de la IEEE. págs. 245–252. doi :10.1109/SECON.2000.845571. ISBN 0-7803-6312-4.S2CID 7738926 .

Robbins, AJ (noviembre de 2005). "Home of Tetration". Archivado desde el original el 13 de junio de 2015. Consultado el 17 de abril de 2009 .

Romerio, GF (2008-01-21). "Terminología de hiperoperaciones". Foro Tetration . Consultado el 21 de abril de 2009 .

Rubtsov, CA; 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 números grandes". Revista Chalkdust .

Weisstein, Eric W. (2003). Enciclopedia concisa de matemáticas del CRC, 2.ª edición . CRC Press. 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). "Computer Arithmetic: Principles, Architectures, and VLSI Design" (PDF) . Apuntes de clase, Laboratorio de Sistemas Integrados, ETH Zürich. Archivado desde el original (PDF) el 2013-08-17 . Consultado el 2009-04-17 .

Zwillinger, Daniel (2002). Tablas y fórmulas matemáticas estándar del CRC, 31.ª edición . CRC Press. pág. 4. ISBN 1-58488-291-3.