Cellular Automata

An example of a cellular automata is a grid on which the squares and be in an on or off state. The system then iterates and the following state in each of the cells depends on rules linked to the state of the nearby cells. For example, the rule might be “if the cells on both sides are "on" or "off", then the cell switches "on" and if they are different, the cell switches "off". What each cell does depends on those around it, but in turn the cells around it depend on the cell.” When the system runs iteration after iteration patterns appear on the grid.

We see here that a one dimensional line of cells. All are white except for one which is black. Each cell has two other neighbors. The rules for this Cellular automata say that if all three of these cells are white, then the new state of the cell will be white; if all three of the cells are black, then the new state of the cell will also be white; in any other case, the new state of the cell will be black. The line then becomes :

And then next line is:

The first nine lines become:

We can see a complex pattern emerging from a very simple rule set that reflects Siepinski's triangle we have seen previously.

In the 1940’s John van Neumann worked on a two dimensional grid with rules based on the “Turing Machine” idea developed earlier by Alan Turing. Van Neumann’s work was developed and simplified. John Conway developed his Game of Life, which is a popularized cellular automata. Its rules are simple; if a black cell has 2 or 3 black neighbors, it stays black. If a white cell has 3 black neighbors, it becomes black. In all other cases, the cell stays or becomes white. Since the cells are so interactive the outcomes of the interlinked iterations are not obvious. Sometimes the cells stay much the same. Sometimes patterns will appear, but die out. Others will fall into cycles that repeat endlessly and still others will continue on, sometimes self organizing patterns emerge. Conway named some of the patterns boat, blinker, toad and glider. It has been shown that cellular automata can be used to perform calculations.

Cellular automata may give us clues as to how living organisms reproduce. Shapes formed within a cellular automata can sometimes reproduce themselves and exhibit some life like patterns. Perhaps the rules encoded within our DNA use a similar system to reproduce life.

Stephen Wolfram began working on cellular automata back in the 1980s. It had generally been assumed previously that the best way to describe nature was through mathematical equations, but he found that very often simple rules in a cellular automata could generate extremely complex outcomes that matched those found in nature. In 2002 he published a book called A New Kind of Science that showed how the understandings of cellular automata could apply to so many other disciplines.

Wolfram distinguished four classes of automata from the four different types of patterns that unfolded as the grids ran their course. The first he calls a homogenous state. This is where the system basically collapses to an end state almost instantaneously. This is like a point attractor.

The second class is where the automata falls into stable periodic structure. The pattern falls returns to a previous state and is caught in a limit cycle.

The third class is called chaotic, where there is no return to a previous state, continually changing in unpredictable ways as with a strange attractor.

Stephen Wolfram identified a fourth type of system, which while complex and unstable, nevertheless forms highly structured and patterned ways.

Ian Stewart has found that the patterns of cellular automata are linked to the patterns on animals skins. Chemicals are released into the pelt of the animal depending on whether or not the neighbouring area had also been coloured. In this way complex patterns are created on the bodies of animals, generated by simple chemical means.

Cellular automata have been used in such diverse areas as ferromagnetism, immunology, power grids, forest fire propagation, turbulence and crystalisation.