4
$\begingroup$

My recent question on Programming Puzzles and Code Golf got some fair attention and showed that not only it is very easy to output $10^{100}$ symbols and halt, but actually quite convenient in many programming languages as well.

While posting it I was wondering whether I should ask for $10^{10^{100}}$ instead but decided against that because while theoretically straightforward, I think it's simply physically impossible within this universe.

Here's my reasoning: to iterate over some command $b^m$ times, one needs $O(m)$ space to maintain the counter. Physical computers of today aside, $10^{100}$ just exceeds the estimated number of particles in the known universe by many orders of magnitude.

My question is not about alternative possibilities of physical realization of memory storage but about the principle. I'm not well-grounded in restricted Turing computation. Are there some tricks towards reducing the space complexity below $O(m)$ given that the value of the counter is never needed, just the fact that it counts the proper number of times and then halts?

$\endgroup$
  • 1
    $\begingroup$ The actual figures are irrelevant, aren't they? Isn't your question "can I output $2^n$ bits using less than $n$ bits of memory"? (Note that with $\sim$-asymptotics, the base matters.) $\endgroup$ – Raphael Nov 1 '16 at 8:11
  • $\begingroup$ @Raphael Yes, it boils down to that. The actual figures were meant for background. I think a change in the base or splitting between what one would call stack and heap or tape and internal state etc. will change the logarithm only by a multiplicative constant, that's why I went with $10$ and the $O$-notation. $\endgroup$ – The Vee Nov 1 '16 at 8:15
7
$\begingroup$

The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this:

Is there a function $f\colon \mathbb{N} \to \{0,1\}^*$ satisfying $|f(n)| = o(\log n)$ and a program $P$ such that $P(f(n))$ uses space $O(f(n))$ and outputs $1^n$?

It is a basic result of Kolmogorov complexity that this is impossible, even without the restriction on space. However, if you are willing to allow randomness and to incur some (multiplicative) inaccuracy, you can use the approximate counting technique of Morris and Flajolet, for which $|f(n)| = \Theta(\log \log n)$.

$\endgroup$
  • $\begingroup$ The approximate counting technique is a fantastic idea! Great to have it confirmed the answer is negative but at the same learn that it is possible to be done approximately. $\endgroup$ – The Vee Nov 1 '16 at 11:31

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.