# Upper bounding the Kolmogorov Complexity of the Standard Model

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?

• 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

## 2 Answers

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.

• 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 '16 at 17:02
• Uncomputability does not mean "can't be answered". It only means that you cannot write a program that will produce the answer in finite time with finite memory for any problem instance. When a general problem is uncomputable, you usually have quite a few instances of that general problem that are trivially computable, and some others that can be computed with algorithms that use additional constrains. It may even be possible that you can find a finite algorithm for any concrete instance of the problem, but you need an infinite amount of these algorithms to write the general solution. – cmaster May 15 at 6:50

You might find this link useful. In AIT, when you try to "estimate" (we are talking about non computable values here, in the general case ) the complexity of a finite string, those constants (related to the programming language) matter. Only in the asymptotic limit the original theory makes sense. The second point is that you are talking about a scientific theory (physics), so the guiding principles ( for example the mathematical framework , Lagrangian, Hamiltonian formalism, min action principle , etc) are part of the "programming language", you need more than just the computation of a Turing machine (in the definitions, though Turing machines might be enough to define some principles). That one line of compact mathematical notation representing the standard model is based on such principles, and some of them are metatheoretical. Anyway, if you study Chaitin' s work in greater depth, you might find some answers.

A more interesting problem to think about (I think ) is this. Maybe the Lagrangian/Hamiltonian/min action mathematical framework represents just one "programming language". Maybe there are others, even more powerful out there. This problem allows a multitude of perspectives, this is just one of them.

You can also consider a more simplistic approach, discarding any metatheoretical arguments and complex analogies. Hilbert's sixth problem (1900) deals with the axiomatization of physics. Depending on the nature of the axioms, you could have in principle a Turing machine encoding these axioms (if ever found). Then you could define the complexity of the scientific domain under consideration (in this case physics) as the length of a binary string encoding the inner workings of this Turing machine. A similar approach has been considered for mathematics (automatization of the process of mathematical discovery), but Godel incompleteness results showed the serious limitations of this process (well, there's a lot to be said here, and there might be ways to deal with these limitations, but there is no room here for that discussion). A similar phenomenon might appear as related to physics, and there are scientists who consider a full axiomatization of physics impossible.

As for the standard model, I would dare to guess that a few million bits of information should be sufficient, as an upper bound. I might be exceeding a true, tighter upper bound by two orders of magnitude.