26
$\begingroup$

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?

$\endgroup$
13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Siva
    May 18 '13 at 10:26
  • $\begingroup$ @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). $\endgroup$ May 18 '13 at 10:29
  • $\begingroup$ 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. $\endgroup$
    – Siva
    May 18 '13 at 10:33
  • $\begingroup$ This paper might be of interest: Quantum Computation of Scattering in Scalar Quantum Field Theories $\endgroup$
    – Siva
    May 18 '13 at 10:38
  • 1
    $\begingroup$ @Siva Just in case there's any confusion: the abstract of that paper refers to computational complexity, which is distinct from Kolmogorov complexity. $\endgroup$ May 18 '13 at 11:16
1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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". $\endgroup$ Jul 5 '16 at 17:02
  • $\begingroup$ 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. $\endgroup$ May 15 '19 at 6:50
1
$\begingroup$

Defining the Kolmogorov complexity for a theory requires defining what the program does. One possible definition would be that the program calculates the probability that a given interaction can occur or be observed, given some initial data (to some given precision). Another definition would be that it outputs the state of the system after a given time, given some input state (to some given precision). A third definition is that the program outputs the theory (including parameter values) in some language.

These three possibilities are fundamentally different and may even have different complexities.

A program predicting SM states would essentially have to perform a numerical solution of the Lagrange equations on a lattice to update the states; while this looks computationally unfeasible I think one could at least in principle write up an algorithm to get an upper bound. FermiQCD, a code for simulating the QCD sector, can be downloaded with a zipped size 6.9 Mb; I would suspect adding the rest of the SM would not really make it much larger (and most code is about other things than the actual core calculation - there is a lot of user interface and comments in there).

So in this sense we can probably guess that the standard model has a Kolmogorov complexity less than 55200000 bits. But it is a very loose bound.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Before seeing this, I came up with 3.576MB with a rough Fermi/back of the envelope method.

I am going to choose the language "English", and import two packages, "Mathematics" and "Physics", and write in a modern high level computer programming language called "Python". These packages and the English dictionary are all stored on a large hard drive on a single computer on Earth. I may use a bit of natural philosophy.

The setup is quite simple. We want to communicate "The Standard Model" to another entity. We're going to end up with a .txt file, which will then be sent over a line.

Let's imagine person A, who only speaks English and has a deep grasp of math, physics, and "The Standard Model", perhaps an experimental physicist working at CERN. This person can, with a bunch of squiggly lines, and a little notebook with twenty or so rational numbers, actually stand next to a great big machine, and tell you what numbers are going to come out it. It's truly remarkable.

Here are the squiggly lines (or a point in a high dimensional pixel space - your call):

The Standard Model Lagrangian

The masses are experimentally determined, and we could define them as constants in our computer program:

import English 
import math
import physics

unit = GeV/c^2
m1 = 0
m2 = 0
m3 = 
...
m17 = 173.1
m18 = 0.0072973525693
...
m22 = ...

and so on for the 22 constants.

However, we are cheating if we stop here. This person has a brain, and in that brain is the English language, no less than 50-100 courses in mathematics and physics, hundreds of papers that were poured over line by line, and the book in hand.

We'll need a mostly "self-contained" reference which discusses "The Standard Model", so let's take "Mathematical Aspects of Quantum Field Theory" by Edson De Faria and Welington de Melo. It's about 300 pages (298), and includes about 100 references (94) in the bibliography. Let's assume the number of courses is 50, and that there is 1 textbook for each course. Let's assume the references are all 50 pages, and the textbooks are all 300 pages long. For a standard .tex file, there will be some ratio of number of symbols per .pdf page. Based on one that I had, it was about $ 2000(symbol/page)=100(symbol/line)*20(line/page)$

This gives

$courses+refs+textbook=50course*1(book/course)*300(page/book)*2000(symbol/page)+100ref*50(page/ref)*2000(symbol/page)+1book*300(page/book)*2000(symbol/page)=40.6*10^6symbol$

Let's assume each symbol is a byte, so that we get $40.6MB$. Now, we need to include the size of math, physics, English, and Python. The English dictionary and Python code are easily measurable. Math and physics are a lot tougher. For the sake of this, let's say the math and physics are contained in the courses, references, and textbooks. Let's say the English language and Python together are $40.6MB$, for a total of $81.2MB$.

Now, this file is uncompressed. Let's say we have a compression ratio of 1/3, so we get $27.06MB$.

Person $\alpha$ speaks Spanish, and we'll assume they are very intelligent and well educated, but did not happen upon any math or physics at all in school. We're imagining they are both using computers, which are connected by a wire over a large distance.

In addition to the math and physics that'll need to be conveyed, person A will need to learn Spanish and person $\alpha$ will need to learn English, so we have two more dependencies, a translation neural network (or person), and a pedagogy package (or teacher):

import teacher
import translator

I don't know the Kolmogorov complexity of either of those.

However, for the inferior machine versions, we can approximate.

OpenNMT is an open-source neural network based translation algorithm (https://github.com/OpenNMT/OpenNMT-py). It is $34.749MB$ zipped.

The teaching, or in other words the skill required to truly translate this information and knowledge to another, is the hardest part. Some universities pioneered an effort at automating their undergraduate math courses. This proved to be quite difficult generally, and they mostly used a hybrid model. However, some of the intro courses are completely online with video lecture supplements. If a course is 12 weeks with 4 hours of lecture per week, at ~2GB/hr, we're up in the $100GB/course$ range.

So, very roughly, an upper bound on the complexity of the Standard Model is somewhere between 61.8MB and 10TB.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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