Thursday, June 14, 2007

Cellular Automata

"The chess-board is the world; the pieces are the phenomena of the universe; the rules of the game are what we call the laws of Nature.
---T. H. Huxley

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."

Full article

No comments: