¿Cómo comparamos el tamaño de los números que están alrededor del tamaño del número de Graham o más grandes?

Question

Cuando los números son tan grandes como el número de Graham, o en algún punto en el que no podemos escribirlos como valores numéricos, ¿cómo los comparamos?

Por ejemplo:

$$G>S^{S^{S^{\dots}}}$$

Dónde $G$ es el número de Graham y $S^{S^{S^{\dots}}}$ es $S$ se elevó a sí mismo $S$ tiempos y $S$ es el número de Skewes.

Parece obvio (creo) que el número de Graham es, en efecto, mayor, pero ¿cómo se puede demostrar eso si ambos números son "tan grandes" que resultan difíciles de comparar?

En términos más generales, ¿cómo comparamos números de este tamaño general?

Como problema mucho más difícil que el anterior, imagina una función $G(x,y)$ donde $G(64,3)=$ El número de Graham. La función $G(x,y)$ es la siguiente:

$$G(x,y)=y\uparrow^{(G(x-1,y))}y$$

Dónde $G(0,y)$ se da.

Pregunto para comparar $G(60,S)$ y $G(64,3)$

Answer 1

Básicamente se quiere construir una cadena de inecuaciones que relacione la expresión menor con la expresión mayor. La inducción suele ser útil en estos casos.

Un teorema útil para las flechas de Knuth es $(a \uparrow^n b) \uparrow^n c < a \uparrow^n (b+c)$ , probado en este documento . También se ha demostrado que $a \uparrow^n c$ es monótona en $a,n$ y $c$ cuando $a,c \ge 3$ que también es útil.

Por ejemplo, se puede ver fácilmente que $S < 3 \uparrow\uparrow 6$ Así que

$$S^{S^{S^\cdots}} = S \uparrow \uparrow S < (3\uparrow\uparrow 6)\uparrow\uparrow(3 \uparrow\uparrow 6) < 3\uparrow\uparrow (6 + 3\uparrow\uparrow 6) < 3 \uparrow\uparrow (3 \uparrow\uparrow 7) < 3 \uparrow\uparrow (3\uparrow\uparrow 3^{3^3}) = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow 4 < 3\uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow\uparrow 3 = G_1$$

Para responder a su pregunta más difícil, primero tenemos que saber qué $G(0,y)$ es. Dado que necesitamos $G(0,3) =4$ para que $G(64,3)$ es el número de Graham, asumiré que $G(0,y)=4$ .

Teorema: $G(n,S) < G(n+1,3)$

Lo demostraremos por inducción. Primero, observemos que $G(0,S) = 4 < 3\uparrow\uparrow\uparrow\uparrow 3 = G(1,3)$ .

Obsérvese que para $n \ge 3$ ,

$$S \uparrow^n S < (3\uparrow\uparrow 6)\uparrow^n (3\uparrow\uparrow 6) < (3\uparrow^n 6)\uparrow^n (3\uparrow\uparrow 6) < 3\uparrow^n (6+3\uparrow\uparrow 6) < 3\uparrow^n (3\uparrow\uparrow\uparrow 3) \le 3\uparrow^n (3\uparrow^n 3) = 3\uparrow^{n+1} 3$$

Así que si tenemos $G(n,S) < G(n+1,3)$ entonces $G(n,S)+1 \le G(n+1,3)$ Así que

$$G(n+1,S) = S \uparrow^{G(n,S)} S < 3 \uparrow^{G(n,S)+1} 3 \le 3 \uparrow^{G(n+1,3)} 3 = G(n+2,3)$$

y el teorema se sigue por inducción.

Así que en particular, $G(60,S) < G(61,3) < G(64,3)$ .

Answer 2

Es difícil describir la magnitud del número de Graham.

En el caso de las torres de energía, es imposible describirlo porque la altura de la torre de energía tendría una magnitud comparable.

Ya un número como $3 \uparrow^{10} 3$ es mucho mayor que el número dado construido por el número de Skewes. Esto se debe a que cada flecha es un nivel de recursividad. $G(2)=3\uparrow^{3\uparrow^4 3} 3$ ya es horriblemente grande, pero absolutamente diminuto comparado con el número de Graham.

Con el rápido crecimiento de la jerarquía, se consigue que el número de Graham sea comparable a $f_{\omega+1}(64)$ mientras que el número $S\uparrow S\uparrow... \uparrow S$ ni siquiera alcanzará $f_\omega(10)$ .

Para demostrar lo grande que es $G(2)$ ya es :

Denote $M=3\uparrow \uparrow \uparrow 3$

M es una torre de energía de $3's$ con altura $3^{27}$ .

Paso $1$ : $N_1=3$

Paso $2$ : $N_2=$ Una torre de energía con $N_1=3$ $3's$ $=3^{27}$ .

Paso $3$ : $N_3=$ Una torre de energía con $N_2$ $3's$$=M$.

Paso $4$ : $N_4=$ Una torre de energía con $N_3$ $3's$ .

Continúe, hasta llegar al paso $M$ . Entonces, usted tiene $G(2)$

Superamos con creces el número $S\uparrow S\uparrow ...\uparrow S$ ya en el Paso $4$ .

Answer 3

Mira hacia arriba "concurso de números grandes".

En general, es lejos más fácil de llegar a los métodos para describir números grandes que comparar dos comparar dos de esos números.

Answer 4

Tal vez, como idea, podríamos comparar las tasas de crecimiento de las funciones que hacen nuestros grandes números.

Imagina que comparas dos números dados como $G=g(x)$ y $S=s(y)$ .

Se comparan las tasas de crecimiento y luego, si $x$ es algo cercano a $y$ La función con más tasas de crecimiento produce el número más grande.

Si $x<y$ pero $g(x)$ crece más rápido que $s(y)$ se vuelve un lío.