Cellular Automata

I was browsing around the Wikipedia articles for Cellular Automata recently, and the thing that struck me about it is how easy it is to notice, if not understand, the levels of abstraction. You start with the rules of Conway's Game of Life and a few samples, easy enough. You think in terms of what a cell does. Then you learn about oscillators, periodic self-sustaining patterns, which aren't that surprising, and still on the level of individual cells.

Then you learn about Gliders, a simple pattern that in four generations gives rise to a copy of itself, but translated 1 cell away. Now we're not talking about what cells are doing anymore. We're talking about what patterns are doing, and they can move around independently from the cells used to represent them. It's a layer of abstraction.

You find out about objects like Reflectors, where when a Glider collides with it, the result is a Glider in a different direction, and things like the Glider Gun that periodically produces a new glider. You start arranging these things together to get a nice little circuit, and soon the Gliders aren't even the object of study anymore, they're just little blips that other things use to pass information. Instead of just the patterns, you now think in terms of the interactions between the patterns, which is another layer of abstraction.

And you can grok these successive layers of abstraction in 15 minutes of reading a little explanatory text and watching animated .gifs. I think the fact that Conway's Life is inherently a very visual phenomenon makes it easier to understand like that.

The article covers a lot of breadth of cellular automata. I think you get a lot more out of it if you have a tiny bit of depth in one particular automata first, so you can understand in a general sense the cool patterns and phenonema that it talks about. Quick reading on Conway's Life (selected with order in mind):

http://en.wikipedia.org/wiki/Oscillator_(cellular_automaton)

http://en.wikipedia.org/wiki/Glider_(Conways_Life)

http://en.wikipedia.org/wiki/Gun_(cellular_automaton)

http://en.wikipedia.org/wiki/Rake_(cellular_automaton)

http://en.wikipedia.org/wiki/Breeder_(cellular_automaton)

http://en.wikipedia.org/wiki/Reflector_(cellular_automaton)

Be sure to click through on the preview images to the animated version, especially rakes, breeders, and reflectors.

The post mentions a bunch of programs for playing with cellular automatons; You can check out GarlicSim, which is my project, and it's intended for simulations in general, including cellular automata:

http://garlicsim.org

Currently only Conway's Game of Life is implemented, and in a crude inefficient way, but the important thing for me with this project is to build the best infrastructure for simulations such as these. For example, I give something similar to source control management for organizing different states of the cellular automata.

I think that in a year from now GarlicSim will become one of the best programs for simulating cellular automata.

I just finished my thesis about cellular automata. Specifically, I worked on the automatic verification of logical formulas about the behavior of a given automaton.

Here's what that means. Suppose that you have some cellular automaton p, and you're interested in knowing whether p returns to its original state when you run it for a while. For finite grids and specific opening patterns this is an easy question to answer -- in theory -- you just simulate the automaton for long enough. But what about infinite grids? Or what if we wanted to answer a question like "does there exist a configuration of p which returns to its original state after 3 steps?" Or what if the automaton is just too big and too complicated to simulate for a long period of time? The majority of my work was in implementing a way of answering questions such as these (link for the really, really interested reader: http://carnegie-mellon.academia.edu/documents/0107/1998/thes...).

Cellular automata are surprisingly deep, for how simple they are. However, they aren't "a new kind of science" - like most constructs in computer science they are amenable to mathematical treatment.

If you already know a fair amount about CA, here's another good question for you to think about. How can we better classify different types of cellular automata based on their behavior? The usual classification system essentially boils down to choosing one of "it is obvious what this CA does", "you can prove what it does", "you can sort of guess what it does", and "no one has any idea so maybe this is universal". This is clearly unsatisfactory -- any suggestions?

Plenty still goes on around Game of Life. For example this self-replicating 'creature' recently found: http://conwaylife.com/forums/viewtopic.php?f=2&t=399&...

(Was featured in New Scientist I believe)

Somewhere I still have a deck of punch cards of my version of Life written in (of course) FORTRAN IV. Each generation printed out on fan-fold. Of course if it ran 'too long' I'd get kicked off of the printer, so I'd run those with different JCL during the night shift ;-)

By and large an excellent rundown, though I had a few issues with the details in places—e.g., totalistic CAs aren't anything special, they're just a restriction of the generalized rules, and happen to be used more often in many-state/many-dimension CAs because the rule enumerations just get too damn big. A niggle.

Seriously, though, some really fantastic stuff. My undergrad thesis used a lot of CAs, and some of the examples still floored me. A working prime generator with integrated LCD display? Um... what?

What's not often mentioned is that it's possible to build a Turing machine emulator as a Life pattern. That means, courtesy of the Halting Problem, that in geenral there is no decision procedure for whether a given Life pattern will expand indefinitely, oscillate, reach steady state, or die (a special case of steady state)[1].

[1] It shouldn't, but it always amuses me in crime dramas and news reports when a victim's condition is reported as "stable." After all, "dead" is stable.

My Conway's Life screensaver for Mac: http://twilightedge.com/mac/crepuscularlife/