Notación de flecha encadenada de Conway
Notación de flecha encadenada con Conway, creado por el matemático John Horton Conway, es un medio de expresar ciertos números extremadamente grandes. Es simplemente una secuencia finita de enteros positivos separados por flechas derechas, por ejemplo. 2→ → 3→ → 4→ → 5→ → 6{displaystyle 2to 3to 4to 5tode 6}.
Al igual que con la mayoría de las notaciones combinatorias, la definición es recursiva. En este caso, la notación eventualmente se resuelve como el número más a la izquierda elevado a alguna potencia entera (generalmente enorme).
Definición y resumen
Una "cadena Conway" se define de la siguiente manera:
- Cualquier entero positivo es una cadena de longitud 1{displaystyle 1}.
- Una cadena de longitud n, seguido de una derecha-flecha → y un entero positivo, juntos forman una cadena de longitud n+1{displaystyle n+1}.
Cualquier cadena representa un número entero, de acuerdo con las seis reglas siguientes. Se dice que dos cadenas son equivalentes si representan el mismo número entero.
Vamos a,b{displaystyle a,b} denotar números enteros positivos y dejar # # {displaystyle} denota el resto sin cambios de la cadena. Entonces:
- Una cadena vacía (o una cadena de longitud 0) es igual a 1{displaystyle 1}
- La cadena p{displaystyle p} representa el número p{displaystyle p}.
- La cadena a→ → b{displaystyle arightarrow b} representa el número ab{displaystyle a^{b}.
- La cadena a→ → b→ → c{displaystyle arightarrow brightarrow c} representa el número a↑ ↑ cb{displaystyle auparrow ^{c}b} (ver la notación de Knuth hacia arriba)
- La cadena # # → → 1{displaystyle #\\\\\\\#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ 1} representa el mismo número que la cadena # # {displaystyle}
- Else, la cadena # # → → ()a+1)→ → ()b+1){displaystyle #derecha (a+1)derecha (b+1)} representa el mismo número que la cadena # # → → ()# # → → a→ → ()b+1))→ → b{displaystyle #derecha (#derecho arightarrow (b+1)rightarrow b}.
Propiedades
- Una cadena evalúa a un poder perfecto de su primer número
- Por lo tanto, 1→ → Y{displaystyle 1to Y} es igual a 1{displaystyle 1}
- X→ → 1→ → Y{displaystyle Xto 1to Sí. equivale a X{displaystyle X}
- 2→ → 2→ → Y{displaystyle 2to 2to 2} Sí. es igual a 4{displaystyle 4}
- X→ → 2→ → 2{displaystyle Xto 2to 2} equivale a X→ → ()X){displaystyle Xto (X)} (para no confundir con X→ → X{displaystyle Xto X})
Interpretación
Se debe tener cuidado al tratar una cadena de flechas como un todo. Las cadenas de flechas no describen la aplicación iterativa 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 puede evaluarse paso a paso en un orden prescrito, p. 34567 de derecha a izquierda, eso no es así con las cadenas de flechas de Conway.
Por ejemplo:
- 2→ → 3→ → 2=2↑ ↑ ↑ ↑ 3=222=16{displaystyle 2rightarrow 3rightarrow 2=2uparrow uparrow 3=2^{2^{2}=16}
- 2→ → ()3→ → 2)=2()32)=232=512{displaystyle 2rightarrow left(3rightarrow 2right)=2^{(3^{2}=2^{3^{2}=512}
- ()2→ → 3)→ → 2=()23)2=64{displaystyle left(2rightarrow 3right)rightarrow 2=left(2^{3}right)^{2}=64}
La sexta regla de definición 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 (normalmente muy) aumentado. Pero su elemento último se reduce, lo que finalmente permite que la quinta regla acorte la cadena. Después, parafraseando a Knuth, "mucho detalle", la cadena se reduce a tres elementos y la cuarta regla termina la recursividad.
Ejemplos
Los ejemplos se vuelven bastante complicados rápidamente. Aquí hay algunos pequeños ejemplos:
n{displaystyle n}
- =n{displaystyle =n} (Por regla 2)
p→ → q{displaystyle pto q}
- =pq{displaystyle =p^{q} (Por regla 3)
- Así, 3→ → 4=34=81{displaystyle 3to 4=3^{4}=81}
4→ → 3→ → 2{displaystyle 4to 3to 2}
- =4↑ ↑ ↑ ↑ 3{displaystyle =4uparrow uparrow 3} (Por regla 4)
- =4↑ ↑ ()4↑ ↑ 4){displaystyle =4uparrow (4uparrow 4)}
- =4↑ ↑ 256{displaystyle =4uparrow 256}
- =4256{displaystyle =4^{256}
- =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 =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,} 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 546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,853,882,811,946,569,946,433,649,006,084,096}
- .. 1.34Alternativa Alternativa 10154{displaystyle approx 1.34*10^{154}
2→ → 2→ → a{displaystyle 2to 2to a}
- =2[↑ ↑ a]2{displaystyle =2[uparrow ^{a}2} (Por regla 4)
- =4{displaystyle =4} (ver la notación de flecha arriba de Knuth)
2→ → 4→ → 3{displaystyle 2to 4tode 3}
- =2↑ ↑ ↑ ↑ ↑ ↑ 4{displaystyle =2uparrow uparrow 4} (Por regla 4)
- =2↑ ↑ ↑ ↑ ()2↑ ↑ ↑ ↑ ()2↑ ↑ ↑ ↑ 2)){displaystyle =2uparrow uparrow (2uparrow uparrow (2uparrow uparrow 2)}
- =2↑ ↑ ↑ ↑ ()2↑ ↑ ↑ ↑ 4){displaystyle =2uparrow uparrow (2uparrow uparrow 4)}
- =2↑ ↑ ↑ ↑ ()2↑ ↑ ()2↑ ↑ ()2↑ ↑ 2))){displaystyle =2uparrow uparrow (2uparrow (2uparrow (2uparrow 2))}
- =2↑ ↑ ↑ ↑ ()2↑ ↑ ()2↑ ↑ 4)){displaystyle =2uparrow uparrow (2uparrow (2uparrow 4)}
- =2↑ ↑ ↑ ↑ ()2↑ ↑ 16){displaystyle =2uparrow uparrow (2uparrow 16)}
- =2↑ ↑ ↑ ↑ ()65536){displaystyle =2uparrow uparrow (65536)}
- =655362{displaystyle ={65536}2} (ver tetración)
2→ → 3→ → 2→ → 2{displaystyle 2to 3to 2to1} 2}
- =2→ → 3→ → ()2→ → 3)→ → 1{displaystyle =2to 3to (2to 3)tode 1} (Por regla 6)
- =2→ → 3→ → 8→ → 1{displaystyle =2to 3to 8to 1} (Por regla 3)
- =2→ → 3→ → 8{displaystyle =2to 3to 8} (Por regla 5)
- =2→ → ()2→ → 2→ → 8)→ → 7{displaystyle =2to (2to 2to 8)to 7} (Por regla 6)
- =2→ → 4→ → 7{displaystyle =2to 4to 7} (Por regla 6)
- =2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 4{displaystyle =2uparrow uparrow uparrow uparrow uparrow uparrow uparrow 4} (Por regla 4)
- = mucho más grande que el número anterior
3→ → 2→ → 2→ → 2{displaystyle 3to 2to 2to 2} 2}
- =3→ → 2→ → ()3→ → 2)→ → 1{displaystyle =3to 2to (3to 2)to 1} (Por regla 6)
- =3→ → 2→ → 9→ → 1{displaystyle =3to 2to 9to 1} (Por regla 3)
- =3→ → 2→ → 9{displaystyle =3to 2to 9} (Por regla 5)
- =3→ → 3→ → 8{displaystyle =3to 3to 8} (Por regla 6)
- =3↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3{displaystyle =3uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow 3} (Por 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 números enteros menores que 2) son:
- a→ → b→ → 2→ → 2{displaystyle ato bto 2tode 2}
=a→ → b→ → 2→ → ()1+1){displaystyle =ato bto 2to (1+1)}
=a→ → b→ → ()a→ → b)→ → 1{displaystyle =ato bto b)to 1}
=a→ → b→ → ab{displaystyle =ato bto a}
=a[ab+2]b{displaystyle =a[a^{b}+2]b}
- (equivalente a la propiedad anterior)
- a→ → b→ → 3→ → 2{displaystyle ato bto 3to 2}
=a→ → b→ → 3→ → ()1+1){displaystyle =ato bto 3to (1+1)}
=a→ → b→ → ()a→ → b→ → ()a→ → b)→ → 1)→ → 1{displaystyle =ato bto (ato bto b)to 1)to 1}
=a→ → b→ → ()a→ → b→ → ab){displaystyle =ato bto (ato bto a^{b}
=a[a→ → b→ → 2→ → 2+2]b{displaystyle =a[ato bto 2to 2+2]b} - a→ → b→ → 4→ → 2{displaystyle ato bto 4to 2}
=a→ → b→ → ()a→ → b→ → ()a→ → b→ → ab)){displaystyle =ato bto bto bto (ato bto a^{b})}
=a[a→ → b→ → 3→ → 2+2]b{displaystyle =a[ato bto 3to 2+2]b}
Podemos ver un patrón aquí. Si, para cualquier cadena X{displaystyle X}, lo dejamos f()p)=X→ → p{displaystyle f(p)=Xto p} entonces X→ → p→ → 2=fp()1){displaystyle Xto pto 2=f^{p}(1)} (ver poderes funcionales).
Aplicar esto con X=a→ → b{displaystyle X=ato b}, entonces f()p)=a[p+2]b{displaystyle f(p)=a[p+2]b} y a→ → b→ → p→ → 2=a[a→ → b→ → ()p− − 1)→ → 2+2]b=fp()1){displaystyle ato bto pto 2=a[ato bto (p-1)to 2+2]b=f^{p}(1)}
Así, por ejemplo, 10→ → 6→ → 3→ → 2=10[10[1000002]6+2]6{displaystyle 10to 6to 3to 2=10[10[1000002]6+2]6}.
Adelante:
- a→ → b→ → 2→ → 3{displaystyle ato bto 2tode 3}
=a→ → b→ → 2→ → ()2+1){displaystyle =ato bto 2to (2+1)}
=a→ → b→ → ()a→ → b)→ → 2{displaystyle =ato bto b)to 2}
=a→ → b→ → ab→ → 2{displaystyle =ato bto a}tod 2}
=fab()1){displaystyle =f^{a^{b}(1)}
De nuevo podemos generalizarnos. Cuando escribimos gq()p)=X→ → p→ → q{displaystyle g_{q}(p)=Xto pto q} tenemos X→ → p→ → q+1=gqp()1){displaystyle Xto pto q+1=g_{q}{p}(1)}, es decir, gq+1()p)=gqp()1){displaystyle g_{q+1}(p)=g_{q}{p}(1)}. En el caso anterior, g2()p)=a→ → b→ → p→ → 2=fp()1){displaystyle g_{2}(p)=ato bto pto 2=f^{p}(1)} y g3()p)=g2p()1){displaystyle g_{3}(p)=g_{2}{p}(1)}Así que a→ → b→ → 2→ → 3=g3()2)=g22()1)=g2()g2()1))=ff()1)()1)=fab()1){displaystyle ato bto 2to 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 flechas encadenadas de Conway:
- A()m,n)=()2→ → ()n+3)→ → ()m− − 2))− − 3{displaystyle A(m,n)=(2to (n+3)to (m-2)-3} para m≥ ≥ 3{displaystyle mgeq 3} (Desde A()m,n)=2[m]()n+3)− − 3{displaystyle A(m,n)=2[m](n+3)-3} en hiperoperación)
por lo tanto
- 2→ → n→ → m=A()m+2,n− − 3)+3{displaystyle 2to nto m=A(m+2,n-3)+3} para 2}" xmlns="http://www.w3.org/1998/Math/MathML">n■2{displaystyle n confiado2}2" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44e71ac55b9fbf1e9f341b946cda63d61d3ef2cd" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;"/>
- ()n=1{displaystyle n=1} y n=2{displaystyle n=2} correspondería con A()m,− − 2)=− − 1{displaystyle A(m,-2)=-1} y A()m,− − 1)=1{displaystyle A(m,-1)=1}, que lógicamente podría ser añadido).
Graham 's number
Número de Graham G{displaystyle G. no puede expresarse concisamente en la notación de flecha encadenada de Conway, pero está ligada por lo siguiente:
<math alttext="{displaystyle 3rightarrow 3rightarrow 64rightarrow 2<G3→ → 3→ → 64→ → 2.G.3→ → 3→ → 65→ → 2{displaystyle 3rightarrow 3rightarrow 64rightarrow 2 identificadoG 3rightarrow 65rightarrow 2}<img alt="{displaystyle 3rightarrow 3rightarrow 64rightarrow 2<G
Prueba: Primero definimos la función intermedia f()n)=3→ → 3→ → n=3↑ ↑ ↑ ↑ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 3flechas{displaystyle f(n)=3rightarrow 3rightarrow n={begin{matrix}3underbrace {uparrow cdots uparrow } 3\{text{n arrows}end{matrix}}}, que se puede utilizar para definir el número de Graham como G=f64()4){displaystyle G=f^{64}(4)}. (El superscript 64 denota un poder funcional.)
Al aplicar la regla 2 y la regla 4 al revés, simplificamos:
f64()1){displaystyle f^{64}(1)}
- =3→ → 3→ → ()3→ → 3→ → ()⋯ ⋯ ()3→ → 3→ → ()3→ → 3→ → 1))⋯ ⋯ )){displaystyle =3derecha 3derecha (3derecha 3derecha)} (con 64) 3→ → 3{displaystyle 3rightarrow 3}s)
- =3→ → 3→ → ()3→ → 3→ → ()⋯ ⋯ ()3→ → 3→ → ()3→ → 3)→ → 1)⋯ ⋯ )→ → 1)→ → 1{displaystyle =3derecha 3derechorrito (3derecha 3derecha)derechots (3derecha 3derecho (3derecha 3)derechazo 1)cdotes)derecha 1) 1}
- =3→ → 3→ → 64→ → 2;{displaystyle =3rightarrow 3rightarrow 64rightarrow 2;}
f64()4)=G;{displaystyle f^{64}(4)=G;}
- =3→ → 3→ → ()3→ → 3→ → ()⋯ ⋯ ()3→ → 3→ → ()3→ → 3→ → 4))⋯ ⋯ )){displaystyle =3derecha 3derecha (3derecha 3derecha)} (con 64) 3→ → 3{displaystyle 3rightarrow 3}s)
f64()27){displaystyle f^{64}(27)}
- =3→ → 3→ → ()3→ → 3→ → ()⋯ ⋯ ()3→ → 3→ → ()3→ → 3→ → 27))⋯ ⋯ )){displaystyle =3derecha 3derecha (3derecha 3derecha)cdotes)} (con 64) 3→ → 3{displaystyle 3rightarrow 3}s)
- =3→ → 3→ → ()3→ → 3→ → ()⋯ ⋯ ()3→ → 3→ → ()3→ → 3→ → ()3→ → 3)))⋯ ⋯ )){displaystyle =3derecha 3derecha (3derecho 3derecho (cdots (3derecho 3derecho (3derecho 3derecho (3derecho 3))})} (con 65 años) 3→ → 3{displaystyle 3rightarrow 3}s)
- =3→ → 3→ → 65→ → 2{displaystyle =3rightarrow 3rightarrow 65rightarrow 2} (computing as above).
- =f65()1){displaystyle =f^{65}(1)}
Como f es estrictamente creciente,
- <math alttext="{displaystyle f^{64}(1)<f^{64}(4)f64()1).f64()4).f64()27){displaystyle f^{64}(1) (64}(4)<img alt="{displaystyle f^{64}(1)<f^{64}(4)
que es la desigualdad dada.
Con flechas encadenadas, es muy fácil especificar un número mucho mayor que G{displaystyle G., por ejemplo, 3→ → 3→ → 3→ → 3{displaystyle 3rightarrow 3rightarrow 3rightarrow 3}.
3→ → 3→ → 3→ → 3{displaystyle 3rightarrow 3rightarrow 3rightarrow 3}
- =3→ → 3→ → ()3→ → 3→ → 27→ → 2)→ → 2{displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow 27rightarrow 2)rightarrow 2,}
- =f3→ → 3→ → 27→ → 2()1){displaystyle =f^{3rightarrow 3rightarrow 27rightarrow 2}(1)}
- =ff27()1)()1){displaystyle =f^{f^{27}(1)}
Función GC
Conway y Guy crearon una función simple de un solo argumento que diagonaliza toda la notación, definida como:
cg()n)=n→ → n→ → n→ → ⋯ ⋯ → → n→ → n→ → n⏟ ⏟ n{displaystyle cg(n)=underbrace {nrightarrow nrightarrow dots rightarrow nrightarrow nrightarrow n} _{n}
lo que significa que la secuencia es:
cg()1)=1{displaystyle cg(1)=1}
cg()2)=2→ → 2=22=4{displaystyle cg(2)=2to 2=2^{2}=4}
cg()3)=3→ → 3→ → 3=3↑ ↑ ↑ ↑ ↑ ↑ 3{displaystyle cg(3)=3to 3to 3=3uparrow uparrow 3}
cg()4)=4→ → 4→ → 4→ → 4{displaystyle cg(4)=4to 4to 4to 4}
cg()5)=5→ → 5→ → 5→ → 5→ → 5{displaystyle cg(5)=5to 5to 5to 5to 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 para esta notación:
a→ → bc=a→ → b− − 1a→ → b− − 1a→ → b− − 1⋯ ⋯ → → b− − 1a→ → b− − 1a→ → b− − 1a⏟ ⏟ cflechas{displaystyle arightarrow ¿Por qué? - ¿Qué? ### {b-1}dots rightarrow - ¿Qué? _{b-1}arightarrow _{b-1}a - ¿Qué?
a→ → 1b=a→ → b{displaystyle arightarrow ¿Qué? b)
Todas las reglas normales no cambian de lo contrario.
a→ → 2()a− − 1){displaystyle arightarrow _{2}(a-1)} ya es igual a lo antes mencionado cg()a){displaystyle cg(a)}, y la función f()n)=n→ → nn{displaystyle f(n)=nrightarrow _{n}n} es mucho más rápido que Conway y Guy cg()n){displaystyle cg(n)}.
Note que expresiones como a→ → bc→ → de{displaystyle arightarrow _{b}crightarrow _{d}e} son ilegales si b{displaystyle b} y d{displaystyle d} son números diferentes; una cadena sólo debe tener un tipo de derecha-flecha.
Sin embargo, si modificamos esto ligeramente de modo que:
a→ → bc→ → de=a→ → bc→ → d− − 1c→ → d− − 1c→ → d− − 1⋯ ⋯ → → d− − 1c→ → d− − 1c→ → d− − 1c⏟ ⏟ eflechas{displaystyle arightarrow ¿Por qué? ¿Qué? ¿Qué? - ¿Qué? - ¿Qué? ### {d-1}dots rightarrow - ¿Qué? - ¿Qué? _{d-1}c} - ¿Qué?
entonces no sólo lo hace a→ → bc→ → de{displaystyle arightarrow _{b}crightarrow _{d}e} ser legal, pero la notación como un todo se vuelve mucho más fuerte.
Contenido relacionado
Conjunto vacío
Historia de la lógica
Símbolo Mayor que (>)
Menor que <
Abscisa y ordenada