Notebooks

Complexity Measures

30 Sep 2012 10:59

C'est magnifique, mais ce n'est pas de la science. (Lots of 'em ain't that splendid, either.) This is, in the word of the estimable Dave Feldman (who taught me most of what I know about it, but has rather less jaundiced views), a "micro-field" within the soi-disant study of complexity. Every few months seems to produce another paper proposing yet another measure of complexity, generally a quantity which can't be computed for anything you'd actually care to know about, if at all. These quantities are almost never related to any other variable, so they form no part of any theory telling us when or how things get complex, and are usually just quantification for quantification's own sweet sake.

The first and still classic measure of complexity is that introduced by Kolmogorov, which is (roughly) the shortest computer program capable of generating a given string. This quantity is in general uncomptable, in the sense that there is simply no algorithm which will compute it. This comes from a result in computer science known as the halting problem, which in turn is a disguised form of Gödel's theorem, so this limit is not likely to be broken any time soon. Moreover, the Kolmogorov complexity is maximized by random strings, so it's really telling us what's random, not what's complicated, and it's gradually come to be called the "algorithmic information." It plays a very important role in every discussion of measuring complexity: in a pious act of homage to our intellectual ancestors, it is solemnly taken out, exhibited, and solemnly put away as useless for any practical application.

Generally speaking, complexity measures either take after Kolmogorov complexity, and involve finding some computer or abstract automaton which will produce the pattern of interest, or they take after information theory and produce something like the entropy, which, while in principle computable, can be very hard to calculate reliably for experimental systems. Bennett's "logical depth" is an instance of the former tendency (it's the running time of the shortest program), Lloyd and Pagels's "thermodynamic depth" of the later (it's the entropy of the ensemble of possible trajectories leading to the current state; uncomputable in the weaker sense that you'd have to go all the way back to the beginning of time...). The statistical complexity of computational mechanics partakes of both natures, being the entropy of an abstract automaton; it can actually be calculated. (I presently have a couple of papers incubating where we do calculate the statistical complexity of various real-world processes.)

Even if the complexity measure is uncomputable, it may be possible to say something about how fast it grows, in some well-defined average sense. For instance, the average Kolmogorov complexity per symbol of a random string converges on the entropy per symbol of the string. Similarly, my first published paper was a proof that the rate of increase in thermodynamic depth ("dive") is also an entropy rate, though not the same one. It'd be nice if there was a similar result about logical depth; watch this space for more developments in this exciting nano-field. --- Such results tend to make the complexity measures concerned seem less interesting, but this is just in line with Bohr's dictum, that the task of theoretical science is to turn deep truths into trivialities.

See also: Complexity, Entropy and the Physics of gzip

Thanks to Michel Decré for correcting my French.


Notebooks:     Hosted, but not endorsed, by the Center for the Study of Complex Systems