Here is a great weblog entry by CosmaShalizi about research into CellularAutomata. (http://bactra.org/weblog/archives/000164.html))

Quick summary of the blog article (and I have to read the papers) :

- 1) CellularAutomata can perform computation. (An example of
*TuringMachineEquivalence*)

- 2) When you try to look for (extract, abstract) commonalities from the various CA configurations which do perform computation you see two kinds of phenomena :
*Domains*and*Particles*.

To quote CosmaShalizi :

One of the more robust positive results was that, for many, many different tasks, the cellular automata evolve a system of computation based on "domains" and "particles". Domains are extended regions in space and time where the CA is repeating the same pattern over and over, possibly with a little unimportant noise incorporated into the pattern. (More exactly, domains are patterns which are left unchanged by the CA rule. For a yet more exact definition, see here or here.) Domains contain very little information, and do no computation. Particles are propagating boundaries between domains, which repeat a given cycle of states over and over and move through space at some constant velocity. They're like solitons (if you're a physicist) or gliders (if you're an aficionado of

ConwayGameOfLife). When particles meet, they interact, producing new particles or annihilating (looking rather like a Feynman diagram). Particles have a very high density of information, and particle interactions are what end up doing the computation. This is emergent computation: you can describe what's going on in terms of the domains and particles, and doing so is vastly simpler and nearly as accurate as evaluating the low-level CA dynamics, but the rules of the CA don't explicitly encode domains or particles at all; they're generated entirely by local interactions.

This is, of course, tremendously exciting. Not just because *domains* and *particles* make me think of people travelling around cities, and patterns of activity and a patterns of space.

Hmmm. "Particles have a very high density of information," can't be exactly right, can it? Because surely the information is encoded in the whole system. Without the structure or geometry imposed by the domains, the particles wouldn't mean anything. (Is the complexity in *TheBeachOrTheAnt*?) But it does remind me of FractalLoading and the notion of journeys as information processing in TheCityAsInformationSystem. I guess SpaceVsInformationFlows in general.

3) The main purpose of the article is to introduce a piece of research which demonstrates that plant-leaves do a kind of distributed computation across leaves.

4) CosmaShalizi doesn't like to draw political analogies but study of *DistributedComputation* must have some useful resonance which CollectiveActionProblems and EmergentDemocracy.

Compare RecommendationArchitecture

See also TheScientificStatusOfPatterns