Home » eBooks » Cellular Automat. A Discrete View of the World

Cellular Automat. A Discrete View of the World

Joel L. Schiff
Copyright © 2008 by John Wiley & Sons, Inc. All rights reserved.

The history of cellular automata is only quite recent, coming to life
at the hands of two fathers, John von Neumann and Stanislaw Ulam
in the early 1950s. Subsequent work in the early 1960s included that
of Ulam and his co-workers at Los Alamos and by John Holland at
the University of Michigan whose work on adaptation continued for
several decades. Early theoretical research was conducted by Hedlund,
Moore, and Myhill, among many others, not always under the name
of cellular automata (CA), since the concept was still in its formative
stages. A big boost to the popularization of the subject came from John
Conway’s highly addictive Game of Life presented in Martin Gardner’s
October 1970 column in Scientific American. Still the study of CA
lacked much depth, analysis, and applicability and could not really be
called a scientific discipline.
All that changed in the early 1980s when physicist Stephen Wolfram
in a seminal paper, “Statistical mechanics of cellular automata,”
initiated the first serious study of cellular automata. In this work and in a
series of subsequent ones Wolfram began producing some of the images
that have now become iconic in the field. Conferences were organized
and people from various disciplines were being drawn into the field. It
is now very much an established scientific discipline with applications
found in a great many areas of science. Wolfram has counted more
than 10,000 papers referencing his original works on the subject and
the field of cellular automata has taken on a life of its own. Another
milestone in the field was the publication in 2002 of A New Kind of
Science, Wolfram’s 1200 page magnum opus, a monumental work which
brought the subject to the attention of a truly global audience.
The CA paradigm is very appealing and its inherent simplicity belies
its potential complexity. Simple local rules govern an array of cells that
update the state they are in at each tick of a clock. It has been found that
this is an excellent way to analyze a great many natural phenomena,
the reason being that most physical processes are themselves local in
nature — molecules interact locally with their neighbors, bacteria with
their neighbors, ants with theirs, and people likewise. Although natural
phenomena are also continuous, examining the system at discrete time
steps does not really diminish the power of the analysis. So in the
artificial CA world we have an unfolding microcosm of the real world.
One of the things self-evident to everyone is the order that is found
in Nature. From an ameoba to plants to animals to the universe itself,
we find incredible order everywhere. This begs the obvious questions:
Where did this order come from — how could it have originated? One
of the fundamental lessons of cellular automata is that they are capable
of self-organization. From simple local rules that say nothing
whatsoever about global behavior, we find that global order is nonetheless
preordained and manifest in so many of the biological and physical
systems that we will consider. In the words of theoretical biologist Stuart
Kauffman, it is “order for free.” It is this order for free that allows us
to emulate the order we find in Nature.
Related to the creation of order is the notion of complexity. How
can a finite collection of chemicals make up a sentient human being?
Clearly the whole is greater than the sum of its parts. How can termites
build complex structures when no individual termite who starts a nest
even lives to see its completion? The whole field of complexity has
exploded over recent years and here too C A play their part. One of the
most endearing creatures that we shall encounter is Langton’s ant in
Chapter 6, and this little creature will teach us a lot about complexity.
Of course it is no longer possible in a single text to cover every aspect
of the subject. The field, as Wolfram’s manuscript count shows, has
simply grown too large. So this monograph is merely an introduction
into the brave new world of cellular automata, hitting the highlights
as the author sees them. The mathematics in Chapter 1 serves mainly
to relate the notions of fractals, dimension, information, and entropy,
which all feature in the science of CA. And in Chapter 2, dynamical
systems are mathematical by their very nature. However, in the
remainder of the text, outbreaks of mathematics have been deliberately kept
to a minimum. On the other hand, a more advanced and mathematical
account of cellular automata can be found in the 2002 book by Ilachin-
ski. An excellent pioneering work is, Cellular Automata Machines, by
Tommaso Toffoli and Norman Margolus, both of whom have made
important contributions to the field. Many of the topics mentioned herein,
such as dynamical systems, chaos, artificial intelligence, and genetic
algorithms, are only touched upon in the context of cellular automata,
but many fine books are available on any of these. It is the author’s
intent that by being exposed to the tip-of-the-iceberg, the curious reader
will be inspired to explore the vast wonderland below.
As much as possible, the author has tried to implement Marvin Min-
sky’s dictum that “You don’t understand anything until you learn it
more than one way.” Indeed, several important notions are presented
from multiple points of view and throughout the text there are several
recurrent themes, such as point attractors, periodic cycles, and chaos,
among others.
One caveat concerning the applications of cellular automata. We
aretex not making any claims that CA models are necessarily superior
to other kinds of models or that they are even justified in every case. We
are merely presenting them as one way of looking at the world which
in some instances can be beneficial to the understanding of natural
phenomena. At the very least, I think you will find them interesting.
For those who already have a passing knowledge of the subject, I think
you will discover some new things you have not seen before. Even if
the entire universe is not one monolithic cellular automaton, as at least
one scientist believes, the journey to understanding that point of view
is well worth the price of admission.
Finally, I wish to thank Auckland University students Michael
Brough, Peter Lane, Malcolm Walsh, as well as Dylan Hirsch-Shell of
UCLA, and Nick Dudley Ward of Pattle Delamore Partners Ltd, who
produced many of the figures from the CA models given in the text, and
Samuel Dillon who produced the Rule 30 data encryption figures. Their
assistance has been invaluable as their programming skills far exceed
my own. I also wish to thank my daughter-in-law Yuka Schiff for many
of the fine graphics and my friend Michael Parish for introducing me to
the fascinating world of bees and Maeterlinck’s classic monograph. A
large debt of gratitude is owed to those who made valuable contributions
to the manuscript in one form or another: Eshel Ben-Jacob, Michael
Brough, Carlos Gershenson, Mario Giacobini, Dylan Hirsch-Shell,
Jacques Mazoyer, Marc Ratkovic, Aaron Schiff, Birgitt Schonfisch,
Dror Speiser, Guillaume Theyssier, and Jean-Baptiste Yunes. A very
special thanks to Amy Hendrickson of TgXnology, Inc. for doing such
an excellent and painstaking job laying up the text and images.
Several of the CA images were produced with the specialized
software of Stephen Wolfram’s New Kind of Science Explorer, which can
be purchased from the website http: //www. wolf ramscience . com/,
and Mirek Wojtowicz’s MCell program, which can be downloaded at
his website http://www.mirekw.com/ca/. The latter also permits
the real-time viewing of the evolution of some of the CA discussed
in the text. Another interesting CA simulator is hosted by Michael
Creutz at http://quark.phy.bnl.gov/www/xtoys/xtoys.html.
Definitely have a look at Andy Wuensche’s stunning website, http:
//www. ddlab. com/, and David Griffeath’s Primordial Soup Kitchen,
http : //psoup .math.wise . edit/welcome .html. An excellent CA
resource website now edited by Tim Tyer is at http: //caf aq. com/.
A website specifically for this text has been set up by John Wiley
& Sons at ftp://ftp.wiley.com/public/sci_tech_med/cellular__automata/.
Here there are further examples that have not been included in the
text, Java applets, CA computer code, as well as a venue for interested
readers to send in their own experimental contributions to the subject.