Notación de flecha encadenada de Conway

Medios para expresar ciertos números extremadamente grandes

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\to 3\to 4\to 5\to 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).

Definición y descripción general

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

• Cualquier número entero positivo es una cadena de longitud . ${\displaystyle 1}$
• Una cadena de longitud n , seguida de una flecha hacia la derecha → y un entero positivo, juntos forman una cadena de longitud . ${\displaystyle 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: ${\displaystyle a,b,c}$ ${\displaystyle \#}$

1. Una cadena vacía (o una cadena de longitud 0) es igual a ${\displaystyle 1}$
2. La cadena representa el número . ${\displaystyle a}$ ${\displaystyle a}$
3. La cadena representa el número . ${\displaystyle a\rightarrow b}$ ${\displaystyle 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}$ ${\displaystyle \#}$
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}$

Propiedades

Sea denotado subcadenas de longitud 1 o mayor. ${\displaystyle 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}$ ${\displaystyle 1}$
3. ${\displaystyle X\to 1\to Y}$ es equivalente a ${\displaystyle X}$
4. ${\displaystyle 2\to 2\to Y}$ es igual a ${\displaystyle 4}$
5. ${\displaystyle X\to 2\to 2}$ es equivalente a ${\displaystyle X\to (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 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.

Ejemplos

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

${\displaystyle n}$

${\displaystyle =n}$(Por regla 2)

${\displaystyle p\to q}$

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

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

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

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

${\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 \approx 1.34*10^{154}}$

${\displaystyle 2\to 2\to a}$

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

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

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

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

${\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\to 3\to 2\to 2}$

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

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

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

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

${\displaystyle =2\to 4\to 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

Ejemplos sistemáticos

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)}$

Función de Ackermann

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

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}$

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\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.

Ampliación de Peter Hurford

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}$

Véase también

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

Referencias

1. John H. Conway y Richard K. Guy, El libro de los números, 1996, págs. 59-62
2. "Números grandes, parte 2: Graham y Conway - Greatplay.net". archive.is . 2013-06-25. Archivado desde el original el 2013-06-25 . Consultado el 2018-02-18 .

Enlaces externos

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