La notación de flechas encadenadas de Conway , creada por el matemático John Horton Conway , es un medio para expresar ciertos números extremadamente grandes . [1] Es simplemente una secuencia finita de enteros positivos separados por flechas hacia la derecha, p. Ej..
Como ocurre con la mayoría de las notaciones combinatorias , la definición es recursiva . En este caso, la notación finalmente se convierte en el número más a la izquierda elevado a una potencia entera (generalmente enorme).
Definición y descripción generalUna "cadena Conway" se define de la siguiente manera:
- Cualquier entero positivo es una cadena de longitud .
- Una cadena de longitud n , seguida de una flecha hacia la derecha → y un número entero positivo, juntos forman una cadena de longitud.
Cualquier cadena representa un número entero, de acuerdo con las cinco (técnicamente cuatro) reglas siguientes. Se dice que dos cadenas son equivalentes si representan el mismo número entero.
Si , , y son números enteros positivos, y es una subcadena, entonces:
- Una cadena vacía (o una cadena de longitud 0) es igual a y la cadena representa el número .
- es equivalente a .
- es equivalente a . (vea la notación de la flecha hacia arriba de Knuth )
- es equivalente a
(con Copias de , Copias de , y pares de paréntesis; aplica para > 0). - Porque es equivalente a , (Por la regla 2) y también a = , (Por la regla 3) podemos definir A igual
Tenga en cuenta que la cuarta regla se puede reemplazar aplicando repetidamente dos reglas para evitar las elipses :
- 4a. es equivalente a
- 4b. es equivalente a
Propiedades- Una cadena se evalúa a una potencia perfecta de su primer número
- Por lo tanto, es igual a
- es equivalente a
- es igual a
- es equivalente a (no confundir con )
InterpretaciónHay que tener cuidado de tratar una cadena de flechas como un todo . Las cadenas de flechas no describen la aplicación repetida de un operador binario. Mientras que las cadenas de otros símbolos infijos (por ejemplo, 3 + 4 + 5 + 6 + 7) a menudo se pueden considerar en fragmentos (por ejemplo, (3 + 4) + 5 + (6 + 7)) sin un cambio de significado (ver asociatividad ), o al menos se puede evaluar paso a paso en un orden prescrito, por ejemplo, 3 4 5 6 7 de derecha a izquierda, que no es así con las cadenas de flechas de Conway.
Por ejemplo:
La cuarta regla es el núcleo: una cadena de 4 o más elementos que terminan con 2 o más se convierte en una cadena de la misma longitud con un penúltimo elemento (generalmente muy aumentado). Pero su elemento final se reduce, permitiendo eventualmente que la segunda regla acorte la cadena. Después, parafraseando a Knuth , "mucho detalle", la cadena se reduce a tres elementos y la tercera regla termina la recursividad.
Ejemplos deLos ejemplos se complican bastante rápidamente. A continuación se muestran algunos pequeños ejemplos:
- (Por regla 1)
- (Por la regla 5)
- Por lo tanto,
- (Por regla 3)
- (Por regla 3)
- (vea la notación de la flecha hacia arriba de Knuth )
- (Por regla 3)
- (ver tetración )
- (Por regla 4)
- (Por la regla 5)
- (Por regla 2)
- (Por regla 3)
- = mucho más grande que el número anterior
- (Por regla 4)
- (Por la regla 5)
- (Por regla 2)
- (Por regla 3)
- = mucho, mucho más grande que el número anterior
Ejemplos sistemáticos
Los casos más simples con cuatro términos (que no contengan números enteros menores de 2) son:
- (equivalente a la última propiedad mencionada)
Podemos ver un patrón aquí. Si, por cualquier cadena, dejamos luego (ver poderes funcionales ).
Aplicando esto con , luego y
Así, por ejemplo, .
Hacia adelante:
Nuevamente podemos generalizar. Cuando escribimos tenemos , es decir, . En el caso anterior, y , entonces
Función de AckermannLa función de Ackermann se puede expresar usando la notación de flechas encadenadas de Conway:
- por (Desde en hiperoperación )
por eso
- por
- ( y correspondería con y , que lógicamente podría agregarse).
Número de GrahamFunción CGConway y Guy crearon una función simple de un solo argumento que diagonaliza sobre toda la notación, definida como:
lo que significa que la secuencia es:
...
Esta función, como era de esperar, crece extraordinariamente rápido.
Extensión de Peter HurfordPeter Hurford, desarrollador web y estadístico, ha definido una extensión a esta notación:
De lo contrario, todas las reglas normales no se modifican.
ya es igual a lo antes mencionado , y la función crece mucho más rápido que el de Conway y Guy .
Tenga en cuenta que expresiones como son ilegales si y son números diferentes; una cadena solo debe tener un tipo de flecha hacia la derecha.
Sin embargo, si modificamos esto ligeramente de modo que:
entonces no solo lo hace convertirse en legal, pero la notación en su conjunto se vuelve mucho más fuerte. [2]
Ver tambiénReferenciasenlaces externos