Collected Essays (29 page)

A cellular automaton rule with scrolls.

Fredkin envisioned a new science where we represent all physical quantities as packets of information. The substrate on which these packets move was to be a cellular automaton. Not to put too fine a point on it, Fredkin argued that, at some deep level, the world we live in is a huge cellular automaton. Although Conway had already expressed opinions to the effect that in a cosmically large Life simulation one might see the evolution of persistent patterns which are as intelligent as us, Fredkin was the first to suggest that the world we live in really
is
a CA.

Fredkin formed the Information Mechanics Group at MIT along with Tommaso Toffoli, Norman Margolus and Gerard Vichniac. Working together, Margolus and Toffoli built the so-called CAM-6 cellular automaton machine in 1984.

Another important 1980s figure in cellular automata was Stephen Wolfram, who wrote an important article pointing out some fundamental similarities between physics and cellular automata. (“Computer Software in Science and Mathematics”,
Scientific American
, September, 1984.) Wolfram suggested that many physical processes that seem random are in fact the deterministic outcome of computations that are simply so convoluted that they cannot be compressed into shorter form and predicted in advance. He spoke of these computations as “incompressible,” and cited cellular automata as good examples. His article included some intriguing color photographs of one-dimensional CAs.

Wolfram’s article fascinated me so much that in April, 1985, I set out to meet Wolfram, Margolus, Toffoli, and the other new cellular automatists.

Modern Cellular Automata: A Journalistic Account

We’ve been talking all afternoon and Stephen Wolfram is tired. On the computer screen in front of us, patterns are forming. We are watching the time-evolutions of various one-dimensional cellular automata. Some of the patterns are predictable as wallpaper, some are confusingly random, but just now there is one that strikes a pleasing balance between order and chaos. It’s shaped like a pyramid, with red and blue down the sides, and with a symmetrical yellow pattern in the middle—a pattern vaguely like an Indian goddess.

“What’s the number on that one?” asks Wolfram.

“398312,” answers Norman Packard, Wolfram’s associate at the Institute for Advanced Study in Princeton.

“This is the way to do scientific research,” I remark. “Sit and watch patterns, and write down the numbers of the ones you like.”

“Oh, this isn’t for science,” says Wolfram. “This is for art. Usually I just talk to scientists and businessmen, and now I’m trying to meet some artists. Wouldn’t that last one make a good poster?”

A few days later and I’m with Charles Bennett, an IBM information-theorist visiting Boston University. Bennett has a TV coupled to a computer and two naked boards full of circuits and chips. One of the boards has two tiny green lights sticking up like eyes. The board with the lights, explains Bennett, serves as a source of random zeroes and ones.

“Watch this,” says Bennett. “The Life rule starting from a primordial soup of bits. It’s a rudimentary model of evolution.”

He fiddles with his machine and the TV screen lights up with a color flea-circus: this is the “soup.” And then, as Life’s transformation rules take over, the dots begin racing around, clumping into things like worms. The worms crawl around the screen, colliding and eating each other, casting off bits of stable debris.

“That’s a glider gun,” says Bennett, pointing to a twinkling little dot-creature. A steady stream of smaller dot-patterns is pulsing out from the glider gun. “We’ve got sixty-five thousand pixels on this screen with sixty updates per second.”

Bennett shows me another pattern, one that looks like boiling red cottage cheese, and then he takes me across the Charles River to the MIT Laboratory of Computer Science. In the basement is an exuberant French scientist named Gerard Vichniac.

He and an associate are watching a small rectangular dot-pattern in the center of their terminal’s screen. The pattern is mostly white, with a small amount of red in it. The edges keep folding in on each other as the pattern evolves according to some simple rule which Vichniac made up. He calls it an “Ising Model,” but it looks like an electronic kaleidoscope. “This pattern started as a red square,” Vichniac tells me. “The rule is reversible, so we know that eventually the red square must come back. We’ve been watching it for eighty thousand steps now.”

Upstairs from Vichniac are two equally cheerful cellular automata specialists, Norman Margolus and Tommaso Toffoli. There’s another journalist there, none other than Stephen Levy, author of
Hackers
, researching a CA article for
The Whole Earth Review
. Cellular automata are hot. I introduce myself and sit down to watch the demonstration. Right now there’s a central cloud of dots, with square little patterns flying out of it. On the sides of each of the square patterns are individual pixels that pump up and down.

“Look at the critters, Tom,” says Margolus. “They look like wheelchair athletes, don’t they?”

“Show him the square rock,” says Toffoli.

Margolus clears the screen and keys a big red square into the center. The square expands out to the edges of the screen and bounces back. As the bouncing continues, the patterns interfere and form complex checkerboard patterns, enough patterns in thirty seconds to have made a respectable one-man Op-Art show in the 1960s.

Toffoli pries Margolus away from the controls and takes over. “Now we do the square rock in the toroidal pond again, but this time we add a heat-bath, a cloud of random gas in the background.”

The background fills with darting dots, and Toffoli keys another big red square into the center. This time the waves are smooth and roughly circular, much like real waves in a real pond. We try it with two squares and get interference patterns. Toffoli is pleased. He says that this shows how simple physics really is.

What is going on?

For the past fifty years, scientists thought of computers in terms of a
series
of computations, to be carried out successively. The idealized model for such computers was the Turing machine: a device which moves back and forth along a long strip of paper making marks. Turing’s model led John von Neumann to the key insight that got the computer revolution off the ground:
a computer program should contain computing instructions as well as data
.

One of the main changes often predicted for coming generations of computers is that computers might begin doing computations in
parallel
. A few such parallel computers exist, such as NASA’s seven million dollar Massively Parallel Processor at the Goddard Space Flight Center. The Connection Machine from Thinking Machines, Inc., of Cambridge, Mass., is a much sexier parallel processing machine. The Connection Machine has 64,000 processing chips. Visitors to the cellular automaton conference CA86 at MIT were invited over to the Thinking Machines offices to see the Connection Machine running cellular automata and simulating a wind-tunnel. Stephen Wolfram consulted with Thinking Machines for a short while before setting off on his own to build and distribute the mathematics program
Mathematica.
But these computers have yet to realize their full potential. The problem is that there is still no simple model of parallel computation; and there is still no good theory of how to program a parallel computer.

Cellular automata may provide the necessary new mind tool for thinking about parallel computation. A striking feature of CAs is that their eventual output is so hard to predict. In practice, the best way to predict what pattern a CA will show in, say, a hundred steps, is simply to run the CA rule itself for one hundred steps. This suggests that the best way to “program” a parallel computer may be empirical: try out several million randomly chosen cell-programs, and select the one that accomplishes your goal the best.

Probably the best-known CA worker is Stephen Wolfram, aged twenty-four. Wolfram was born in Oxford, and is said to have left home at the age of twelve. As a teenager, he published a number of papers on particle physics. He obtained his Ph.D. in physics from Cal Tech in 1980, won the MacArthur prize in 1981, and joined the Institute for Advanced Study in Princeton in 1982. And then, in the process of trying to find a model for the way in which galaxies form out of the universe’s initially chaotic state, Wolfram became interested in cellular automata.

Stocky, tousled, and seeming a bit older than his years, Wolfram speaks with the directness of a man who knows what he is doing. “Computer scientists had done some fairly worthless clean-up work on Ulam and von Neumann’s work. There were maybe a hundred papers. What I found outrageous was that none of the papers had any pictures.”

Wolfram’s papers all have pictures, lots of pictures, usually pictures of one-dimensional cellular automata evolving in time. (Wolfram’s papers are collected, along with numerous papers by other authors, in his excellent volume,
Theory and Applications of Cellular Automata,
World Scientific.) Wolfram recalls his initial investigations into one-dimensional CAs as “botanical.” He watched thousands and thousands of them on his computer until he got a feeling for what kinds of possibilities there were. He now feels that a number of very simple CAs can serve as universal computers. In Wolfram’s words, “It is possible to make things of great complexity out of things that are very simple. There is no conservation of simplicity.”

One application of CAs is to the little-understood phenomenon of turbulence. “If we had a better understanding of how complex systems work, we could use them in engineering applications,” remarks Wolfram, and goes on to tell a story about the design of the DC-10 airplane. “The wing of a DC-10 is held on by a single steel bar. Two or three steel bars would probably be better, but for more than one bar the mathematics becomes too complicated for a simulation to be carried out. The weakness of our mathematics forces us to adopt the simplest possible design.”

I ask him what engineers think of his method of modeling turbulence with CAs. “Some say it’s wrong, and some say it’s trivial. If you can get people to say both those things, you’re in quite good shape.”

Up at Boston University, Charles Bennett and the Hungarian computer scientist Peter Gacs are using two-dimensional cellular automata to model biological notions. Unlike a solid-state computer, a human brain is filled with random noise. How is it that we manage to remember things, and to think logically, when all of our mental patterns are constantly being bombarded by extraneous stimuli? Bennett and Gacs tell me they have found a CA model for the process, and they show me the screenful of boiling red cottage cheese. Despite the boiling, the cheese stays mostly red: this is the persistence of memory. Gacs says something very interesting about the device that produces the display.

“With the cellular automaton simulator, we can see many very alien scenes. We have a new world to look at, and it may tell us a lot about our world. It is like looking first into a microscope.”

Computer science is still so new that many of the people at the cutting edge have come from other fields. Though Toffoli holds degrees in physics and computer science, Bennett’s Ph.D. is in physical chemistry. And twenty-nine year old Margolus is still a graduate student in physics, his dissertation delayed by the work of inventing, with Toffoli, the CAM-6 Cellular Automaton Machine.

After watching the CAM in operation at Margolus’s office, I am sure the thing will be a hit. Just as the Moog synthesizer changed the sound of music, cellular automata will change the look of video.

I tell this to Toffoli and Margolus, and they look unconcerned. What they care most deeply about is science, about Edward Fredkin’s vision of explaining the world in terms of cellular automata and information mechanics. Margolus talks about computer hackers, and how a successful program is called “a good hack.” As the unbelievably bizarre cellular automata images flash by on his screen, Margolus leans back in his chair and smiles slyly. And then he tells me his conception of the world we live in.

“The universe is a good hack.”

CA Lab

On March 22, 1986, my fortieth birthday, I got a phone call offering me a job as a professor in the Department of Mathematics and Computer Science at San Jose State University.

In
The Unbearable Lightness of Being
, Milan Kundera talks about “the frenzy of a forty-year-old man starting a new life.” That’s how it was to move from Virginia to California with my wife and three kids and to start teaching computer courses.

During the second semester I began to understand something about what I was doing, and I wrote ANIMALS.EXE, my very first cellular automaton program, an assembly language textmode graphics display of a one-dimensional CA.

Margolus and Toffoli’s CAM-6 board was finally coming into production around then, and I got the Department to order one. The company making the boards was Systems Concepts of San Francisco; I think they cost $1500. We put our order in, and I started phoning Systems Concepts up and asking them when I was going to get my board. By then I’d gotten a copy of Margolus and Toffoli’s book,
Cellular Automata Machines
, and I was itching to start playing with the board. And still it didn’t come. Finally I told System Concepts that SJSU was going to have to cancel the purchase order. The next week they sent the board. By now it was August, 1987.

The packaging of the board was kind of incredible. It came naked, all by itself, in a plastic bag in a small box of Styrofoam peanuts. No cables, no software, no documentation. Just a three inch by twelve inch rectangle of plastic—actually two rectangles one on top of the other—completely covered with computer chips. There were two sockets at one end. I called Systems Concepts again, and they sent me a few pages of documentation. You were supposed to put a cable running your graphics card’s output into the CAM-6 board, and then plug your monitor cable into the CAM-6’s other socket. No, Systems Concepts didn’t have any cables, they were waiting for a special kind of cable from Asia. So one of the SJSU Math and CS Department techs made me a cable. All I needed then was the software to drive the board, and as soon as I phoned Toffoli he sent me a copy.