Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Kolmogorov complexity of a hypothesis/theory/model is the shortest computer program that simulates it, regardless of how inefficient executing that program may be in terms of memory and time. I'm interested in how complex the standard model is, by this measure.

For example, this MinutePhysics video notes that the standard model is (almost) one equation. That's pretty short (less than 50 characters), but of course in order to turn it into a computer program you also need to encode how to perform the underlying math.

On the other end of the spectrum: teaching a human physics via text books can be done with millions of characters, but the majority of that "millions" is presumably due to the constraints of communicating to a human.

I guess I expect the answer to be less than a million bytes, and maaaaaaybe less than a kilobyte, but that's not really based on much except intuition. (Obviously this all has to be relative to a specific programming language. Pick any language you want.)

I searched google, and google scholar, and was surprised to fail to quickly find even a loose upper bound on the complexity of the known laws of physics. Has such an exercise in code golf been done? How difficult is it to do one? How complicated is the standard model?

share|cite|improve this question
    
Leave alone the standard model, I don't think the answer is known even for simple field theory toy models. What you've asked is a pretty deep question and I'm curious to see the answers but it's possible that there aren't any yet. – Siva May 18 '13 at 10:26
    
@Siva Note that I don't really care about the exact value, just a reasonable upper bound. The exact value has more to do with the particulars of your programming language or Turing machine encoding, and as you note is very difficult to determine (in fact: once you exceed a particular complexity, lower bounds become impossible due to issues related to the halting problem). – Craig Gidney May 18 '13 at 10:29
    
I'm not talking about the exact value. Any handle on an estimate of complexity would be very interesting. Maybe I'm making it out to be more complicated than it is, but I think we're some way from understanding such a characterization of QFTs, especially since they have "many" degrees off freedom. – Siva May 18 '13 at 10:33
    
This paper might be of interest: Quantum Computation of Scattering in Scalar Quantum Field Theories – Siva May 18 '13 at 10:38
    
@Siva Just in case there's any confusion: the abstract of that paper refers to computational complexity, which is distinct from Kolmogorov complexity. – Craig Gidney May 18 '13 at 11:16

What you explained is correct, given a chosen language and a formal system there is always a minimal program that generates the rest of the string and you can use that as a measure of complexity. But there is a practical problem to implement this a as form of comparing two theories. It has been shown that it is not computable, that is, there is no program which takes a string $s$ as input and produces the integer $K(s)$ as output.

share|cite|improve this answer
    
Yes, I knew know that. I just want small upper bounds. (I rephrased the question to avoid using the word 'estimate'.) I'm looking for explicit cases of "well, here's a golf-script program that does it in 10K chars" or "we showed it would take at most 1MiB of Fortran to write the code though we didn't actually do it". – Craig Gidney Jul 5 at 17:02

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.