Notación de flechas encadenadas de Conway - Conway chained arrow notation

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 . Es simplemente una secuencia finita de números enteros positivos separados por flechas hacia la derecha, por ejemplo . ${\ Displaystyle 2 \ a 3 \ a 4 \ a 5 \ a 6}$

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 general

Una "cadena Conway" se define de la siguiente manera:

• Cualquier entero positivo es una cadena de longitud .${\ Displaystyle 1}$
• Una cadena de longitud n , seguida de una flecha hacia la derecha → y un número entero positivo, forman juntos una cadena de longitud .${\ Displaystyle n + 1}$

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: ${\ Displaystyle p}$${\ Displaystyle q}$${\ Displaystyle r}$${\ Displaystyle X}$

1. Una cadena vacía (o una cadena de longitud 0) es igual a , y la cadena representa el número .${\ Displaystyle 1}$${\ Displaystyle p}$${\ Displaystyle p}$
2. ${\ Displaystyle X \ a 1}$es equivalente a .${\ Displaystyle X}$
3. ${\ displaystyle p \ rightarrow q \ rightarrow r}$es equivalente a . (vea la notación de la flecha hacia arriba de Knuth )${\ Displaystyle p [\ uparrow ^ {r}] q}$
4. ${\ Displaystyle X \ to p \ to (q + 1)}$es equivalente a (con copias de , copias de y pares de paréntesis; aplica para  > 0).${\ Displaystyle X \ a (X \ a (\ cdots (X \ a (X) \ a q) \ cdots) \ a q) \ a q}$
   ${\ Displaystyle p}$${\ Displaystyle X}$${\ Displaystyle p-1}$${\ Displaystyle q}$${\ Displaystyle p-1}$${\ Displaystyle q}$
5. Porque es equivalente a , (Por regla 2) y también a = , (Por regla 3) podemos definir a igual${\ displaystyle p \ rightarrow q \ rightarrow 1}$${\ Displaystyle p \ to q}$${\ Displaystyle p \ uparrow q}$${\ Displaystyle p ^ {q}}$${\ Displaystyle p \ to q}$${\ Displaystyle p ^ {q}}$

Tenga en cuenta que la cuarta regla se puede reemplazar aplicando repetidamente dos reglas para evitar las elipses :

4a. es equivalente a${\ Displaystyle X \ a 1 \ a (q + 1)}$${\ Displaystyle X}$

4b. es equivalente a${\ Displaystyle X \ to (p + 1) \ to (q + 1)}$${\ Displaystyle X \ to (X \ to p \ to (q + 1)) \ to q}$

Propiedades

1. Una cadena se evalúa a una potencia perfecta de su primer número
2. Por lo tanto, es igual a${\ Displaystyle 1 \ to Y}$${\ Displaystyle 1}$
3. ${\ Displaystyle X \ a 1 \ a Y}$ es equivalente a ${\ Displaystyle X}$
4. ${\ Displaystyle 2 \ a 2 \ a Y}$ es igual a ${\ Displaystyle 4}$
5. ${\ Displaystyle X \ a 2 \ a 2}$ es equivalente a (no confundir con )${\ Displaystyle X \ a (X)}$${\ Displaystyle X \ a X}$

Interpretación

Hay 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:

• ${\ displaystyle 2 \ rightarrow 3 \ rightarrow 2 = 2 \ uparrow \ uparrow 3 = 2 ^ {2 ^ {2}} = 16}$
• ${\ displaystyle 2 \ rightarrow \ left (3 \ rightarrow 2 \ right) = 2 ^ {(3 ^ {2})} = 2 ^ {3 ^ {2}} = 512}$
• ${\ displaystyle \ left (2 \ rightarrow 3 \ right) \ rightarrow 2 = \ left (2 ^ {3} \ right) ^ {2} = 64}$

La cuarta regla es el núcleo: una cadena de 4 o más elementos que terminan en 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 de

Los ejemplos se complican bastante rápidamente. A continuación, se muestran algunos pequeños ejemplos:

${\ Displaystyle n}$

${\ Displaystyle = n}$ (Por regla 1)

${\ Displaystyle p \ to q}$

${\ Displaystyle = p ^ {q}}$ (Por la regla 5)

Por lo tanto, ${\ Displaystyle 3 \ a 4 = 3 ^ {4} = 81}$

${\ Displaystyle 4 \ a 3 \ a 2}$

${\ displaystyle = 4 \ uparrow \ uparrow 3}$ (Por regla 3)

${\ displaystyle = 4 \ uparrow (4 \ uparrow 4)}$

${\ displaystyle = 4 \ uparrow 256}$

${\ displaystyle = 4 ^ {256}}$

${\ displaystyle = 13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,}$ ${\ Displaystyle 546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096}$

${\ Displaystyle \ aproximadamente 1,34 * 10 ^ {154}}$

${\ Displaystyle 2 \ a 2 \ a a}$

${\ displaystyle = 2 [\ uparrow ^ {a}] 2}$ (Por regla 3)

${\ displaystyle = 4}$(ver la notación de la flecha hacia arriba de Knuth )

${\ Displaystyle 2 \ a 4 \ a 3}$

${\ displaystyle = 2 \ uparrow \ uparrow \ uparrow 4}$ (Por regla 3)

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow 2))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow 4)}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow (2 \ uparrow (2 \ uparrow 2)))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow (2 \ uparrow 4))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow 16)}$

${\ displaystyle = 2 \ uparrow \ uparrow (65536)}$

${\ displaystyle = {^ {65536} 2}}$(ver tetración )

${\ Displaystyle 2 \ a 3 \ a 2 \ a 2}$

${\ Displaystyle = 2 \ a 3 \ a (2 \ a 3) \ a 1}$ (Por regla 4)

${\ Displaystyle = 2 \ a 3 \ a 8 \ a 1}$ (Por la regla 5)

${\ Displaystyle = 2 \ a 3 \ a 8}$ (Por regla 2)

${\ displaystyle = 2 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 3}$ (Por regla 3)

= mucho más grande que el número anterior

${\ Displaystyle 3 \ a 2 \ a 2 \ a 2}$

${\ Displaystyle = 3 \ a 2 \ a (3 \ a 2) \ a 1}$ (Por regla 4)

${\ Displaystyle = 3 \ a 2 \ a 9 \ a 1}$ (Por la regla 5)

${\ Displaystyle = 3 \ a 2 \ a 9}$ (Por regla 2)

${\ displaystyle = 3 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 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:

• ${\ Displaystyle a \ a b \ a 2 \ a 2}$
  ${\ Displaystyle = a \ to b \ to 2 \ to (1 + 1)}$
  ${\ Displaystyle = a \ to b \ to (a \ to b) \ to 1}$
  ${\ Displaystyle = a \ to b \ to a ^ {b}}$
  ${\ Displaystyle = a [a ^ {b} +2] b}$

(equivalente a la última propiedad mencionada)

• ${\ Displaystyle a \ a b \ a 3 \ a 2}$
  ${\ Displaystyle = a \ to b \ to 3 \ to (1 + 1)}$
  ${\ Displaystyle = a \ to b \ to (a \ to b \ to (a \ to b) \ to 1) \ to 1}$
  ${\ Displaystyle = a \ to b \ to (a \ to b \ to a ^ {b})}$
  ${\ Displaystyle = a [a \ to b \ to 2 \ to 2 + 2] b}$
• ${\ Displaystyle a \ a b \ a 4 \ a 2}$
  ${\ Displaystyle = a \ to b \ to (a \ to b \ to (a \ to b \ to a ^ {b}))}$
  ${\ Displaystyle = a [a \ to b \ to 3 \ to 2 + 2] b}$

Podemos ver un patrón aquí. Si, para cualquier cadena , dejamos entonces (ver poderes funcionales ). ${\ Displaystyle X}$${\ Displaystyle f (p) = X \ ap}$${\ Displaystyle X \ ap \ to 2 = f ^ {p} (1)}$

Aplicando esto con , luego y${\ Displaystyle X = a \ to b}$${\ Displaystyle f (p) = a [p + 2] b}$${\ Displaystyle a \ to b \ to p \ to 2 = a [a \ to b \ to (p-1) \ to 2 + 2] b = f ^ {p} (1)}$

Así, por ejemplo ,. ${\ Displaystyle 10 \ a 6 \ a 3 \ a 2 = 10 [10 [1000002] 6 + 2] 6}$

Hacia adelante:

• ${\ Displaystyle a \ a b \ a 2 \ a 3}$
  ${\ Displaystyle = a \ to b \ to 2 \ to (2 + 1)}$
  ${\ Displaystyle = a \ to b \ to (a \ to b) \ to 2}$
  ${\ Displaystyle = a \ to b \ to a ^ {b} \ to 2}$
  ${\ Displaystyle = f ^ {a ^ {b}} (1)}$

Nuevamente podemos generalizar. Cuando escribimos tenemos , es decir, . En el caso anterior, y así${\ Displaystyle g_ {q} (p) = X \ to p \ to q}$${\ Displaystyle X \ to p \ to q + 1 = g_ {q} ^ {p} (1)}$${\ Displaystyle g_ {q + 1} (p) = g_ {q} ^ {p} (1)}$${\ Displaystyle g_ {2} (p) = a \ to b \ to p \ to 2 = f ^ {p} (1)}$${\ Displaystyle g_ {3} (p) = g_ {2} ^ {p} (1)}$${\ Displaystyle a \ ab \ a 2 \ a 3 = g_ {3} (2) = g_ {2} ^ {2} (1) = g_ {2} (g_ {2} (1)) = f ^ {f (1)} (1) = f ^ {a ^ {b}} (1)}$

Función de Ackermann

La función de Ackermann se puede expresar usando la notación de flechas encadenadas de Conway:

${\ Displaystyle A (m, n) = (2 \ to (n + 3) \ to (m-2)) - 3}$para (Dado que en hiperoperación )${\ Displaystyle m \ geq 3}$${\ Displaystyle A (m, n) = 2 [m] (n + 3) -3}$

por eso

${\ Displaystyle 2 \ a n \ a m = A (m + 2, n-3) +3}$ por ${\ Displaystyle n> 2}$

( y correspondería con y , que lógicamente se podría agregar).${\ Displaystyle n = 1}$${\ Displaystyle n = 2}$${\ Displaystyle A (m, -2) = - 1}$${\ Displaystyle A (m, -1) = 1}$

Número de Graham

El número de Graham en sí no se puede expresar de forma concisa en la notación de flechas encadenadas de Conway, pero está delimitado por lo siguiente: ${\ Displaystyle G}$

${\ displaystyle 3 \ rightarrow 3 \ rightarrow 64 \ rightarrow 2 <G <3 \ rightarrow 3 \ rightarrow 65 \ rightarrow 2}$

Prueba: Primero definimos la función intermedia , que se puede usar para definir el número de Graham como . (El superíndice 64 denota un poder funcional ). ${\ displaystyle f (n) = 3 \ rightarrow 3 \ rightarrow n = {\ begin {matrix} 3 \ underbrace {\ uparrow \ uparrow \ cdots \ uparrow} 3 \\ {\ text {n flechas}} \ end {matriz }}}$${\ Displaystyle G = f ^ {64} (4)}$

Al aplicar la regla 2 y la regla 4 al revés, simplificamos:

${\ Displaystyle f ^ {64} (1)}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 1)) \ cdots))}$(con 64 )${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3) \ rightarrow 1) \ cdots) \ rightarrow 1) \ rightarrow 1}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow 64 \ rightarrow 2;}$

${\ Displaystyle f ^ {64} (4) = G;}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 4)) \ cdots))}$(con 64 )${\ displaystyle 3 \ rightarrow 3}$

${\ Displaystyle f ^ {64} (27)}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 27)) \ cdots))}$(con 64 )${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3))) \ cdots))}$(con 65 años)${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow 65 \ rightarrow 2}$ (computando como arriba).

${\ Displaystyle = f ^ {65} (1)}$

Dado que f es estrictamente creciente ,

${\ Displaystyle f ^ {64} (1) <f ^ {64} (4) <f ^ {64} (27)}$

que es la desigualdad dada.

Con flechas encadenadas, es muy fácil especificar un número mucho mayor que , por ejemplo ,. ${\ Displaystyle G}$${\ displaystyle 3 \ rightarrow 3 \ rightarrow 3 \ rightarrow 3}$

${\ displaystyle 3 \ rightarrow 3 \ rightarrow 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2) \ rightarrow 2 \,}$

${\ displaystyle = f ^ {3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2} (1)}$

${\ Displaystyle = f ^ {f ^ {27} (1)} (1)}$

que es mucho mayor que el número de Graham, porque el número es mucho mayor que . ${\ displaystyle 3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2}$ ${\ Displaystyle = f ^ {27} (1)}$${\ Displaystyle 65}$

Función CG

Conway y Guy crearon una función simple de un solo argumento que diagonaliza sobre toda la notación, definida como:

${\ displaystyle cg (n) = \ underbrace {n \ rightarrow n \ rightarrow n \ rightarrow \ dots \ rightarrow n \ rightarrow n \ rightarrow n} _ {n}}$

lo que significa que la secuencia es:

${\ displaystyle cg (1) = 1}$

${\ displaystyle cg (2) = 2 \ to 2 = 2 ^ {2} = 4}$

${\ Displaystyle cg (3) = 3 \ a 3 \ a 3 = 3 \ uparrow \ uparrow \ uparrow 3}$

${\ displaystyle cg (4) = 4 \ a 4 \ a 4 \ a 4}$

${\ Displaystyle cg (5) = 5 \ a 5 \ a 5 \ a 5 \ a 5}$

...

Esta función, como era de esperar, crece extraordinariamente rápido.

Extensión de Peter Hurford

Peter Hurford, desarrollador web y estadístico, ha definido una extensión a esta notación:

${\ displaystyle a \ rightarrow _ {b} c = \ rightarrow {a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} \ dots \ rightarrow _ {b- 1} a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} a} _ {c {\ text {flechas}}}}$

${\ displaystyle a \ rightarrow _ {1} b = a \ rightarrow b}$

De lo contrario, todas las reglas normales no se modifican.

${\ Displaystyle a \ rightarrow _ {2} (a-1)}$ya es igual a lo mencionado anteriormente , y la función está creciendo mucho más rápido que la de Conway y Guy . ${\ Displaystyle cg (a)}$${\ Displaystyle f (n) = n \ rightarrow _ {n} n}$${\ Displaystyle cg (n)}$

Tenga en cuenta que las expresiones como son ilegales si y son números diferentes; una cadena solo debe tener un tipo de flecha derecha. ${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e}$${\ Displaystyle b}$${\ Displaystyle d}$

Sin embargo, si modificamos esto ligeramente de modo que:

${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e = a \ rightarrow _ {b} \ underbrace {c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} \ dots \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c} _ {e {\ text {flechas}}}}$

entonces no solo se vuelve legal, sino que la notación en su conjunto se vuelve mucho más fuerte. ${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e}$

Ver también

• Notación Steinhaus-Moser
• Creando sistemáticamente secuencias cada vez más rápidas

Referencias

enlaces externos

• Factoides> números grandes
• Grandes números de Robert Munafo
• El libro de los números de JH Conway y RK Guy