Cellular Automaton

CellularAutomata (CAs) are in essence a specialized flavor of FiniteStateAutomaton. As part of this larger family of DiscreteSystem?s, they form the foundation of ProgrammingLanguages and their compilers, the von Neumann computer architecture and SelfReproducingSystems, and other fundamental research topics in ComplexSystems and ArtificialLife.

All CAs work about the same way, though as with many such artificial constructs, any rule or assumption listed below has been questioned at least once:

A CA consists of a finite discrete space of cells. Each cell has an associated state variable, which for simplicity's sake can be thought of as being one of a finite list of integers. Each cell is associated with a fixed number of neighbors so that the whole set of cells is arranged in some particular topology.
A CA also has a fixed state transition rule, which can be thought of as a comprehensive lookup table that maps (1) the state of a cell plus the states of all its neighbors to (2) a new value for the state of the cell.
The state of the CA at any timepoint is the list of the states of all of its cells.
The initial configuration or initial state of the CA is just some set of states assigned to every cell in the CA.
Subsequent states of the CA are determined by applying the state transition rule to every cell in the CA synchronously, so that every cell's state is updated all at once. Each such update is a "time step" of the CA.

Some popular CellularAutomata

the XOR CA

A very simple CA that shows interesting behavior is the XOR CA. For example, suppose we have N cells, arranged so that each is connected to 2 neighbors in a ring topology. These cells have 2 states: "on" or "off". The XOR transition rule is: the next state of the cell is XOR(left neighbor, right neighbor). In other words,

 left  right  -> new value for me
-----  -----  -> ----------------
  00->0
  01->1
  10->1
  11->0

If we start with 13 cells in the initial configuration (where 1 = "X" and 0 = ".", and the line is actually a torus, so the left neighbor of the left cell is the rightmost cell)

..X...X.X...X

And synchronously update all the cells, over time we see

..X...X.X...X XX.X.X...X.X. XX....X.X.... XXX..X...X..X ...XX.X.X.XXX (I think I got that right) and so forth

If you play on an infinite line and start with one cell, you get PascalsTriangle? mod 2, which is basically a grainy SierpinskiTriangle?.

the Life CA

One very well-known but rather complicated CellularAutomaton is JohnHortonConway's GameOfLife. Other important work in ComplexSystems involving CAs is going at the SantaFeInstitute and other places where ComplexSystems are studied.

Electrons

A less-well-known, but still fun example is the ElectronCellularAutomata.

Ants

SixLineAntProgram

Many CellularAutomata update every cell on every iteration. Other kinds have certain "particles" that move over the grid, leaving painted lines behind. They are called ___???___ cellular automata.

CAs are interesting because

Some of them are capable of universal computation. (example: rule110) That means you could build a TuringComplete computer using just the moving & changing states of the cells. The GameOfLife is one CA where this is true. JohnVonNeumann designed but could not build a SelfReproducingSystem using a very complicated CA (when it was finally built using modern tech, it worked).
By tuning certain the parameters some CAs can be made "ordered", "complex" or "chaotic". Work with just that sort of tuning led to the current interest in the EdgeOfChaos.
CAs are in essence massively parallel systems, and are a very good model of how concurrency affects the way computation happens.
Many natural patterns, like the colors on certain cone shells or the ripples in certain sand dunes, are very well modeled by CAs.
They make good screen savers.
The herb growth patterns in AncientDomainsOfMystery? are based on Conway's GameOfLife.

As I said above, a lot of the "rules" of CAs have been broken. Allowing the connections or the number of cells to change over time based on the rules leads us to GeneralRewritingSystems? and LindemayerSystems?. Letting the transition rules in each cell be different (but fixed) leads to BooleanNetworks? and inhomogeneous CAs. Letting the number or topology of the connections between cells leads to SmallWorldNetworks and other interesting things whose names are hard to Wiki-ize. Letting the states be continuous-valued leads to CoupledOscillators?. Changing the way the cells update leads to asynchronous CAs or continuous-time CAs, also very interesting. And so forth. -- BillTozier

See http://psoup.math.wisc.edu/kitchen.html for a lively and interesting collection of info on CAs.

Sometimes people say "It's amazing that Cellular Automata can produce such an abundance of chaos and complexity from such simple rules."

This is not a profound truth about complexity and simplicity. This is an artefact of what people will consider "simple". Cellular Automata are not simple.

Take the very simple XOR 1-dimensional Cellular Automata. Say that the function f[x, t] gives the state of a cell at position x at generation t. The the general form of f[x, t] is

f[x, t] = 
f[x-1, t-1] is 0 and f[x+1, t-1] is 0 : 0
f[x-1, t-1] is 1 and f[x+1, t-1] is 0 : 1
f[x-1, t-1] is 0 and f[x+1, t-1] is 1 : 1
f[x-1, t-1] is 1 and f[x+1, t-1] is 1 : 0

Through some magic, you don't apply this formula to f[x, 0] - you just somehow know the answer for every possible value of x; this is the initial configuration.

Now, imagine that you had to write out the general formula for f[x, 1]. You'd have much the same thing, four possibilities each depending on f[x(+-)1, 0]. But what if you had to write out the full general formual for f[x, 2]? That would contain references to f[x+1, 1] and f[x-1, 1], which you would also have to expand out in full.

The full and general formula for the state of cell x at generation 20 would take many, many, many pages to write in full. Possibly a library's worth of pages.

The function giving the state of even the most simple Cellular Automata is very complex indeed. It only seems simple because we can talk about the passing of time, "generations", et al - things that we are so familiar with that some people can forget how extremely complex an element of time, and sucessive dependant iterations, can be.

Steven Wolfram's "NewKindOfScience" is arguably the definitive treatise on CellularAutomatons (CellularAutomata is the proper plural but breaks Wiki plural markup rules).

You could try and make that argument, but it would be pretty weak. Wolfram has some interesting things to say; and a lot of hot air as well. The book has a lot of great figures, and description of some interesting CA. On the other hand, other interesting systems are brushed over in favour of long extrapolations on computability and physics, which range from merely unsupported to objectively false. For all the size of the book, it is almost completely lacking in rigour, which is a shame. So no, this isn't anything near a definitive treatment. Interesting read, for all its flaws, but a better treatment would be nice to see.

Would you point out (page numbers would help) some of the "merely unsupported" and "objectively false" parts (perhaps on the NewKindOfScience page)? I'm particularly interested in the objectively false ones. It seems to me that Wolfram is attempting to advance the state of a very interesting art, and I'd prefer to build on his work by correcting his errors instead of dismissing him for making mistakes.

Wolframs book covers some interesting parts of early work in CA. He did some good work in the 80's with this; much of that is well covered. Unfortunately, he does a very poor job of acknowledging work that others did, even going so far as to imply that he discovered things that he didn't rather than fairly attributing the work. I find this, along with his rather laughable self-image, detracts from the book. The book has difficulty 'advancing' anything, as where it is (somewhat) technical it mostly covers what was state of the art decades ago, and where it isn't technical it tends to run off into flights of fancy about 'life the universe and everything' which are poorly if at all supported in the text. On the other hand, it is a very large book, and contains plenty of good stuff. It is just rather a shame that some people will pick this up in complete ignorance of the subject, and leave it with a rather badly skewed view of things, perhaps not realizing how much more material there is on the subject. There are a number of technical errors in the book, as alluded to above, and I'll try and remember to dig up a few references when I am in my office. The almost complete lack of rigour in the presentation makes some things difficult to address properly; some of these things have been well hashed out in the literature - a fact which Wolfram either ignores or is ignorant of. More later.

Thanks - I'm very interested in advancing the field, and relatively uninterested in applauding or trashing Wolfram or his book. I began this section by suggesting that NewKindOfScience is "arguably the definitive treatise on CellularAutomatons." If you know of some other published work that you feel is a more appropriate candidate as "the definitive treatise", please offer a citation so that those of us who are interested - especially those of us who "pick this up in complete ignorance of the subject" - have a better resource.

''I am not an expert in CA, but my understanding (in part from discussion with people who are experts), is that there really isn't one yet. Wolfram's book is going to be used for a long time if for nothing other than the figures, but it isn't very technically complete. There are some classic books in the subject like Toffoli and Margolis "Cellular Automata Machines" (don't have my copy here, think it is MIT press from mid 80's), but nothing, as far as I know, that would be called 'definitive'. There are a large number of primary sources, of course. From W's book alone, it will be very difficult to see how this work fits in with other areas in general. Contrary to the title, it has many connections...''