Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

This question was asked to Jeannette Wing after her PCAST presentation 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.

share|improve this question
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. –  Ross Snider Sep 23 '10 at 2:13
1  
@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 Sep 23 '10 at 2:45
    
@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 (meta.cstheory.stackexchange.com/questions/225/…) [see the answer already given below - a quick Google query involving "physics" "information" and "volume" will get you to the same place]. –  Ross Snider Sep 23 '10 at 2:50
    
@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? –  Charles Stewart Sep 23 '10 at 8:27
    
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 Sep 23 '10 at 12:51

3 Answers 3

Lance, there is in fact a theorem which gives bounds on this. The Margolus-Levitin 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), arXiv).

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

share|improve this answer

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 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.

share|improve this answer
6  
This is probably the best "popular science" article I've read on the holographic principle: sufizmveinsan.com/fizik/holographic.html –  arnab Sep 23 '10 at 2:12
    
"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 Sep 23 '10 at 7:55
    
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 Sep 23 '10 at 8:12
    
Fair enough. My sole intention was pointing the questioner towards the existing physics literature in this area. –  Per Vognsen Sep 23 '10 at 8:25
1  
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 Sep 23 '10 at 9:12

hi lance this is an interesting and somewhat amusing question but agree its poorly formulated in its current form and Im rather surprised its at 26 votes currently. but Ill 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 its highly related to this other question Physics results in TCS?

to answer this question Ill take a few different approaches which I think all have merit.


first, one approach sometimes used in physics and engineering fields is "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 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 havent 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 Satisfiability 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 plank limit which has units of time, space, mass etcetera. there is a plank Length unit $l_p$ defined on that wikipedia page. see units in this table

I dont know the exact physical interpretation of the plank length (its 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.

share|improve this answer
    
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 Jan 14 '12 at 22:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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