# An algorithm for counting to Graham’s Number

I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory.

I thougth of the way to organize counter suitable for calculating $a{\uparrow\uparrow}b$, but got stuck at even smaller problem of counting to $2^a$, where $a$ is a 64-bit integer ($2^{21}$Tb needed for storage of such number is above what I assume reasonable).

Is there some clever technique to count beyond $2{\uparrow\uparrow}6$? Or is there any conceptual limitations on the counters with a polynomial-bounded memory?

• You'll need $\;\;\;$ Graham's number $\: \leq \: 2^{\hspace{.02 in}\text{amount_of_memory}}\hspace{-0.04 in}\cdot$ number of states $\;\;\;$ in order to do that. $\hspace{.38 in}$
– user6973
May 23 '15 at 11:25

In general, to get a program to run for $T(n)$ time you need $\Omega(\log(T(n)))$ memory.