Se han utilizado varias notaciones para representar hiperoperaciones. Una tal notación es. Otra notación es, una notación infija que es conveniente para ASCII . La notación se conoce como 'notación de corchetes'.
Notación de flecha hacia arriba de Knuth es una notación alternativa. Se obtiene reemplazando en la notación de corchetes por flechas.
Por ejemplo:
la flecha única representa exponenciación (multiplicación iterada)
la flecha doble representa tetración (exponenciación iterada)
la flecha triple representa pentación (tetración iterada)
La definición general de la notación de flecha hacia arriba es la siguiente (para ):
Exponenciación por un poder natural se define como multiplicación iterada, que Knuth denota con una sola flecha hacia arriba:
Por ejemplo,
La tetración se define como exponenciación iterada, que Knuth denota con una "flecha doble":
Por ejemplo,
Las expresiones se evalúan de derecha a izquierda, ya que los operadores se definen como asociativos por la derecha .
Según esta definición,
etc.
Esto ya conduce a algunos números bastante grandes, pero la secuencia del hiperoperador no se detiene aquí.
La pentación , definida como tetración iterada, está representada por la "flecha triple":
La hexación , definida como pentación iterada, está representada por la "flecha cuádruple":
y así. La regla general es que un-el operador de flecha se expande en una serie asociativa a la derecha de () -Operadores de flecha. Simbólicamente,
Ejemplos:
Notación
En expresiones como , la notación para la exponenciación suele ser escribir el exponente como superíndice al número base . Pero muchos entornos, como los lenguajes de programación y el correo electrónico de texto sin formato , no admiten la composición tipográfica en superíndice . La gente ha adoptado la notación lineal.para tales entornos; la flecha hacia arriba sugiere "elevarse al poder de". Si el conjunto de caracteres no contiene una flecha hacia arriba, se usa el signo de intercalación (^) en su lugar.
La notación de superíndice no se presta bien a la generalización, lo que explica por qué Knuth eligió trabajar desde la notación en línea en lugar de.
es una notación alternativa más corta para nuparrows. Por lo tanto.
Las flechas de Knuth se han vuelto bastante populares, tal vez porque es un logotipo más fuerte que, por ejemplo,. [ investigación original? ]
Escribir notación de flecha hacia arriba en términos de potencias
Intentando escribir el uso de la conocida notación de superíndice da una torre de energía.
Por ejemplo:
Si b es una variable (o es demasiado grande), la torre de energía podría escribirse con puntos y una nota que indique la altura de la torre.
Continuando con esta notación, podría escribirse con una pila de tales torres de energía, cada una describiendo el tamaño de la que está encima.
Nuevamente, si b es una variable o es demasiado grande, la pila podría escribirse usando puntos y una nota que indique su altura.
Además, podría escribirse usando varias columnas de tales pilas de torres de energía, cada columna describiendo el número de torres de energía en la pila a su izquierda:
Y de manera más general:
Esto podría llevarse a cabo indefinidamente para representar como exponenciación iterada de exponenciación iterada para cualquier a , n y b (aunque claramente se vuelve bastante engorroso).
Usando tetration
La notación de tetraciónnos permite hacer estos diagramas un poco más simples sin dejar de emplear una representación geométrica (podríamos llamar a estas torres de tetración ).
Finalmente, como ejemplo, el cuarto número de Ackermann podría representarse como:
Generalizaciones
Algunos números son tan grandes que varias flechas de la notación de flecha hacia arriba de Knuth se vuelven demasiado engorrosas; luego un operador de n- flechaes útil (y también para descripciones con un número variable de flechas), o lo que es lo mismo, hiperoperadores .
Algunos números son tan grandes que ni siquiera esa notación es suficiente. El Conway encadenado flecha notación se puede usar entonces: una cadena de tres elementos es equivalente con las otras notaciones, pero una cadena de cuatro o más es aún más potente.
= , Desde = = , Así el resultado sale con
= o (Trillón)
Nota: Gartrialogue = = = = = =
Definición
Sin referencia a la hiperoperación, los operadores de flecha hacia arriba pueden definirse formalmente por
para todos los enteros con .
Esta definición usa exponenciación como caso base, y tetración como exponenciación repetida. Esto es equivalente a la secuencia de hiperoperación excepto que omite las tres operaciones más básicas de sucesión , suma y multiplicación .
Alternativamente, se puede elegir la multiplicación como caso base e iterar desde allí. Entonces la exponenciación se convierte en multiplicación repetida. La definición formal sería
para todos los enteros con .
Sin embargo, tenga en cuenta que Knuth no definió la "flecha nula" (). Se podría extender la notación a índices negativos (n ≥ -2) de tal manera que coincida con toda la secuencia de hiperoperación, excepto por el rezago en la indexación:
La operación de flecha hacia arriba es una operación asociativa a la derecha , es decir, se entiende que es , en vez de . Si la ambigüedad no es un problema, a veces se eliminan los paréntesis.
Tablas de valores
Computación 0 ↑ n b
Informática resultados en
0, cuando n = 0 [nb 1]
1, cuando n = 1 y b = 0 [nb 2] [nb 3]
0, cuando n = 1 yb > 0 [nb 2] [nb 3]
1, cuando n > 1 yb es par (incluido 0)
0, cuando n > 1 y b es impar
Computación 2 ↑ n b
Informática se puede reformular en términos de una tabla infinita. Colocamos los números en la fila superior y llene la columna de la izquierda con valores 2. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar .
Valores de = H norte + 2 ( 2 , B ) {\ Displaystyle H_ {n + 2} (2, b)} = 2 [ norte + 2 ] B {\ Displaystyle 2 [n + 2] b}
= 2 → b → n
B
ⁿ
1
2
3
4
5
6
fórmula
1
2
4
8
dieciséis
32
64
2
2
4
dieciséis
65536
3
2
4
65536
4
2
4
La tabla es la misma que la de la función de Ackermann , excepto por un cambio en y y una suma de 3 a todos los valores.
Computación 3 ↑ n b
Colocamos los números en la fila superior y llene la columna de la izquierda con valores 3. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar .
Valores de = H norte + 2 ( 3 , B ) {\ Displaystyle H_ {n + 2} (3, b)} = 3 [ norte + 2 ] B {\ Displaystyle 3 [n + 2] b}
= 3 → b → n
B
ⁿ
1
2
3
4
5
fórmula
1
3
9
27
81
243
2
3
27
7,625,597,484,987
3
3
7,625,597,484,987
4
3
Computación 4 ↑ n b
Colocamos los números en la fila superior y llene la columna de la izquierda con valores 4. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar .
Valores de = H norte + 2 ( 4 , B ) {\ Displaystyle H_ {n + 2} (4, b)} = 4 [ norte + 2 ] B {\ Displaystyle 4 [n + 2] b}
= 4 → b → n
B
ⁿ
1
2
3
4
5
fórmula
1
4
dieciséis
64
256
1024
2
4
256
3
4
4
4
Computación 10 ↑ n b
Colocamos los números en la fila superior y llene la columna de la izquierda con los valores 10. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar .
Valores de = H norte + 2 ( 10 , B ) {\ Displaystyle H_ {n + 2} (10, b)} = 10 [ norte + 2 ] B {\ Displaystyle 10 [n + 2] b}
= 10 → b → n
B
ⁿ
1
2
3
4
5
fórmula
1
10
100
1.000
10,000
100.000
2
10
10,000,000,000
3
10
4
10
Para 2 ≤ b ≤ 9 el orden numérico de los númeroses el orden lexicográfico con n como el número más significativo, por lo que para los números de estas 8 columnas, el orden numérico es simplemente línea por línea. Lo mismo se aplica a los números en las 97 columnas con 3 ≤ b ≤ 99, y si partimos de n = 1 incluso para 3 ≤ b ≤ 9,999,999,999.
Ver también
Recursividad primitiva
Hiperoperación
Castor ocupado
Notación de barra de cutler
Tetración
Pentacion
Función de Ackermann
Número de Graham
Notación Steinhaus-Moser
Notas
^ Tenga en cuenta que Knuth no definió el operador.
^ a b Para obtener más detalles, consulte Potencias de cero .
^ a b Para obtener más detalles, consulte Cero elevado a cero .
Referencias
^ Knuth, Donald E. (1976). "Matemáticas e informática: afrontando la finitud". Ciencia . 194 (4271): 1235-1242. Código Bibliográfico : 1976Sci ... 194.1235K . doi : 10.1126 / science.194.4271.1235 . PMID 17797067 .
^RL Goodstein (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 .
enlaces externos
Weisstein, Eric W. "Notación de flecha hacia arriba de Knuth" . MathWorld .
Robert Munafo, Números grandes: hiperoperadores superiores