Home » eBooks » Cellular Automata Machines

Cellular Automata Machines


The writing of this book, like the worlds that it describes, could have gone
on forever. We hope that the rest of the story will be written by our readers.
We are grateful for the help we received in our editorial task from Ed
Barton, Charles Bennett, Tom Cloney, Ray Hirschfeld, Hrvoje Hrgovcic, Mark
Smith, Pablo Tamayo, Thao Nguyen, Gerard Vichniac, and David Zaig.
We should like to thank Harold Abelson, Richard Brower, Arthur Burks,
Nicola Cabibbo, Michael Creutz, Dominique d’Humiere, Uriel Frisch,
Peter Gacs, Bill Gosper, David Griffeath, Hyman Hartman, Brosl Hasslacher,
Daniel Hillis, Giuseppe Iacopini, Leo Kadanoff, Rolf Landauer, Leonid Levin,
Mike Levitt, Stewart Nelson, Giorgio Parisi, Yves Pomeau, Claudio Rebbi,
Brian Silverman, Gerald Sussman, and Stephen Wolfram for useful
discussions and suggestions. Charles Bennett made direct contributions to the
book’s contents.
The development of a family of cellular automata machines is an offshoot
of more theoretical endeavors of the Information Mechanics Group at the MIT
Laboratory for Computer Science. Encouragement and practical support
were given by the director of the laboratory Michael Dertouzos, by Edward
Fredkin—who led the group until recently and is behind many of the ideas
presented in this book—and by the Provost, John Deutsch.
This research was supported in part by the following government agencies:
Defense Advanced Research Projects Agency (Grant No. N00014-83-10-0125),
National Science Foundation (Grant No. 8214312-1ST), and U.S. Department
of Energy (Grant No. DE-AC02-83-ER13082).
Tommaso Toffoli
Norman Margolus
November 5, 1986

In Greek mythology, the machinery of the universe was the gods themselves.
They personally tugged the sun across the sky, delivered rain and thunder,
and fed appropriate thoughts into human minds. In more recent conceptions,
the universe is created complete with its operating mechanism: once set in
motion, it runs by itself. God sits outside of it and can take delight in
watching it.
Cellular automata are stylized, synthetic universes denned by simple rules
much like those of a board game. They have their own kind of matter which
whirls around in a space and a time of their own. One can think of an
astounding variety of them. One can actually construct them,’ and watch them
evolve. As inexperienced creators, we are not likely to get a very interesting
universe on our first try; as individuals, we may have different ideas of what
makes a universe interesting, or of what we might want to do with it. In
any case, once we’ve been shown a cellular-automaton universe we’ll want to
make one ourselves; once we’ve made one, we will want to try another one.
After having made a few, we’ll be able to custom-tailor one for a particular
purpose with a certain confidence.
A cellular automata machine is a universe synthesizer. Like an organ, it
has keys and stops by which the resources of the instrument can be called
into action, combined, and reconfigured. Its color screen is a window through
which one can watch the universe that is being “played.”
This book, then, is an introductory harmony and orchestration manual
for “composers” of cellular-automaton universes.