Measuring Complexity

From: andrew cooke <andrew@...>

Date: Sat, 26 Sep 2009 11:07:42 -0400

I'm considering revisiting a problem I worked on years ago (when I
first came to Chile, I think, and was looking for a job) - the
automatic generation of complex, but structured rhythms.

I have a possible technical approach, which I'll describe later
(Scala, OpenCL, genetic programming).  Here I'm looking at how to
measure complexity.

A couple of reviews that take a fairly standard view:
http://www.nbb.cornell.edu/neurobio/land/PROJECTS/Complexity/index.html
http://www.cscs.umich.edu/~crshalizi/notebooks/complexity-measures.html
http://www.cs.brandeis.edu/~pablo/thesis/html/node9.html

The second has pointers that look liked they could be interesting and
the third is part of a thesis -
http://www.cs.brandeis.edu/~pablo/thesis/html/thesis_html.html

There's also this - http://szabo.best.vwh.net/complexity.html - which
covers some of the same ground as the above, but is a little more
speculative and/or confused.

And while the above tend to associate complexity with entropy
(although quickly expanding to address issues of functional depth etc)
the following takes the opposite approach and assumes that complexity
is order - http://www.americanscientist.org/bookshelf/pub/measuring-complexity
- which actually makes sense with the context of the question "how did
complexity emerge in the universe?".  The physical ideas are
interesting, but it's not what I am looking for here.

Andrew