Si llamo a la Función Ackermann con el número de Graham como sus dos argumentos, será menor que$g_{65}$

Question

En el comic de xkcd 207 establece que

[xkcd] significa llamar a la función de Ackermann con Graham número de los argumentos para horrorizar a los matemáticos.

$A(g_{64},g_{64})$

En esta explicación se establece que

Incluso el simple hecho de hacer $g_{65}$ reduce el número de $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$ a la insignificancia.

Así:

Es $g_{65}$ mayor que $A(g_{64}, g_{64})$?

Y es mayor que $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$?

Answer 1

Nunca he entendido cómo esto debería horrorizar a los matemáticos. Después de todo, los números son los números y el Grahams número y la función de Ackermann están estrechamente relacionadas. Tenemos, usando la notación de flecha arriba

$$A(m,n) = 2\uparrow^{m-2} (n+3) - 3$$

y

$$g_n = 3 \uparrow^{g_{n-1}} 3$$

Por lo $A(g_{64},g_{64}) = 2 \uparrow^{g_{64}-2} (g_{64}+3) - 3$

lo que me parece rougly sobre el mismo orden de absurdamente hugeness. De hecho, el uso de la desigualdad a partir de la respuesta a esto, obtenemos

$$A(g_{64}+2,1) + 3 = 2 \uparrow^{g_{64}} 4 < 3 \uparrow^{g_{64}} 3 = g_{65} < 2 \uparrow^{g_{64}} 5 - 2 = A(g_{64}+2,2) -2$$

Pero, a continuación, utilizando la definición recursiva de la función de Ackermann podemos obtener el límite inferior

$$g_{65} > A(g_{64}+2,1) + 3 = A(g_{64}+1,A(g_{64}+2,0)) + 3 = A(g_{64}+1,g_{64}+3) +3 > A(g_{64},g_{64})$$

pero sólo ligeramente, en relación con el tamaño de los constantes $+1$ $+3$ en comparación con $g_{64}$. Así que en el otro lado $ A(g_{64}+2,2) - 2$ es menor que $A(A(g_{64},g_{64}),A(g_{64},g_{64}))$, que es la respuesta a tu segunda pregunta.