0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$
    – user6973
    May 23 '15 at 11:25
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.