[Objective criterion for 'complex' status ?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Objective criterion for 'complex' status ?

(Click here to view the original thread with full colors/images)


Posted by: Thomas

Hello,

Just a very simple question: the difference between simple, chaotic and complex systems (in Wolfram's CA terminology, class I-II, III and IV respectively, IIRC) and the notion of a 'phase transition' from order to chaos with complexity in the middle are quite appealing, but most of the descriptions I find are put in informal terms.

I would like to know if there is a single, objective, calculable criterion which allows one to say: "this system is complex" or "this system is not complex (chaotic or simple)". Also, I would like to know whether there is an objective procedure which allows us, simply by observing the rules of a system, to determine whether it will be complex or not. There does not seem to be any fundamental impossibility in this.

Many thanks!


Posted by: Jason Cawley

Probably the simplest thing you can measure would be the entropy. In complex rules after any significant number of steps it will be high, essentially regardless of the initial state of the system. Simple rules will give low entropy measure later in their evolution - for some, especially from initials of low entropy measure; others, all the time.

You can try to distinguish 3s from 4s by looking at the variance of the entropy through time. 3s have nearly maximal entropy, reach it rapidly and stay there. 4s on the other hand will give a fluctuating entropy measure, can stabilize at middling values (less than fully mixed), and the eventual entropy can in general depend on the initials. Andrew Wuensch uses a 2D entropy vs. change in entropy plot as an classifier e.g.

You can measure the length of the minimal boolean expression for a later step in the system. When there are class 1 or 2 simplicities, you effectively get lots of "cancelling" in these, which a symbolic interpreter like Mathematica can simplify (akin to collecting terms in a large polynomial). The length of the minimum boolean expression grows rapidly with step number for class 3 and 4 rules.

You can look at how well various compression algorithms do at collapsing the size of the data produced by the system - things like run length encoding for example. Simple systems will show large compression, complicated ones will not. (This can be thought of as a generalization of entropy measuring).

None of these measures is going to be perfect because none makes full use of all the parameters of the underlying rule. You are mapping very large rule spaces into a binary classification (or into two such in sequence, as a tree, if you continue to the Wolfram classes).

Any such mapping is necessarily "lossy" to an extreme degree. To expect any single measure of only some aspect of much more complicated systems to correctly classify trillions of cases is unrealistic - some cases will appear intermediary or ambiguous under any measure or definition. But that will only affect fringes - any of the above will distinguish a typical complex from a typical simple system.


Posted by: Tony Smith

Chris Langton's 1990 Physica D paper "Computation at the edge of chaos: phase transitions and emergent computation" explains his investigation of one-dimensional cellular automata and proposes a simple numeric parameter, λ. Langton claimed CA rules able to perform complex computations were most likely to be found near "critical" λ values, which correlated with a phase transition between ordered and chaotic behavioral regimes.

In 1993, Melanie Mitchell, Peter Hraber, and James Crutchfield published Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations undertook a related experiment which "produced very different results" and led them to "suggest that the interpretation of the original results is not correct".

In my opinion, while a simple numerical parameter like Langton's λ was always going to prove to simplistic, the over interpretation of Mitchell, Hraber and Crutchfield's results was a key in an unfortunate retreat from the kind of deep study that the edge of chaos–border of order, aka Wolfram's Class 4, should be getting.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings