3
$\begingroup$

Lance Fortnow asked a question, What is the Volume of Information?, which Ross Snider criticised on two grounds:

  1. Off topic: 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, and
  2. Not advanced as a TCS question: 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/…)

I'm generally of the opinion that the physical basis of computation is fundamental to computer science —slogan: computer science is ultimately a physical science, one that involves a lot of formal science— and is perfectly amenable to formal treatment. Indeed, quantum computation could hardly be treated rigorously if that were not so.

I'm guessing that Ross' objection is not on those grounds, but rather he finds Lance's question to be the kind of question that has too much physics in it to be good for this site.

Are we worried about this? Should we resist questions whose TCS to physics quotient gets too low?

Related: Scope of questions?

| |
$\endgroup$
  • 3
    $\begingroup$ Well, if the question has 8 upvotes, 1 downvote, and 0 close-votes, I think it's already fairly obvious that most people seem to find it interesting and on-topic. $\endgroup$ – Jukka Suomela Sep 23 '10 at 8:41
  • $\begingroup$ @Jukka: sure, but I think that Ross' concerns deserve proper discussion. $\endgroup$ – Charles Stewart Sep 23 '10 at 8:46
  • $\begingroup$ I oppose to your way of summarizing the item 2 of Ross Snider’s criticism. It is really in response to Robin’s previous comment, and to me it means “If Robin’s interpretation is right, then the question is about physics, not about TCS.” $\endgroup$ – Tsuyoshi Ito Sep 23 '10 at 12:46
6
$\begingroup$

I'm sure some questions can be too physical for us. But I think this question, and in general questions that relate to the physical limits of computation are fine.

For example, the Strong Church-Turing thesis (SCTT) should definitely be considered an acceptable topic of discussion on a TCS website. (The SCTT has appeared in so many TCS papers.) The SCTT is a statement about the physical world we live in, so a zealous poster might downvote and vote to close based on it being a physical proposition. I don't agree with that.

As another example, consider this paper by Andrew Yao which appeared in the Journal of the ACM. JACM is a CS journal. If a discussion on such topics is good enough for them, it sure is good enough for me.

This particular question was related to the SCTT. There are some models of hypercomputers that violate the SCTT and an easy way to show that they are not realistic models of computation is to invoke the Holographic principle and the information density bound.

Finally, the upvotes for the question should clearly display that the community considers the question relevant and interesting, and therefore it should remain. I know we're in the early phase of the site trying to define what the site should be, but let's not be too restrictive. If we keep driving people away, we're going to be left with no one. (As a side note, I'm sure this question would be perfectly acceptable on MO!)

| |
$\endgroup$
3
$\begingroup$

My reservations (mild) about that answer have nothing to do with physics really. They have more to do with the rather soft nature of the question and the difficulty of answering versus discussing. But it's a fascinating discussion to have and as far as physics vs TCS goes, I welcome the perspective that the physics-trained researchers bring. It's not just quantum computing: it's also complex systems/social networks and statistical models for SAT, among others.

| |
$\endgroup$
3
$\begingroup$

Because I (inadvertently) initiated this meta discussion I feel I ought to contribute an answer. I also feel the need to defend my position, and what I believe to be true about the relevance of Lance's question in context of this StackExchange.

I agree with Robin under the comments that the question is a good physics question. In fact, Lance's question starts with "From a physics perspective...". The question is also phrased to include "What is information?" and "What is volume?" (this second question standing on its own does not qualify in any way as being on-topic).

I am of course aware of the tenable connection between information theory and physics (in fact I mentioned this connection as one of my reasons for pursuing higher studies in TCS in my answer to this question posted before Lance's question). I hope this dispels to some degree the cargo-cult physics googling caricature of my comment that Charles Stewart presented here; Namely, I am familiar with the topic, but not so familiar that I would hazard to claim any sort of expertise - notice I have never tried to post an authoritative sounding answer to any related question. I hope my comment under Lance's question sounded exactly as handwave-y as it was: it was a motion that was supposed to communicate "you should really talk to physicist because we are by no means the right community to define 'volume' or 'the amount of information in a physical system.'"

My main thesis would have two parts:

  • Lance's question, while having connections to TCS, doesn't not constitute a good TCS question. It is not refined enough, it has not been distilled enough, to qualify a good TCS answer. For example, it would be better if the question identified some problem with using bits of precision as a basis of information in a physical system, and asked how this might be resolved. Also that, if we were to admit the question as being relevant to TCS, we should reject it on the grounds that quick reference searches are enough to provide background material and links to better coverage.
  • That the question got more upvotes than it deserved because of the name of the author of the question. This question rapidly gathered upvotes, and in fact is currently ranked higher than some very strong TCS questions (for example this one here).

I would like to point out that the answers to the question, from authors I respect and am sure have a great deal of domain knowledge, did not amount to more than what can be found with a quick Google search.

| |
$\endgroup$
2
$\begingroup$

Honestly, I'm amazed that this question can be viewed as off-topic. It seems to me that cstheory is the perfect place to ask about whether some concept has an existing crisp formulation. Previous questions in this vein have included asking about something in the spirit of Rice's theorem in complexity theory and my own question on analogs for compressed sensing. Information theory is most definitely a part of theoretical computer science, and asking about whether the concept of volume, borrowed from physics, can be suitably formalized or not in an information theoretic sense is undeniably a valid one.

Moreover, while I'm all for being more strict about soft questions, I feel that being pedantic about the scope of technical questions is going to be a big turn-off to some people. cstheory is not supposed to be an elite club or something. It's the virtual equivalent to a coffee break in a conference. And Fortnow's question would certainly make for interesting conversation there. Also, the more types of questions we allow, the more people we bring in from different backgrounds, which only helps the cause of growing this site.

| |
$\endgroup$
  • 3
    $\begingroup$ Yes. MO has had lots of meta discussion about coffee break questiions, and frankly I like this question a lot more than "What are unsolved problems in CS", for example. $\endgroup$ – Suresh Venkat Sep 23 '10 at 16:56
1
$\begingroup$

It should be clear that I think physics has an important overlap with theoretical computer science. The real concern is that these kinds of question provoke the worst kind of answers.

Let me denounce what we might call cargo-cult physics, where a perfectly competent TCS researcher might read such a question, think, "oh, I read something about that in Baez's This week's finds!" and races off to Wikipedia, quickly skims a few articles to digest some technical terms, and throws together an as authoritative sounding an answer as can be cobbled together from such partly understood material.

We should try to insist that answers here will stand up to criticism from professional physicists. Maybe we should help get the physics proposal rolling, which might be able to help us later: it has some professional physicists committed.

| |
$\endgroup$
  • $\begingroup$ Charles: I don't appreciate your passive-aggressive swipe at my answer and the attack on my character. My background in mathematics and mathematical physics is actually deeper than my computer science background. When an area lies considerable outside the expertise of computer scientists, it seems eminently reasonable to point out someone at a popular exposition that contains references to the professional literature for further study. $\endgroup$ – Per Vognsen Sep 23 '10 at 8:53
  • $\begingroup$ @Per: My criticism of your answer was finished in that other thread. If I had intended further criticism of your answer, I would have spelled it out, and I would have phrased it more diplomatically. This answer was trying to spell out a concern that reflect what I read into Ross' comment, not one raised by your answer. $\endgroup$ – Charles Stewart Sep 23 '10 at 9:24
  • $\begingroup$ Then I mistook what seemed like a none too subtle undercurrent, for which I apologize. As for your general concerns, my personal feeling is that any heuristic-sounding answer given on a topic with relevance to TCS but outside of it will be taken by most people in the appropriate spirit. The voting and commenting system already provides a means for pointing out misinformation, etc. $\endgroup$ – Per Vognsen Sep 23 '10 at 9:40
  • 1
    $\begingroup$ There are already a fair number of physicists on the site particularly due to quantum computation. I certainly identify as a physicist more than as a computer scientist. $\endgroup$ – Joe Fitzsimons Sep 23 '10 at 11:42
  • $\begingroup$ I was just about to say that we do have people with a good understanding of physics and TCS on the site, and was going to name Joe Fitzsimons. He beat me to it though! $\endgroup$ – Robin Kothari Sep 23 '10 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .