In a usenet debate surrounding IntelligentDesign, the issue of measuring complexity kept coming up. Are there any good objective metrics for "complexity"? 

* "Number of parts" is limited because it could be a result of repetition, chaos, or waste.
* "Number of different parts" can be fudged and requires meaningful difference metrics.

KolmogorovComplexity is a good candidate.

''I am not sure it would be easy to apply such to biological systems. There may be somewhat random noise in the specimen that does not really contribute to complexity. For example, if you add a little bit of randomness to an image (dithering or "graininess"), most compression systems will use up more space even though we don't "need" the randomness. Such cannot distinguish between "useful" randomness and non-useful. In biological systems cell A may deviate from cell B purely out of randomness. Such may add to a multi-celled organism's complexity score even though it may not be necessary for survival or reproduction benefits. Perhaps it does, but the algorithm cannot tell either way. In short, it is hard to tell whether OnceAndOnlyOnce is being violated out of waste or purpose.''

SyntheticBiology provides a way of determining this. The field is still in its infancy but the determination of exactly what different parts are essential to survival and reproduction is one of its defining goals. In short, it may be hard to tell but it's not impossible and it's only going to get easier over time.

------

I'd suggest that complexity for ''interactive systems'' is determined by lengths of interaction dependency-chains.  This view accepts that the purpose of a RubeGoldberg device is to be as unnecesarily complex as possible and still accomplish a particular task.  In biological systems, you can measure complexity at the cellular level (the chains of events required for mitosis, meiosis, photosynthesis, use of ATP, removal of waste, etc.) and at higher levels (flow of blood connecting body-parts with heart introduces complexity, the mechanism utilized to staunch bleeding wounds is not particularly complex - only a few primary steps (relative to creation of proteins in the first place; the whole process of facial recognition (from light striking the face to triggering a recognition or associative-memory response in a human) is remarkably complex.

RubeGoldbergMachine and BigBallOfMud are anti-patterns regarding software complexity that suggest this is a decent metric.

The only problem here is determining proper levels of abstraction.  When dealing with levers and pivots, should you really be concerned about the complexities of their underlying structure?  You'll need a strict working definition for what qualifies as a "action dependency" that forces particular levels of abstraction.  I.e. if the slight vibrations received when the ball drops into the cup aren't necessary to move forward to the next step in the interaction chain, you can't count it.

This doesn't apply so well to non-interactive systems.  For values and descriptions, KolmogorovComplexity is almost certainly the best choice. And for pure calculation, essential algorithmic complexity (e.g. O(N*lg(N)) vs. NP-complete) might be the best we can do.

------

For software, what about '''Automatability'''? The harder it is to automate a process, the higher it scores on a complexity scale.

''Do you know of a metric for "automatability"?''

Um.....well......median bid price?

----
CategoryMetrics CategoryComplexity