<p>That comment in her article doesn't give a lot of context about what kind of answer she might be expecting. But certainly this is by now a well-known and venerable question about which much is already known. The Wikipedia page on <a href="http://en.wikipedia.org/wiki/Holographic_principle">the holographic principle</a> has a good overview. The most counterintuitive thing about the holographic principle is that it says the information capacity of a region should be proportional to its surface area; if you think of information capacity in terms of how many tiny two-state devices you can pack in there, you'd expect the interior volume to be the limiting factor. That intuition holds true up to a certain point, but eventually the concentration of mass-energy, putting aside quantum miniaturization issues, becomes so great that a black hole forms. Roughly speaking, by a bit of dimensional analysis and the fact that gravity is an inverse-square law, it's radius squared (proportional to surface area) that's the relevant quantity here.</p>

CC BY-SA 2.5
2010-09-23T02:12:30.593Z
This is probably the best "popular science" article I've read on the holographic principle: http://sufizmveinsan.com/fizik/holographic.html
arnab
CC BY-SA 2.5
2010-09-23T07:55:22.780Z
"That a black hole forms doesn't mean it contains no information" In fact, it has maximum entropy for its contained quantity of mass-energy, relative to outsiders.
Per Vognsen
CC BY-SA 2.5
2010-09-23T08:12:25.327Z
Per: I deleted my comment, because it didn't make the point I wanted to make, which is that I think we need to be careful about what physical theory we pull in to answer this question.  I have the impression that the theory of quantum gravity is not regarded as settled, and string-theoretic concepts of information density are certainly not.  A good answer to this question should proceed at a slower pace.
Charles Stewart
CC BY-SA 2.5
2010-09-23T08:25:09.040Z
Fair enough. My sole intention was pointing the questioner towards the existing physics literature in this area.
Per Vognsen
CC BY-SA 2.5
2010-09-23T09:12:43.860Z
Charles: One of the strengths of the holographic principle is that it is not based on a particular theory or ideology of quantum gravity; it's considered a litmus test that proposed theories should pass approximately. My knowledge of string theory is virtually nil, but I've been told that string theorists have accounted for the holographic principle.
Per Vognsen
CC BY-SA 2.5
2010-09-23T01:59:40.423Z
2010-09-23T02:13:53.987Z
2010-09-23T02:13:53.987Z
Per Vognsen
<p>Lance, there is in fact a theorem which gives bounds on this. The <a href="http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem">Margolus-Levitin theorem</a> bounds the rate of computation in terms of energy density. There is a nice trick which can then be played: If the local energy density exceeds a certain limit, a black hole will form causing an event horizon which will essentially prevent you from getting an answer by causally disconnecting that region of space-time from the rest of the universe. Seth Lloyd has a nice paper using this trick to estimate the computational power of the universe (<a href="http://prl.aps.org/abstract/PRL/v88/i23/e237901">Phys. Rev. Lett. 88, 237901 (2002)</a>, <a href="http://arxiv.org/abs/quant-ph/0110141">arXiv</a>).</p>

<p>You can of course use similar reasoning on any finite region of space-time.</p>

CC BY-SA 3.0
2010-09-23T11:49:07.063Z
2011-08-11T06:48:08.467Z
2011-08-11T06:48:08.467Z
Joe Fitzsimons
<p>This is an interesting and somewhat amusing question but it's poorly formulated in its current form.</p>

<p>I'll take another stab/risk at an answer hoping that scoring will take the original difficulty and basic/inherent "soft" ambiguity of the question in mind and that based on current literature knowledge there are several possible avenues but arguably no "correct answer".</p>

<p>The main query seems to be  "physics analogies in computer science" of which volume is one of them. 
Therefore it's highly related to this other question
<a href="https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs">Physics results in TCS?</a></p>

<p>To answer this question I'll take a few different approaches which I think all have merit. </p>

<p><hr>
first, one approach sometimes used in physics and engineering fields is <a href="http://en.wikipedia.org/wiki/Dimensional_analysis" rel="nofollow noreferrer">"dimensional analysis".</a></p>

<p>In this case strictly interpreted, volume is in the unit "space" or "length cubed". (Although note in physics sometimes the term "space" is measured in either terms length or length cubed.)</p>

<p>Therefore one could argue that in algorithmics the study of the space hierarchy is analogous to the study of "volume". A $O(n^3)$ space algorithm seems also to have the units "length cubed" where length is expressed in terms of input size.</p>

<p>The problem with this is that in algorithmics a $O(n^3)$ algorithm is merely a contrived limit, in a sense TCS has considered the "multidimensional space continuum" since its inception seen in the space hierarchy theorem. </p>

<p>Carrying this over to physics, it might seem absurd to consider anything other than 3-d space, but of course advanced physics takes into consideration all kinds of higher dimensional space realms all the time, via c-dimensional Hilbert [vector] spaces. So it would seem that in some sense an $O(n^c)$ space algorithm can be construed to operate in a c-dimensional hilbert space. Seems like <a href="https://cstheory.stackexchange.com/questions/6959/mulmuleys-gct-program">mulmuleys GCT program</a> would be a premiere example of this.</p>

<hr>

<p>Another approach to a volume analogy (and other physics quantities) in TCS is as follows, as discussed in the other question. It is known that SAT has a transition point extremely analogous to the transition point in physics/thermodynamics, Which happens eg with ideal gases under compression from one phase to another eg gas to liquid. This happens under a decrease in volume (say of the container of the gas). Now in SAT with random inputs the main two parameters on input size are clauses and variables. (Another parameter is number of variables in clauses, although that is often fixed at 3 for 3-SAT.) </p>

<p>Adjusting either the clauses or variables while keeping the other fixed pushes the problem difficulty through the easy-hard-easy transition point. Therefore it seems that these parameters are somehow analogous to Volume although I haven't seen the specifics mapped out. Digging into some of the deep papers on the statistical physics of SAT may turn up the analog of Volume. See [5] for a basic mapping of SAT onto statistical physics terminology.</p>

<p>[5] Analytic and Algorithmic
Solution of Random
Satisﬁability Problems by Mezard, Parisi, Zechina<br>
<a href="http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf" rel="nofollow noreferrer">http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf</a></p>

<hr>

<p>The other approach might be related to the prior responses talking about high density information processing in physical space leading to black holes. It would use the <a href="http://en.wikipedia.org/wiki/Planck_units" rel="nofollow noreferrer">Planck limit</a> which has units of time, space, mass etcetera. There is a Planck Length unit $l_p$ defined on that Wikipedia page. See units in this <a href="http://en.wikipedia.org/wiki/Planck_units#Base_Planck_units" rel="nofollow noreferrer">table</a>.</p>

<p>I don't know the exact physical interpretation of the Planck length (it's arguably an active area of physics research), but I believe it can be interpreted in some sense as "smallest possible length of space". In other words $l_p^3$ might be the size of a smallest possible physical bit. It is interesting and perhaps a discontinuity of the analogy that in physics a smallest bit apparently must actually have volume (ie units length cubed) in contrast to computer science in which bits seem to have a dimension of unit "length" only.</p>

CC BY-SA 3.0
2012-01-14T22:29:27.983Z
ps I will split this up into separate answers if there is support, plz upvote this comment if you agree. I also should include the currently acceptable answer "there is no meaning to the _volume_ of information!" & argue that case briefly
vzn
CC BY-SA 3.0
2012-01-14T20:02:35.040Z
2017-06-08T07:31:06.910Z
2017-06-08T07:31:06.910Z
vzn
<p>This question was asked to Jeannette Wing after her <a href="http://cacm.acm.org/blogs/blog-cacm/98818-talking-with-pcast/fulltext">PCAST presentation</a> on computer science.</p>

<blockquote>
  <p>“From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science community since I think it begs the question “What is information?”) </p>
</blockquote>

<p>Beyond "What is information?" one should also figure out what "volume" means in this context? Perhaps maximum density of information is a better measure.</p>

CC BY-SA 2.5
2010-09-23T02:13:21.647Z
I downvoted because I don't find this question relevant to the site (despite how infinitely interesting it is). It really doesn't meet the qualifications in the FAQ so far as I can tell. No hate, Lance: I love your blog and someday hope to meet you. Tell Gasarch I'm sorry I didn't finish the book review for SIGACT news yet. O_o

Perhaps if the question were unpacked a little bit? I'm pretty sure physics people use entropy (degrees of freedom) do determine "physical" information.
Ross Snider
CC BY-SA 2.5
2010-09-23T02:45:48.243Z
@Ross: I interpreted the question to mean "is there a physical limit to how much information we pack into a region of space?" With that interpretation, I think it's a good question, and I've heard an answer to it before, so I know an answer exists.
Robin Kothari
CC BY-SA 2.5
2010-09-23T02:50:20.343Z
@Robin: In which case the question (while legitimate and interesting) isn't really a TCS question (and so is not appropriate), and also doesn't meet the qualification here (http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235) [see the answer already given below - a quick Google query involving "physics" "information" and "volume" will get you to the same place].
Ross Snider
CC BY-SA 2.5
2010-09-23T08:27:59.607Z
@Ross: The physical basis of information is not TCS?  I think this is best discussed on meta... Voilà, [Scope: Can questions be too physical for us?](http://meta.cstheory.stackexchange.com/questions/368/scope-can-questions-be-too-physical-for-us)
Charles Stewart
CC BY-SA 2.5
2010-09-23T12:51:23.707Z
I agree to Ross Snider and voted to close it as off topic.  While the question sounds interesting, it looks like a question in physics to me in its current form.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T23:06:14.140Z
A possibly related question: [how much computational power fits into a cubic centimeter](http://cstheory.stackexchange.com/questions/2758/how-much-computational-power-fits-into-a-cubic-centimeter).
Kaveh
<it.information-theory><physics>
What is the Volume of Information?
Lance Fortnow
# What is the Volume of Information?

(Asked by: username_0 on 2010-09-23)

This question was asked to Jeannette Wing after her [PCAST presentation](http://cacm.acm.org/blogs/blog-cacm/98818-talking-with-pcast/fulltext) on computer science.

> “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science community since I think it begs the question “What is information?”)

Beyond "What is information?" one should also figure out what "volume" means in this context? Perhaps maximum density of information is a better measure.

**Tags:** it.information-theory, physics
> **Comments:**
> **username_1**: I downvoted because I don't find this question relevant to the site (despite how infinitely interesting it is). It really doesn't meet the qualifications in the FAQ so far as I can tell. No hate, Lance: I love your blog and someday hope to meet you. Tell Gasarch I'm sorry I didn't finish the book review for SIGACT news yet. O_o  Perhaps if the question were unpacked a little bit? I'm pretty sure physics people use entropy (degrees of freedom) do determine "physical" information.  
> **username_2**: @Ross: I interpreted the question to mean "is there a physical limit to how much information we pack into a region of space?" With that interpretation, I think it's a good question, and I've heard an answer to it before, so I know an answer exists.  
> **username_1**: @Robin: In which case the question (while legitimate and interesting) isn't really a TCS question (and so is not appropriate), and also doesn't meet the qualification here (http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235) [see the answer already given below - a quick Google query involving "physics" "information" and "volume" will get you to the same place].  
> **username_3**: @Ross: The physical basis of information is not TCS?  I think this is best discussed on meta... Voilà, [Scope: Can questions be too physical for us?](http://meta.cstheory.stackexchange.com/questions/368/scope-can-questions-be-too-physical-for-us)  
> **username_4**: I agree to Ross Snider and voted to close it as off topic.  While the question sounds interesting, it looks like a question in physics to me in its current form.  
> **username_5**: A possibly related question: [how much computational power fits into a cubic centimeter](http://cstheory.stackexchange.com/questions/2758/how-much-computational-power-fits-into-a-cubic-centimeter).  

---

## 3 answers

### Answer by username_8 on 2010-09-23. Score: 25

Lance, there is in fact a theorem which gives bounds on this. The [Margolus-Levitin theorem](http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem) bounds the rate of computation in terms of energy density. There is a nice trick which can then be played: If the local energy density exceeds a certain limit, a black hole will form causing an event horizon which will essentially prevent you from getting an answer by causally disconnecting that region of space-time from the rest of the universe. Seth Lloyd has a nice paper using this trick to estimate the computational power of the universe ([Phys. Rev. Lett. 88, 237901 (2002)](http://prl.aps.org/abstract/PRL/v88/i23/e237901), [arXiv](http://arxiv.org/abs/quant-ph/0110141)).

You can of course use similar reasoning on any finite region of space-time.


---

### Answer by username_6 on 2010-09-23. Score: 23

That comment in her article doesn't give a lot of context about what kind of answer she might be expecting. But certainly this is by now a well-known and venerable question about which much is already known. The Wikipedia page on [the holographic principle](http://en.wikipedia.org/wiki/Holographic_principle) has a good overview. The most counterintuitive thing about the holographic principle is that it says the information capacity of a region should be proportional to its surface area; if you think of information capacity in terms of how many tiny two-state devices you can pack in there, you'd expect the interior volume to be the limiting factor. That intuition holds true up to a certain point, but eventually the concentration of mass-energy, putting aside quantum miniaturization issues, becomes so great that a black hole forms. Roughly speaking, by a bit of dimensional analysis and the fact that gravity is an inverse-square law, it's radius squared (proportional to surface area) that's the relevant quantity here.

> **Comments:**
> **username_7**: This is probably the best "popular science" article I've read on the holographic principle: http://sufizmveinsan.com/fizik/holographic.html  
> **username_6**: "That a black hole forms doesn't mean it contains no information" In fact, it has maximum entropy for its contained quantity of mass-energy, relative to outsiders.  
> **username_3**: Per: I deleted my comment, because it didn't make the point I wanted to make, which is that I think we need to be careful about what physical theory we pull in to answer this question.  I have the impression that the theory of quantum gravity is not regarded as settled, and string-theoretic concepts of information density are certainly not.  A good answer to this question should proceed at a slower pace.  
> **username_6**: Fair enough. My sole intention was pointing the questioner towards the existing physics literature in this area.  
> **username_6**: Charles: One of the strengths of the holographic principle is that it is not based on a particular theory or ideology of quantum gravity; it's considered a litmus test that proposed theories should pass approximately. My knowledge of string theory is virtually nil, but I've been told that string theorists have accounted for the holographic principle.  

---

### Answer by username_9 on 2012-01-14. Score: -4

This is an interesting and somewhat amusing question but it's poorly formulated in its current form.

I'll take another stab/risk at an answer hoping that scoring will take the original difficulty and basic/inherent "soft" ambiguity of the question in mind and that based on current literature knowledge there are several possible avenues but arguably no "correct answer".

The main query seems to be "physics analogies in computer science" of which volume is one of them.
Therefore it's highly related to this other question
[Physics results in TCS?](https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs)

To answer this question I'll take a few different approaches which I think all have merit.

---

first, one approach sometimes used in physics and engineering fields is ["dimensional analysis".](http://en.wikipedia.org/wiki/Dimensional_analysis)

In this case strictly interpreted, volume is in the unit "space" or "length cubed". (Although note in physics sometimes the term "space" is measured in either terms length or length cubed.)

Therefore one could argue that in algorithmics the study of the space hierarchy is analogous to the study of "volume". A $O(n^3)$ space algorithm seems also to have the units "length cubed" where length is expressed in terms of input size.

The problem with this is that in algorithmics a $O(n^3)$ algorithm is merely a contrived limit, in a sense TCS has considered the "multidimensional space continuum" since its inception seen in the space hierarchy theorem.

Carrying this over to physics, it might seem absurd to consider anything other than 3-d space, but of course advanced physics takes into consideration all kinds of higher dimensional space realms all the time, via c-dimensional Hilbert [vector] spaces. So it would seem that in some sense an $O(n^c)$ space algorithm can be construed to operate in a c-dimensional hilbert space. Seems like [mulmuleys GCT program](https://cstheory.stackexchange.com/questions/6959/mulmuleys-gct-program) would be a premiere example of this.

---

Another approach to a volume analogy (and other physics quantities) in TCS is as follows, as discussed in the other question. It is known that SAT has a transition point extremely analogous to the transition point in physics/thermodynamics, Which happens eg with ideal gases under compression from one phase to another eg gas to liquid. This happens under a decrease in volume (say of the container of the gas). Now in SAT with random inputs the main two parameters on input size are clauses and variables. (Another parameter is number of variables in clauses, although that is often fixed at 3 for 3-SAT.)

Adjusting either the clauses or variables while keeping the other fixed pushes the problem difficulty through the easy-hard-easy transition point. Therefore it seems that these parameters are somehow analogous to Volume although I haven't seen the specifics mapped out. Digging into some of the deep papers on the statistical physics of SAT may turn up the analog of Volume. See [5] for a basic mapping of SAT onto statistical physics terminology.

[5] Analytic and Algorithmic
Solution of Random
Satisﬁability Problems by Mezard, Parisi, Zechina  
<http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf>

---

The other approach might be related to the prior responses talking about high density information processing in physical space leading to black holes. It would use the [Planck limit](http://en.wikipedia.org/wiki/Planck_units) which has units of time, space, mass etcetera. There is a Planck Length unit $l\_p$ defined on that Wikipedia page. See units in this [table](http://en.wikipedia.org/wiki/Planck_units#Base_Planck_units).

I don't know the exact physical interpretation of the Planck length (it's arguably an active area of physics research), but I believe it can be interpreted in some sense as "smallest possible length of space". In other words $l\_p^3$ might be the size of a smallest possible physical bit. It is interesting and perhaps a discontinuity of the analogy that in physics a smallest bit apparently must actually have volume (ie units length cubed) in contrast to computer science in which bits seem to have a dimension of unit "length" only.

> **Comments:**
> **username_9**: ps I will split this up into separate answers if there is support, plz upvote this comment if you agree. I also should include the currently acceptable answer "there is no meaning to the _volume_ of information!" & argue that case briefly  

---

