Page 1 of 3
You may know about Cellular Automata, if not you may know John Conway's game of Life, but why is this whole subject so important and so interesting? We take a look at not only what a CA is, but why it is so important.
The origins of CAs are difficult to pin down but back in the early 1950s Stanislaw Ulam a mathematician at Los Alamos used the first digital computers to play with patterns that evolved with time. He called them “recursively defined geometry”.
The first true CAs were probably invented by Ulam’s close friend the well-known mathematician and computer scientist Johnny Von Neumann. Ulam suggested that Von Neumann try to construct rule-based machines in an artificial universe that would help model self reproduction. He chose a chessboard universe in which each square represents a cell that can obey a set of rules. This was the first cellular automaton.
A Cellular Automaton is a very simple form of computation. If you look at the world around you what you see are things that have a position and a state. A biological cell sits at a particular spot in a clump of other cells and its state is that it is either alive or dead. You can think up other examples that are less biologically driven, but it is this one that really drives the CA idea.
So we have something, a cell, that has a location and a state.
The key next step is to ask what is it that affects the cell's state?
In most cases you would assume that the cell's state is influenced by its local neighbourhood. What matters is what is going on where the cell is not something happening miles away.
This is the assumption of localization and it is inherent in most of classical physics. A wave, say, is described by a differential equation which relates what happens at a point to what happens in an infinitesimal region around the point.
You might want to say that the local assumption is too restrictive in that it doesn't allow for long range interactions but in the physical world long range interactions occur by an influence that moves from point-to-point. Long range interactions occur by propagation of pulses and waves which depend only on local interactions.
The final CA assumption is that of locality of influence. A cell's state is only affected by the local conditions. In most cases we reduce this even further to say that a cell's state is only influenced by its current state and the states of neighboring cells.
The idea is that you start of with an initial colony of cells, each one with an initial state, and then you allow the colony to develop. This is usually done using discrete time steps - you can run CAs in continuous time, but this is more difficult. At time t you have the positions and states of all the cells; you then apply a rule that gives the state of each cell according to its current state and the state of neighbouring cells. At time t+1 the cells all change their state according to the same rule.
Clearly to define a CA you have to specify the possible states, the initial arrangement of cells and the update rule.
So what do you hope this sort of computation might be good for?
You can think of CAs as the digital version of classical differential equations which are used to describe so much of physics. However CAs aren't as easy to analyse as you might expect. The nature of the rule used in a typical CA makes it very difficult to predict what will happen given any initial condition. For example, you might like to ask if a given set of cells will oscillate, die away or grow without bound - you might like to ask, but finding an answer is much more difficult. CAs are intriguing because they are.
CAs are examples of how local rules can result in globally organized behaviour - or at least what looks like globally organized behaviour.
As an example of a CA that does something useful, consider the consider a rectangular grid of cells where each one has a state of black or white and the initial setup:
The rule that each of the cells are going to obey at the next clock tick is the following:
If you are black and have a white neighbor then stay black, otherwise turn white.
where in this case a neighbor is defined to be any cell horizontally or vertically adjacent.
What do you think the result of this simple rule is going to be when all of the cells obey it?
What might surprise you is that this rule only leaves the outline of the original shape in black:
In other words, the rule succeeded in picking out the outline of the shape. Notice that nothing but local information was used by any of the cells and yet it succeeded in extracting something that we might think of as global, i.e. the outline.
It’s the same sort of phenomenon as the displays of pictures and patterns that happen at sporting events when members of the crowd are given cards to hold up at specified times.
A global pattern can result from the application of a local rule.