Notación de flecha encadenada de Conway

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 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 resuelve como el número más a la izquierda elevado a una potencia entera (normalmente enorme).

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

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

Cualquier cadena representa un número entero, según las seis reglas que se indican a continuación. Se dice que dos cadenas son equivalentes si representan el mismo número entero.

Sea n los números enteros positivos y sea n el resto inalterado de la cadena. Entonces: ${\estilo de visualización a,b,c}$${\estilo de visualización \#}$

1. Una cadena vacía (o una cadena de longitud 0) es igual a${\estilo de visualización 1}$
2. La cadena representa el número .${\estilo de visualización a}$${\estilo de visualización a}$
3. La cadena representa el número .${\displaystyle a\flecha derecha b}$$Estilo de visualización a^{b}}$
4. La cadena representa el número (ver la notación de flecha hacia arriba de Knuth )${\displaystyle a\rightarrow b\rightarrow c}$${\displaystyle a\uparrow ^{c}b}$
5. Las cadenas y representan el mismo número que la cadena.${\displaystyle \#\rightarrow 1}$${\displaystyle \#\rightarrow 1\rightarrow a}$${\estilo de visualización \#}$
6. De lo contrario, la cadena representa el mismo número que la cadena .${\displaystyle \#\rightarrow (a+1)\rightarrow (b+1)}$${\displaystyle \#\rightarrow (\#\rightarrow a\rightarrow (b+1))\rightarrow b}$

Sea denotado subcadenas de longitud 1 o mayor. ${\estilo de visualización X, Y}$

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

Hay que tener cuidado de tratar una cadena de flechas como un todo . Las cadenas de flechas no describen la aplicación iterada de un operador binario. Mientras que las cadenas de otros símbolos infijos (p. ej. 3 + 4 + 5 + 6 + 7) a menudo se pueden considerar en fragmentos (p. ej. (3 + 4) + 5 + (6 + 7)) sin un cambio de significado (véase asociatividad ), o al menos se pueden evaluar paso a paso en un orden prescrito, p. ej. 3 ^{4 5 6 7} de derecha a izquierda, no ocurre lo mismo con las cadenas de flechas de Conway.

Por ejemplo:

• ${\displaystyle 2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=2^{4}=16}$
• ${\displaystyle 2\rightarrow (3\rightarrow 2)=2^{3^{2}}=2^{9}=512}$
• ${\displaystyle (2\rightarrow 3)\rightarrow 2=(2^{3})^{2}=8^{2}=64}$

La sexta regla de definición es la clave: una cadena de 4 o más elementos que termina en 2 o más se convierte en una cadena de la misma longitud con un penúltimo elemento (normalmente mucho) aumentado. Pero su último elemento se reduce, lo que finalmente permite que la quinta regla acorte la cadena. Después de, parafraseando a Knuth , "mucho detalle", la cadena se reduce a tres elementos y la cuarta regla termina la recursión.

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

${\estilo de visualización n}$

${\estilo de visualización =n}$(Por regla 2)

${\displaystyle p\to q}$

${\displaystyle =p^{q}}$(Por la regla 3)

De este modo,${\displaystyle 3\a 4=3^{4}=81}$

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

${\displaystyle =4\flecha arriba \flecha arriba 3}$(Por la regla 4)

${\displaystyle =4\flecha arriba (4\flecha arriba 4)}$

${\displaystyle =4\flecha arriba 256}$

${\estilo de visualización = 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 la regla 4)

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

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

${\displaystyle =2\flecha arriba \flecha arriba \flecha arriba 4}$(Por la regla 4)

${\displaystyle =2\flecha arriba \flecha arriba 2\flecha arriba \flecha arriba 2\flecha arriba \flecha arriba 2}$

${\displaystyle =2\flecha arriba \flecha arriba 2\flecha arriba \flecha arriba 4}$

${\displaystyle =2\flecha arriba \flecha arriba 2\flecha arriba 2\flecha arriba 2\flecha arriba 2}$

${\displaystyle =2\flecha arriba \flecha arriba 2\flecha arriba 2\flecha arriba 4}$

${\displaystyle =2\flecha arriba \flecha arriba 2\flecha arriba 16}$

${\displaystyle =2\flecha arriba \flecha arriba 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 la regla 6)

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

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

${\displaystyle =2\a (2\a 2\a 8)\a 7}$(Por la regla 6)

${\displaystyle =2\a 4\a 7}$(Por la regla 6)

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

= mucho mayor que el número anterior

${\displaystyle 3\to 2\to 2\to 2}$

${\displaystyle =3\to 2\to (3\to 2)\to 1}$(Por la regla 6)

${\displaystyle =3\to 2\to 9\to 1}$(Por la regla 3)

${\displaystyle =3\to 2\to 9}$(Por la regla 5)

${\displaystyle =3\to 3\to 8}$(Por la regla 6)

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

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

Los casos más simples con cuatro términos (que no contienen ningún número entero menor que 2) son:

• ${\displaystyle a\to b\to 2\to 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\to b\to 3\to 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\to b\to 4\to 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 , hacemos entonces (ver potencias funcionales ). ${\displaystyle X}$${\displaystyle f(p)=X\to p}$${\displaystyle X\to p\to 2=f^{p}(1)}$

Aplicando esto con , entonces 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\to 6\to 3\to 2=10[10[1000002]6+2]6}$

Siguiendo adelante:

• ${\displaystyle a\to b\to 2\to 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 , entonces${\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\to b\to 2\to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^{a^{b}}(1)}$

La función de Ackermann se puede expresar utilizando la notación de flecha encadenada de Conway:

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

por eso

${\displaystyle 2\to n\to m=A(m+2,n-3)+3}$para${\displaystyle n>2}$

( y correspondería con y , que lógicamente podrían añadirse).${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle A(m,-2)=-1}$${\displaystyle A(m,-1)=1}$

El número de Graham no se puede expresar en notación de flecha encadenada de Conway, pero está limitado por lo siguiente:

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

Demostración: primero definimos la función intermedia , que puede utilizarse para definir el número de Graham como . (El superíndice 64 denota una potencia funcional .) ${\displaystyle f(n)=3\rightarrow 3\rightarrow n={\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n arrows}}\end{matrix}}}$${\displaystyle G=f^{64}(4)}$

Aplicando 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 's)${\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 \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}{\text{64 layers}}}$$

${\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 's)${\displaystyle 3\rightarrow 3}$

$${\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}}$$

${\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 's)${\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 's)${\displaystyle 3\rightarrow 3}$

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

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

$${\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}{\text{65 layers}}}$$

Dado que f es estrictamente creciente ,

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

cual es la desigualdad dada.

Con flechas encadenadas, es muy fácil especificar un número mucho mayor que el número de Graham, por ejemplo, . ${\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)}$

$${\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\3\uparrow 3\end{matrix}}\right\}\ 27}$$ 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}$

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\to 3\to 3=3\uparrow \uparrow \uparrow 3}$

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

${\displaystyle cg(5)=5\to 5\to 5\to 5\to 5}$

...

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

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

${\displaystyle a\rightarrow _{b}c=\underbrace {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{ arrows}}}}$

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

Por lo demás, todas las reglas normales no sufren modificaciones.

${\displaystyle a\rightarrow _{2}(a-1)}$ya es igual a la mencionada anteriormente , y la función crece 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 expresiones como son ilegales si y son números diferentes; una cadena debe tener solo un tipo de flecha hacia la 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{ arrows}}}}$

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

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

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