Thursday, February 11, 2010

emergent behaviour papers

After this (
bbc) fantastic documentary, I thought I should restart my reading in this area. More to come!

Computations at the Edge of Chaos: Phase Transitions and Emergent Computation (Physica D | pdf | bib | 2002 )
Chris Langton

This paper examines the behaviour of Cellular Automata (CA) as one property of their rule-set changes. It is the first description of emergent behaviour occurring somewhere on the spectrum from a dull, homogeneous environment to a random, chaotic one.

The variable that is changed is lambda, a statistical variable saying how likely it is to end up in an "active" state. That is, what fraction of rules lead to a cell becoming active. As the above image shows, as lambda changes, so does the typical output patterns. These changing patterns are what first attracted me to the paper (useful for procedural?!), but the real significance is that really interesting patterns only occur for a limited range of lambda values. Too low and we don't get anything happening (deep space), too high and all we see is Chaos (center of the sun). Between we get "just right", where interesting CA's live.

Computationally we see that we need storage and transmission to get interesting systems. Storage leads to homogeneous environments (low entropy), and transmission to chaos (high entropy). Both are required for meaningful computation, and we only see them both in small parts of the range of possible CA's.

This paper caused me to put A New Kind of Science onto my must-read list.

Reverse engineering of spatial patterns in cellular automata ( springer | pdf | 2008 )
Yuuichi Ichise & Yoshiteru Ishida

This is a short paper that describes how to reverse engineer a CA from the results. They use the algorithm that you'd imagine, taking each observed result and filling in an entry in the rule-table. They also explore reverse engineering probabilistic CA's by accumulating the observed instances of each each particular rule. In both PCA (probabilistic cellular automata) and CA's case they return a CA with unknowns in the case that there is no example data. The important observation is that if there is insufficient data, there are a set of CA's that will reproduce a given pattern.