patternMinor
Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?
Viewed 0 times
withoutspaceoutputwouldpossible100thatcomputerusingand
Problem
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?
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?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#65359, answer score: 7
Revisions (0)
No revisions yet.