Which is bigger? $Ackermann(G_{64}, G_{64})$ or $G_{G_{64}}$

497 Views Asked by At

I have been playing around with the Ackermann function a bit and realized that it gets very big very fast. (Im going to use $A$ for $Ackermann$ throughout this question)

Already $A(5,1)$ is (according to WolframAlpha) an integer too large to represent. It also presents me with a representation that looks like this:

$$ A(5,1) = 2 \uparrow \uparrow \uparrow 4 - 3 = 2 \uparrow^{3} 4 - 3 $$

After playing around a little I found out that it always represents it like this:

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

After seeing this I started to wonder what would happen if you use Graham's number as the arguments. Since the value of it would uncomprehensible I tried to find something to compare it against. Remembering how the number is defined I asked myself if $G_{G_{64}}$ is bigger than $A(G_{64},G_{64})$?

Or in other words:

$$ A(G_{64},G_{64}) = 2 \uparrow^{G_{64} - 2} (G_{64} + 3) - 3 $$ vs $$ G_{G_{64}} = 3 \uparrow^{G_{G_{64}} - 1} 3 $$

I personally supspect it is $G_{G_{64}}$ since it has a lot more arrows but I'm not entirely sure.

1

There are 1 best solutions below

0
On BEST ANSWER

In fact, $G_{65}$ is already greater than $Ack(G_{64}, G_{64})$. Using monotonicity of Knuth arrows, we have

$G_{65} = 3 \uparrow^{G_{64}} 3 = 3 \uparrow^{G_{64}-1} (3 \uparrow ^{G_{64}-1} 3) > 2 \uparrow^{G_{64}-2} (G_{64}+3) = Ack(G_{64},G_{64})+3$.

To see that $3 \uparrow^{G_{64}-1} 3 > G_{64}+3$, observe that $3 \uparrow^1 3 = 27$, so again by monotonicity of Knuth arrows we have $3 \uparrow^b 3 \ge b+26$, and in particular $3 \uparrow^{G_{64}-1} 3 \ge G_{64}+25$.