Hiperoperación

En matemáticas , la secuencia de hiperoperaciones es una secuencia infinita de operaciones aritméticas (llamadas hiperoperaciones en este contexto) ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} 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). ^{[ nb 1 ]} Después de eso, la secuencia procede con más operaciones binarias que se extienden más allá de la exponenciación, usando la asociatividad derecha . Para las operaciones más allá de la exponenciación, el n º miembro de esta secuencia es nombrado por Reuben Goodstein por el prefijo griego de n sufijo -ación (como tetración ( n = 4 ), pentación ( n = 5 ), hexación ( n = 6 ), etc.) ^{[ 7 ]} y puede escribirse 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:

a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots a[n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ copias de }}a},\quad n\geq 2

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

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 mayores que los que puede mostrar la notación científica , como el número de Skewes y el googolplexplex (por ejemplo $50[50]50$ es mucho mayor que el número de Skewes y googolplexplex), pero hay algunos números que ni siquiera ellos pueden mostrar fácilmente, como el número de Graham y TREE(3) . ^{[ 14 ]}

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

Definición

La secuencia de hiperoperaciones es la secuencia de operaciones binarias. $H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}$ definido recursivamente de la siguiente manera: $H_{n}(a,b)={\begin{cases}b+1&{\text{si }}n=0\\a&{\text{si }}n=1{\text{ y }}b=0\\0&{\text{si }}n=2{\text{ y }}b=0\\1&{\text{si }}n\geq 3{\text{ y }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{en otro caso}}\end{cases}}.$ 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)&=b+1,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a^{b}\end{aligned}}$ para todos los enteros no negativos $a$ y $b$ . Las hiperoperaciones pueden verse, por lo tanto, como una respuesta a la pregunta "¿qué sigue?" en la secuencia de funciones que comienza con sucesor, suma, multiplicación, exponenciación. Así como la multiplicación de enteros se define como suma iterada y la exponenciación de enteros se define mediante multiplicación iterada, la siguiente hiperoperación, tetración , se define mediante exponenciación iterada; por ejemplo, $H_{4}(a,3)=\operatorname {tetración} (a,3)=a^{a^{a}}$ es una torre de poder de tres $a$ s, y $H_{4}(a,4)=\operatorname {tetración} (a,4)=a^{a^{a^{a}}}$ . Asimismo, la quinta hiperoperación pentación se define mediante tetración iterada, de modo que $H_{5}(a,3)=\operatorname {tetración} (a,\operatorname {tetración} (a,a))$ .

Los parámetros de la jerarquía de hiperoperaciones a veces se denominan mediante su término de exponenciación análogo; ^{[ 15 ]} así , a es la base , b es el exponente (o hiperexponente ), ^{[ 13 ]} y n es el rango (o grado ). ^{[ 8 ]} En general, $H_{n}(a,b)$ puede leerse como "la b- ésima n -ación de un ", de modo que $H_{4}(7,9)$ se lee como "la novena tetración de 7", y $H_{123}(456,789)$ se lee como "la 789ª 123-ación de 456".

Una forma alternativa de escribir hiperoperaciones es la notación compacta. $a[n]b$ para $H_{n}(a,b)$ En esta notación, la exponenciación se denota $a[3]b=a^{b}$ , tetración se denota $a[4]b$ (de modo que $a[4]3=a^{a^{a}}$ , la pentación se denota $a[5]b$ y así sucesivamente. Las hiperoperaciones también se pueden expresar utilizando la notación de flecha hacia arriba de Knuth . En esta notación, $a\uparrow b$ representa la función de exponenciación $a^{b}$ , $a\uparrow \uparrow b$ representa tetración, $a\uparrow \uparrow \uparrow b$ o $a\uparrow ^{3}b$ representa la pentación $a[5]b$ y, en general, $H_{n}(a,b)=a\uparrow ^{n-2}b$ para $n\geq 0.$ Otra alternativa es la notación de flechas encadenadas de Conway . En esta notación, se tiene $H_{n}(a,b)=a[n]b=a\rightarrow b\rightarrow n-2$ , de modo que (por ejemplo) $a[5]b=a\rightarrow b\rightarrow 3$ . ^{[ 16 ]}

Ejemplos

A continuación se muestra una lista de las primeras siete (de la 0 a la 6) hiperoperaciones ( 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 ]}

0, cuando n = 3 y b > 0 ^{[ nb 3 ]}

1, cuando n > 3 y b es par (incluido el 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) =

2, cuando n = 0

a + 1, cuando n = 1

a , cuando n ≥ 2

H _n ( a , a ) =

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

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

0, cuando n = 0, o n ≥ 4

a − 1, cuando n = 1

− a , cuando n = 2

1 / a , 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 en 1914, quien desarrolló parte de la teoría de las hiperoperaciones conmutativas (véase § Hiperoperaciones conmutativas más adelante). ^{[ 8 ]} Aproximadamente 12 años después, Wilhelm Ackermann definió la función $\phi (a,b,n)$ , que se asemeja un poco a la secuencia de hiperoperación. ^{[ 17 ]}

En su artículo de 1947, ^{[ 7 ]} 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 una función de tres argumentos, por ejemplo, $G(n,a,b)=H_{n}(a,b)$ La secuencia de hiperoperaciones en su conjunto se considera una versión de la función de Ackermann original. $\phi (a,b,n)$ — recursivo pero no recursivo primitivo — modificado 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.

La función de Ackermann original de tres argumentos $\phi$ 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 aspectos. Primero, $\phi (a,b,n)$ define una secuencia de operaciones que comienza 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 $\phi$ producir $\phi (a,b,3)=G(4,a,b+1)=a[4](b+1)$ , diferenciándose así de las hiperoperaciones más allá de la exponenciación. ^{[ 9 ]}^{[ 18 ]}^{[ 19 ]} El significado de b + 1 en la expresión anterior es que $\phi (a,b,3)$ = $a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}$ , donde b cuenta el número de operadores (exponenciaciones), en lugar de contar el número de operandos ("a") como lo hace la b en $a[4]b$ 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 que comienza desde un

En 1928, Wilhelm Ackermann definió una función de 3 argumentos. $\phi (a,b,n)$ que evolucionó gradualmente hasta convertirse en una función de dos argumentos conocida como la función de Ackermann . La función de Ackermann original $\phi$ era menos similar a las hiperoperaciones modernas, porque sus condiciones iniciales comienzan con $\phi (a,0,n)=a$ 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á.

Otra condición inicial que se ha utilizado es $A(0,b)=2b+1$ (donde la base es constante) $a=2$ ), debido a Rózsa Péter , que no forma una jerarquía de hiperoperaciones.

Variante que comienza desde 0

En 1984, CW Clenshaw y FWJ Olver iniciaron la discusión sobre el uso de hiperoperaciones para prevenir desbordamientos de punto flotante en computadoras . ^{[ 26 ]} Desde entonces, muchos otros autores ^{[ 27 ]}^{[ 28 ]}^{[ 29 ]} 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 $F_{n}(a,0)=0$ , 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 desplazada en uno.

Hiperoperaciones menores

Una alternativa para estas hiperoperaciones se obtiene mediante evaluación de izquierda a derecha. ^{[ 11 ]} 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)}b=\left(a_{(n)}(b-1)\right)_{(n-1)}a

con

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

Doner y Tarski extendieron esto a los números ordinales . ^{[ 30 ]} Utilizan el índice 0 en lugar del índice 1 para la suma. Extienden las fórmulas para manejar también cada ordinal sin predecesor inmediato reemplazando $b - 1$ en lo anterior con el supremo sobre todos los ordinales menores que $b$ , y tratan $a n$ de manera similar. Usamos letras griegas para indicar que estos son números ordinales y no simplemente números naturales.

{\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\nu }\beta &=\sup \limits _{\delta <\beta ,~\mu <\nu }(\alpha O_{\nu }\delta )O_{\mu }\alpha \,.\end{aligned}}

Con estas definiciones $O_{0}$ es suma , $O_{1}$ ⁠ es la multiplicación, y ⁠ $O_{2}$ ⁠ es exponenciación. Sin embargo, ⁠ $O_{3}$ ⁠ no logra formar la "torre de poder" aparente con la hiperoperación (no inferior) correspondiente.^{[ 31 ]}^{[ nb 4 ]} En cambio,

\alpha O_{3}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.

Hiperoperaciones conmutativas

Las hiperoperaciones conmutativas fueron consideradas por Albert Bennett ya en 1914, ^{[ 8 ]} lo que posiblemente sea la primera observación 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 ^{[ 7 ]} utilizó la secuencia de hiperoperadores para crear sistemas de numeración para los enteros no negativos. La denominada representación hereditaria completa del entero n , en el nivel k y base b , puede expresarse de la siguiente manera utilizando solo los primeros k hiperoperadores y usando como dígitos solo 0, 1, ..., b − 1, junto con la base b misma:

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 [ k − 1] x _{k − 1} [ k - 2] ... [2] x ₂ [1] x ₁

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

b [ k ] x _k ≤ n

b [ k ] x _k [ k − 1] x _{k − 1} ≤ n

...

b [ k ] x _k [ k − 1] x _{k − 1} [ k - 2] ... [2] x ₂ [1] x ₁ ≤ 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 los paréntesis innecesarios dando mayor precedencia a los operadores de nivel superior en el orden de evaluación; por lo tanto,

Las representaciones de nivel 1 tienen la forma b [1] X, con 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 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 la 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 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 de nivel 3 en base 2 de 6 anterior 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

Cálculo

Las definiciones de la secuencia de hiperoperaciones se pueden transponer naturalmente a los 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 calcular $H_{n}(a,b)$ se puede usar una pila , que inicialmente contiene los elementos $\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 5 ].}

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

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

Ejemplo

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

La secuencia de reducción es ^{[ nb 5 ]}^{[ nb 6 ]}

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

TRS basado en la definición sub 1.2

La definición mediante 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 de $H_{n}(a,b)=H_{n}^{1}(a,b)$ se puede implementar utilizando una pila.

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 según las reglas ^{[ nb 5 ].}

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

MIENTRAS stackLength <> 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 $\langle 1,3,0,3\rangle$ las configuraciones de pila sucesivas son

{\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 sucesivas de la pila 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}}