Cellular Automata

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.

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 biological, 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 neighborhood. 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 that 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 that depend only on local interactions.

The final CA assumption is that of locality of influence. A cell's state is only affected by 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 off 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 neighboring cells. At time t+1, the cells all change their state according to the same rule.

To clearly 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 analyze 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 unpredictable and mostly unfathomable.

CAs are examples of how local rules can result in globally organized behavior — or at least what looks like globally organized behavior.

A CA That Finds Edges

As an example of a CA that does something useful, 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 is 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.

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.

John Conway's Life

Our example is very simple, and while it might be impressive, it is uncharacteristically easy to understand for a CA. The best known of all CAs is Conway's Life, and this seems just as simple, but it has taken a long time to work out even simple things about how it behaves, and we are still making discoveries.

This was devised in 1970 by John Horton Conway, a Cambridge mathematician who made a public appearance via Martin Gardner's column in Scientific American (Oct 1970 and Feb 1971).

The rules of Life are very simple. The universe is a rectangular grid with each grid square representing a cell, which can be either alive or dead (on or off if you want a less emotive description).

Each cell clearly has eight neighbors, and what happens at each generation depends on how many neighbors N it has:

N Next generation2 No change3 Alive or On0,1,4-8 Dead or off

Notice that the rule is very simple. If you imagine that you are a cell sitting in the middle of a huge rectangle of other cells, it is very easy for you to find out what to do. You simply count how many of your eight neighbors are alive, and if the result is 3, you set your state to "on" (irrespective of what it is currently). If it is exactly 2, then you don't change your state, and for any other value, you set your state to Off.

You can see that Life is an entirely local process in the sense that no cell has any idea of what it is going on globally. You might also think that Life is really going to be very boring and that large-scale structures are unlikely to happen — but in this case, you would be wrong.

For example, just try and predict what will happen to a line of cells — one cell, then two, then three, and so on.

A single cell dies at once.

Two cells also die at the first step, however, three cells do something remarkable and give the first hint that there is a lot going on here. Three cells arranged in a horizontal line flip to three cells in a vertical line at the next generation and then back again to three in a horizontal row. We have an oscillator!

Four cells form a solid block and then a block with a hole in it that is stable and unchanging.

Five cells go through a sequence of changes to produce a set of four 3-cell oscillators.

Six cells go through a sequence of interesting shapes and then vanish.

By now, you are probably getting the idea.

Life isn't predictable!

Enter The Glider

In fact, Life is so difficult to understand that even simple questions proved very difficult to answer. For example, are there any patterns that grow without end? In 1969, Conway discovered an interesting little pattern of five cells, which he called a glider.

What made this interesting was that a glider walks its way across the Life universe and behaves like a basic particle that can be used to build other shapes.

However, the real breakthrough came in 1970 when, in order to win a $50 prize, Bill Gosper discovered the glider gun.

This complicated arrangement of cells fired a new glider every 30 generations. At last, it was proven that there were patterns that grew without limit because the gun added five cells every 30 generations.

More important, however, was the fact that with a glider gun, you could now begin to build machines in Life space!

The streams of gliders could be used as if they were electric currents, and thus logic gates and memory could be built. Soon, a complete Life computer was constructed, proving that the simple rule involving only local behavior of each cell gave rise to something as complicated as a digital computer. In other words, it was equivalent to a universal Turing machine that could compute anything that could be computed.

After the glider gun, all sorts of interesting shapes were discovered — oscillators, movers, emitters, and so on.

The most important thing to notice is that even today, Life is an experimental subject; very little if anything has been proven theoretically. What is more, Life is just one example of a range of similar cellular automata — each a simple collection of rules that invariably lead to complex behavior.

In general, a CA is a universe of cells each of which can be in one of a number of states with the addition of a set of rules that depend only on the cells in the immediate neighborhood of the cell.

Given that these CAs are small artificial universes, you can see that we aren't doing very well at explaining them. In our own universe, we speculate that everything might well be based on some simple rule that generates all of the complexity, and hence we go in search of grand unified theories or a theory of everything. If we can't find a theory of everything in situations when we know the rules, then things look bleak!

There are a lot of 2D CAs, and indeed, Life is just an example of a set of CAs called "Totalistic." In a totalistic CA, the state of a cell is an integer that only depends on the sum of the states of its nneighbors and possibly its current state.

One Dimension

The problem with two-dimensional CAs, like the one described above and like Life, is that they are just too complicated to analyze in detail.

The solution came from the mathematician Stephen Wolfram, whose first important contribution to the theory was to reduce the situation to the point where it could be analyzed. He decided that a one-dimensional CA would be worth investigating.

The idea of a 1D CA is no different from a 2D one, but we start off with a line of agents, and at the next tick, the line is replaced by a new line determined by the rule that is being followed.

As this is only a 1D arrangement, we don't actually have to replace the existing line, just display the new line underneath, building up a complete pattern of the development of the CA. It's also possible to specify the rule in terms of the color of the agent, its two neighbors, and the color of the new cell just below.

For example, the pattern:

specifies a rule that if an agent is white and has two black neighbors, then the cell below should be black.

As there are only eight possible arrangements of neighbors, a complete rule that specifies exactly what should happen in any situation only has to list if the result of each of the eight is black or white.

By thinking of black as 1 and white as 0, you can give each neighbor pattern a number between 0 and 7 and then read off the resulting black or white cell on the next row as a set of eight zeros or ones, i.e. a binary number. This can be used as an index to specify the rule.

This means you can refer to any of the 256 rules that are possible in a 1D CA by number. This in itself is something of a conceptual breakthrough because now you can begin to think about classifying the behavior of each of the possible rules.

This is exactly what a biologist would do when confronted by a new biosphere. Once you have classified what you are looking at, you can start to see patterns and make theories up about what you are looking at.

Without classification, you are simply looking at an undifferentiated mess, no matter how interesting it might appear.

Wolfram examined all 256 of the rules by simulating them and discovered that there were four classes of behavior.

• Class 1 behaviors were boring, just resulting in all-on or all-off states.
• Those in Class 2 were also fairly boring and resulted in stable states, only slightly more interesting than Class 1.
• Class 3 produced disordered behavior — random triangles and "video noise."
• Finally, Class 4 displayed complex behaviors that included "Life-like" patterns. Class 4 patterns demonstrate that even 1D CAs have enough complexity to produce interesting behavior.

Many of these 1D CAs produce interesting patterns, and they are fun to play with. Not quite as impressive as fractals from a graphics point of view, but given the amount you put in, you seem to get a lot out — and of course this is the point!

Even 1D CAs are complex enough to make you believe that complexity can arise easily from simplicity. In fact, rule 30 has been proposed as a cryptographic method. The one-way function is just the evolution of an initial state — the message can't be cracked because it is very hard to work backward from a final configuration to the initial configuration that created it.

Generalized CA

You can invent your own type of CA — you can vary the form of the grid, the states that the cells can have, and the rules that apply. You can work in more than 2D if you want to, but this is proving to be more difficult than you might expect.

Also of interest are probabilistic CAs, where the update rule specifies a probability of a state change.

One important class of CAs is reversible. If there is a one-to-one correspondence between initial and final configurations, such CAs are, in a sense, deterministic and are generally used to model physical systems. A reversible system obeys the second law of thermodynamics and neither creates nor destroys information. Not all CAs are reversible, and many have states that can never be reached from a starting configuration — such things are very hard to prove, however.

Today's research in CAs is very broad and includes work to find new configurations in Life that do interesting things, to find 3D CAs that have specific physical properties, and to breed CAs using the genetic algorithm.

Perhaps the most important thing to realize is that CAs are a model for distributed parallel processing that might just be easier to work with than things like map/reduce and Hadoop. If you find this surprising, consider the fact that a spreadsheet is a programmable CA where each cell can have its own rule. CAs with fixed rules are a model for Single Instruction Multiple Data (SIMD) parallelism. CAs with variable rules are a model for Multiple Instruction Multiple Data (MIMD) parallelism.

Where Next

There are far too many books, papers, and websites even on CAs to give even a reasonably full list.

While A New Kind of Science is the best known of the books proposing that CAs might be a theory of everything, it's a shame to ignore some of the really good alternatives.

My favorite is currently out of print, but you can still find it second hand: Enter the Complexity Lab: Where Chaos Meets Complexity by William Roetzheim. Any of the many popular science books with words like "Complexity," "Chaos," or "Artificial Life" in the title are also worth looking at.

If you want to read a good book on the ideas but at a more academic level, try: Nonlinear Physics for Beginners: Fractals, Chaos, Pattern Formation, Solitons, Cellular Automata and Complex Systems by Lui Lam.

Related Articles and References

• Modeling Nature: Cellular Automata Simulations with Mathematica by R.J. Gaylord and K. Nishidate.
• Enter the Complexity Lab: Where Chaos Meets Complexity by William Roetzheim.
• A New Computational Universe — Fredkin’s SALT CA
• Cellular Automata by Mike James
• http://mathworld.wolfram.com/CellularAutomaton.html

Let us know your thoughts and questions in the comments section.