Cellular Automata

Take a board, and divide it up into squares, like a chess-board or checker-board. These are the cells. Each cell has one of a finite number of distinct colors --- red and black, say, or (to be patriotic) red, white and blue. (We don't allow continuous shading, and every cell has just one color.) Now we come to the "automaton" part. Sitting somewhere to one side of the board is a clock, and every time the clock ticks the colors of the cells change. Each cell looks at the colors of the nearby cells, and its own color, and then applies a definite rule, the transition rule, specified in advance, to decide its color in the next clock-tick; and all the cells change at the same time. (The rule can say "Stay the same.") Each cell is a sort of very stupid computer --- in the jargon, a finite-state automaton --- and so the whole board is called a cellular automaton, or CA. To run it, you colors the cells in your favorite pattern, start the clock, and stand back.

Now that (I hope) you have a concrete picture, I can get a bit more technical, and more abstract. The cells don't have to be colored, of course; all that's important is that each cell is in one of a finite number of states at any given time. By custom they're written as the integers, starting from 0, but any "finite alphabet" will do. Usually the number of states is small, under ten, but in principle any finite number is OK. What counts as the "nearby cells", the neighborhood, varies from automaton to automaton; sometimes just the four cells on the principle directions, sometimes the corner cells, sometimes a block or diamond of larger size; in principle any arbitrary shape. You don't need to stick to a chess-board; you can use any pattern of cells which will fill the plane (or "tessellate" it; an old name for cellular automata is "tessellation structures"). And you don't have to stick to the plane; any number of dimensions is allowed. (Well, any integer number of dimensions. I doubt a fractal CA makes sense.) You do need to stick to discrete time, to clock-ticks; but CA have cousins in which time is continuous. There are various tricks for handling the edges of the board; the one which has "all the advantages of theft over honest toil" is to assume an infinite board.

One important use of CA is to mimic bits and pieces of the real world, or, as they say in the trade, to model it. You'd expect this to work well for things with lots of discrete little parts, and in fact there are CA models for crystals and percolation and such forth. But there are also CA for fluid flow (called lattice gasses), for "reaction-diffusion" systems in chemistry and other sorts of pattern formation, for insect colonies, for ecosystems, for the development of organisms, for traffic (some even vaguely convincing), even for urban growth. There's a modest industry of seeing which types of CA have various properties of interest to theoretical physicists --- time-reversibility, various sorts of symmetry, etc. There's even a current of thought pushing the idea that CA capture something really fundamental about physics, that they are more physical than the differential equations we have come to know and love these last three hundred years. I can't say I buy this myself, but I also haven't examined it very deeply.

CA were not invented, however, to be realistic models of Nature. They started with John von Neumann, who wanted to study self-reproduction, and decided that the first thing to do was ignore everything biologists had learned about the way actually existing organisms reproduce themselves. This is known as hubris, and is especially galling when it works. Von Neumann was able to prove that a certain CA can have a "general constructive automaton," a configuration of states which can construct almost any configuration of states. (Like most CA-wallahs, I used to think that it was a "universal constructor" which could build absolutely anything, but since writing the first version of this notebook I've been privileged to hear Barry McMullin discourse on von Neumann's work to the SFI journal club, and been set straight.) This was in the computational dark ages --- see below --- so he did all this work with pencil and paper. He didn't label his states with colors, but with little wiring-diagram-like icons, to help show the function of each cell. The constructor is told what to build by a "tape," a string of cells whose states the constructor read as instructions. (Back in the dark ages, computers really were programmed by punched or magnetic tape, and programming was called "taping.") If your initial set-up is a constructor, and a tape which reads

1. Build a general constructive automaton, according this plan;
2. Copy this tape into the new constructor,

then voilà, you have an automaton (constructor + tape) which will reproduce itself.

Von Neumann's design works, but it's ugly. You need twenty-nine different states, a very complicated transition rule, and a huge constructor. (Also time and patience; Dr. McMullin estimates six centuries, if each cycle of the constructor can be run in only one second, which is a bit optimistic.) Moreover the process doesn't look much like biological reproduction at all; to begin with, DNA is (as Dawkins says) a recipe, not a blue-print, and von Neumann definitely calls for blue-prints. And I don't have to tell you that, in the physical world, general constructive automata are thin on the ground --- for the moment, anyway.

Anyway, from von Neumann the torch was passed to his partner-in-crime, Stanislaw Ulam, and Arthur Burks and his "Logic of Computers" group at Michigan (Burks edited von Neumann's posthumous Theory of Self-Reproducing Automata, and one of the students in his group, E. F. Codd, was able to come up with a CA with universal construction using only eight states, and got a thesis out of it), and John Horton Conway, who devised the most notorious CA of all, the Game of Life.

Life has only two states, 1 and 0, standing for "living" and "dead", respectively. The transition rule is also simple. You look at all eight cells immediately around you. If less than two of your neighbors are alive, you die. If exactly two of your neighbors are live, you don't change. If exactly three of your neighbors are alive, you will be alive next turn, regardless of your current state. If four or more of your neighbors are alive, you are over-crowded and you die. --- Conway was thinking about colonial organisms, but it has to be one of the least convincing biological models ever. [Obviously, I wrote that before visiting the Santa Fe Institute.] It turns out that the number of interesting configurations you can make from these elements is immense: things which blink and oscillate; things which glide across the plane; things which eat the gliders; things which throw off the gliders like waste. (Enthusiasts have named all of these, and many more.) You can even prove that you can build a pukka universal computer out of these smaller configurations, and a self-reproducer, though I don't think anyone's had the patience to do it.

The growing interest in CA is, incidentally, a good example of what the late Heinz Pagels meant when he talked about "the computer and the rise of the sciences of complexity." It is extraordinarily difficult to predict, a priori, how a CA will evolve from an arbitrary starting-point; usually the only way to do it is to work the calculation through explicitly. You can try doing this by hand --- Conway used to use Go boards, and Ulam something which, from the photographs, resembled Jenga sticks, but the really interesting examples can have more than a million cells, and even if they made boards that large, it would take much too long. (Of course, if you can find more-or-less autonomous features, like the blinkers and gliders in Life, that'd speed things up; this leads into fascinating issues about causality and hierarchy and emergence and epistemology, which I may be rash enough to elaborate on another time. Onwards.) Clearly, if you want to study these things, you need something which will do lots of calculations very rapidly, and will not get bored, i.e. a computer. Von Neumann recognized this from the first, and predicted (correctly) that computer simulations would come to be used in much the same way as experiments in natural science: simulations suggest theories, which in turn suggest new simulations to check them. (Since you can also produce actual mathematical proofs about CA, but not, pace Spinoza, about Nature, the analogy is not perfect.)

Cellular Automata

Cellular automata are simulations on a linear, square, or cubic grid on which each cell can be in a single state, often just ON and OFF, and where each cell operates on its own, taking the states of its neighbors as input and showing a state as output.

One of the simplest examples of these would be a 1-dimensional cellular automaton in which each cell has two states, ON and OFF, which are represented by black and white, and where each cell turns on if at least one of its neighbors are in the ON state. When started from 1 cell, this simply creates a widening black line. When the layers are shown all at once, though, you can see that it makes a pyramidal shape.

All layers at once

For example, in the figure above, the second line is generated from doing the rule for all cells in the first line, the third line from the second line, and so on. More complicated figures can be generated from different rules, such as a cellular automaton in which a cell changes to ON if either the cell to it’s top left or top-right is ON, but not if both are on. This creates a Sierpinski Triangle when starting from a single cell:

Stephen Wolfram developed a numbering system for all cellular automata which base only on themselves, their left-hand neighbor, and their right-hand neighbor, often called the elementary cellular automata, which looks something like this for the Sierpinski Triangle automata (Rule 18):

This code has all possible ON and OFF states for three cells on the top, and the effect that it creates on the cell below them on the bottom. Using this system, we can find that there are 256 different elementary cellular automata. We can also easily create a number for each automaton by simply converting the ON and OFF states at the bottom to 1s and 0s, and then combining them to make a binary number (00010010 in the Sierpinski Triangle example). Then, we convert the binary to decimal and so get the rule number. (128*0+64*0+32*0+16*1+8*0+4*0+2*1+1*0= 18 for the example). We can also do the reverse to get a cellular automata from a number. Using this method, we can create pictures of all 255 elementary cellular automata:

Whilst some are rather boring, such as Rule 0, which is just white, or Rule 14, which is a single diagonal line.

There are many variations on this basic cellular automata type, such as an extension of the code where next-nearest neighbors are also included. This results in 4294967296 different cellular automata, a few of which appear to create almost 3-dimensional patterns such as the 3D Tetrahedrons cellular automata (rule 3283936144 ) which appears to show certain tetrahedral-ish shapes popping out of a plane.

There are also totalistic cellular automata, which are created by basing the next cell somehow on the average of the top-left, center, and top-right cells above it. These can have more than two states, and sometimes produce very strange-looking patterns, such as Rule 1599, a 3-state cellular automata:

As well as all these, there are continuous-valued cellular automata, which, instead of having cells that can only be in certain states, have the cells have real-number values. Then, at every step a function is applied to the cell that is to be changed as well as it’s neighbors. A good example of this is the Heat cellular automaton, in which the function is ((left_neighbor+old_cell+right_neighbor)/3+ a number between 0 and 1) mod 1). It produces a “boiling” effect, in which it resembles a pot of water slowly boiling on an oven.

There are tons more 1-dimensional cellular automata; Stephen Wolfram filled most of an entire (1200 page) book with these. However, there are essentially only 4 classes of cellular automata. The first type is the most boring; it is where the cellular automata evolves into a single, uniform state. An example of this would be the Rule 254 elementary cellular automata (the first example), which eventually evolves into all black. The second type, repetition, is a little more interesting, as it does not evolve into a single state but is instead repetitive. This can include a single line, simple oscillation, or fractal-like behavior, an example of which would be Rule 18. The third type is simply completely chaotic behavior- not very interesting, but definitely more than the previous two- such as in Rule 30. The last type, type 4, is where there are many individual structures that interact, sometimes passing right through, other times blowing up. An example of this would be Rule 110. This type is probably the most interesting to watch, as the eventual outcome is unknown.

Cellular Automaton

A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired. von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his "universal constructor."

Cellular automata were studied in the early 1950s as a possible model for biological systems (Wolfram 2002, p. 48). Comprehensive studies of cellular automata have been performed by S. Wolfram starting in the 1980s, and Wolfram's fundamental research in the field culminated in the publication of his book A New Kind of Science (Wolfram 2002) in which Wolfram presents a gigantic collection of results concerning automata, among which are a number of groundbreaking new discoveries.

The Season 2 episode "Bettor or Worse" (2006) of the television crime drama NUMB3RS mentions one-dimensional cellular automata.Cellular automata come in a variety of shapes and varieties. One of the most fundamental properties of a cellular automaton is the type of grid on which it is computed. The simplest such "grid" is a one-dimensional line.

In two dimensions, square, triangular, and hexagonal grids may be considered. Cellular automata may also be constructed on Cartesian grids in arbitrary numbers of dimensions, with the -dimensional integer lattice being the most common choice. Cellular automata on a -dimensional integer lattice are implemented in Mathematica as CellularAutomaton[rule, init, steps].

The number of colors (or distinct states) a cellular automaton may assume must also be specified. This number is typically an integer, with (binary) being the simplest choice. For a binary automaton, color 0 is commonly called "white," and color 1 is commonly called "black". However, cellular automata having a continuous range of possible values may also be considered.

In addition to the grid on which a cellular automaton lives and the colors its cells may assume, the neighborhood over which cells affect one another must also be specified. The simplest choice is "nearest neighbors," in which only cells directly adjacent to a given cell may be affected at each time step. Two common neighborhoods in the case of a two-dimensional cellular automaton on a square grid are the so-called Moore neighborhood (a square neighborhood) and the von Neumann neighborhood (a diamond-shaped neighborhood).



The simplest type of cellular automaton is a binary, nearest-neighbor, one-dimensional automaton. Such automata were called "elementary cellular automata" by S. Wolfram, who has extensively studied their amazing properties (Wolfram 1983; 2002, p. 57). There are 256 such automata, each of which can be indexed by a unique binary number whose decimal representation is known as the "rule" for the particular automaton. An illustration of rule 30 is shown above together with the evolution it produces after 15 steps starting from a single black cell.