David's Blague

Now for some mechanics.

A cellular automaton is a model. Untangled from all the biological, physical, and mathematical metaphor, cellular automata are simple.

They exist on a grid of cells:


As pictured here, cells are represented by the egg shapes with letters in them. As you may have guessed, the cells give cellular automata the first part of their name. Between the cells are arrows, which declare the "neighborhood" of a cell. A cell's neighbors have arrows pointing into that cell.

Some cellular automata differentiate between one neighbor and another. In this series we'll look at some of each. Note, in passing (don't get hung up on it) that any cellular automaton that does not distinguish between neighbors can be easily represented by one that does. So the former should just be considered a kind of short-cut for the latter.

Inside each cell is exactly one member of a finite set.


Different models use different symbols in the set. 1 and 0 is very common. As is black and white. As long as the set is finite, it can also include more than two symbols.

If you're with me so far, this next piece is the last before we put it all together.

In order to pick which symbol from the finite set a cell should display, the cell examines its neighbors, and only its neighbors, and applies a rule. Programmers think of this rule as code in some programming language, but it can be even simpler than that. Here is an example of a rule:


This rule could be stated in the following casual shorthand: if exactly one of a cell's neighbors is a 1, that cell should be a 1. Otherwise, it should be a 0.

It's important to note that at least one 1200 page book has sold a fair number of copies by pointing out that a very simple rule can generate complexity out of simplicity. Put another way, complexity is simply a feature of some systems, even without entropy or chance.

The rule I just described would yield us output that looks something like this:


And with output like that, who needs a million monkeys typing?

Labels: cellular automata, deusexautomatis, etech