Notebooks

Cellular Automata

09 Jul 2023 12:55

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.

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

This sounds very well, but the reality was that in the '50s and '60s, computers were rare, slow, expensive, and visually incompetent. To judge from the early papers, finding a machine you could interact with was a religious experience, and one didn't object to seeing merely the hinder parts of Jehovah. (One of the first visual displays was a spare oscilloscope Ulam attached to a machine named JOHNIAC. I've seen screen photos, and they're appalling.) Even puny and blinkered boxes at the level of an Apple II were immense steps forward, since they can evolve a decent-sized Game of Life at a speed which does not require the patience of a Benedictine copyist, and in fact ever since Martin Gardner publicized Life in Scientific American, a significant fraction of the world's computing power has been devoted to the game. --- Of course, you get even better results if you build your computer with running CA in mind; and there are people at MIT, who seem to have the patience of Benedictine copyists, who have been devoting the last few decades to such "cellular automata machines."

I'm interested in them for two big reasons:

  1. My graduate advisers studied them. (See, I conceal nothing from you.)
  2. They're a good place to study self-organization. They are simple, the mechanisms at work are completely known, and they can do just about anything, without any over-all guidance or intelligence.
As the poet says,
Miraculous results have been achieved
through the simplest means:
a bottle, a prism, a lens, a fragment of paper, an apple,
and the august, etiolate skull of a sheep
high on a summer hill.

Still, I wouldn't turn up my nose at building a better screen-saver (or a better parallel computer).

See also: Complexity; Dynamics; Math I ought to learn; Pattern formation; Random fields; Self-organization; Statistical mechanics; Turbulence.

permanent link for this note   RSS feed for this note

Notebooks: