<p>With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (exponential), Turing machine state (constant) and position of the head over the tape (polynomial)). Thus any machine that runs for more than exponential time would have to visit some state more than once and hence loop.</p>

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

CC BY-SA 3.0
2015-05-23T11:28:35.367Z
2015-05-23T11:28:35.367Z
Tom van der Zanden
<p>I’m trying to come up with an algorithm that performs some action a <a href="http://en.wikipedia.org/wiki/Graham%27s_number" rel="nofollow">Graham’s number</a> of times on a machine with a reasonable amount of memory.</p>

<p>I thougth of the way to organize counter suitable for calculating <a href="http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation" rel="nofollow">$a{\uparrow\uparrow}b$</a>, 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).</p>

<p>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?</p>

<space-bounded><combinatorics>
An algorithm for counting to Graham’s Number
Oleg Stroganov
# An algorithm for counting to Graham’s Number

(Asked by: username_0 on 2015-05-23)

I’m trying to come up with an algorithm that performs some action a [Graham’s number](http://en.wikipedia.org/wiki/Graham%27s_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$](http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation), 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?

**Tags:** space-bounded, combinatorics

---

## 1 answers

### Answer by username_1 on 2015-05-23. Score: 1 | Accepted answer

With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (exponential), Turing machine state (constant) and position of the head over the tape (polynomial)). Thus any machine that runs for more than exponential time would have to visit some state more than once and hence loop.

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


---

