CA 98 Schedule and Abstracts
Organized by
David Griffeath, University of Wisconsin
CONSTRUCTIVE CELLULAR AUTOMATA THEORY
November 14  17, 1998
Santa Fe Institute
Santa Fe, New Mexico
Jointly sponsored by SFI and the National Science
Foundation
 SATURDAY
 12:00
 LUNCH
 1:00  1:50
 Cris Moore:
How to Predict a Cellular Automaton Quickly or Prove that You (Probably) Can't
 2:00  2:50
 Noam Elkies:
An Introduction to the Facts of Life
 COFFEE
 3:30  4:20
 Janko Gravner:
Cellular Automata as Prototypes for Physical Phenomena:
nucleation, growth, diffusion and complexity
 4:30  5:20
 Norm Margolus:
Physical Worlds
 SUNDAY
 8:30
 COFFEE
 9:00  9:50
 Mark Niemiec:
Synthesis of Complex Life Objects from Gliders
 10:00  10:50
 Jim Propp:
Virtual Ants and Bees
 11:00  11:50
 Matthew Cook:
Constructive Methods for OneDimensional Cellular Automata
 12:00  1:00
 LUNCH
 1:00
 SELFORGANIZED OUTINGS
 Options, subject to interest and selftransport, with approximate cost, were:
 Bandelier National Monument: 16th century cliff dwellings
($5)
 Bradbury Science Museum: history of the Los Alamos Lab
($2)
 The Georgia O'Keefe Museum: Santa Fe's newest ($5)
 Santa Fe Detours: guided walking tour of town ($10)
 7:30
 WORKSHOP DINNER
 Cafe San Estavan
 428 Agua Fria (505) 9951996
 MONDAY
 9:00
 COFFEE
 9:30  10:20
 Nick Gotts:
Selforganised Construction in Sparse Random Arrays of Conway's Game of Life
 10:30  11:20
 Jon Machta:
Complexity of Pattern Formation in Statistical Physics
 12:00
 LUNCH
 1:30  2:20
 Roberto Schonmann:
Metastability, Nucleation and Growth in the Kinetic Ising Model
 2:30  3:20
 Rudy Rucker:
Continuousvalued CAs for Physics, Biology, and the Sheer Gnarl of It
 COFFEE
 7:30
 SHOW & TELL with Pizza
 TUESDAY
 9:00
 COFFEE
 9:30  10:20
 Dietrich Leithner:
Construction of Periodic Life Patterns
 10:30  11:20
 Jim Crutchfield:
Cellular Automata Pattern Dynamics
 11:30
 LUNCH
ABSTRACTS
 Constructive Methods for OneDimensional Cellular Automata
 Matthew Cook, Hungary
 Elementary 1D cellular automata exhibit much of the behavior
seen in any CA rule, of any dimension, with any neighborhood. Just as
constructive methods can be developed for more complicated rules like Life,
it is possible to design advanced constructions for simple 1D rules.
I will discuss methods and ideas that are useful for constructive proofs of
computational ability in onedimensional CA.

 Cellular Automata Pattern Dynamics
 Jim Crutchfield, UC  Berkeley, SFI
 I'll compare and contrast two views of cellular automata behavior. The
first, the dynamical system view, analyzes CAs in terms of state space
structures  such as attractors, their basins and separatrices  that
guide and constrain CA temporal evolution. The second view identifies the
minimal structural components into which CA configurations can be decomposed.
Synthesizing these two views leads to novel approaches to classifying CA
behavior and to measuring the complexity of CA spatial patterns.

 An Introduction to the Facts of Life
 Noam Elkies, Harvard University
 Conway's Game of Life is one of the earliest and
surely the best known and most intensively studied example
of a CA (cellular automaton). Its simple rule allows a
provably inexhaustible variety of behaviors, and continues
to present open problems and to reward new ideas with full
or partial solutions of these problems; Life may also serve
as a fertile testbed for the study of other CA rules, since
ideas and tools originally developed specifically for Life
often have much wider applicability. These tools and ideas
include useful classes of objects (still Lifes, oscillators,
gliders/spaceships, eaters, sparks, guns/rakes, spacefillers,
drifters,...) as well as software for efficiently running
and evaluating random initial states, exhaustive searches
for objects or interactions with specified properties, etc.
In the talk we review the definition of Life, give a sampling
of the many remarkable discoveries that have been made
from the time of Conway's creation of the Life rule to the
present, and indicate the key techniques, idea and tools
used to look for them and the applications and potential
applications of these methods to other CA's. We conclude
with several open problems concerning the existence of
objects with specific properties and the longterm
evolution of "random" initial patterns.

 Selforganised Construction in Sparse Random Arrays of Conway's Game of Life
 Nick Gotts, MLURI  Aberdeen
 A new approach to the study of complex cellular automata is
described, and applied to Conway's Game of Life. It is shown that in
infinite (and very large finite) random arrays of the Game of Life,
selforganised construction processes will produce coherent structures
exceeding any required number of live cells, provided the initial
probability of a cell being live is sufficiently low. These coherent
structures will include "indefinite growth clusters" that expand as
long as they have space to do so. Such selforganised construction
processes will have a crucial influence on the dynamics of infinite
and large finite arrays after a sufficient number of steps. For
finite arrays within a wide range of sizes and initial densities, they
will produce structures with dynamic properties not possessed by any
structure present in the original array. The application of the
approach to other cellular automata is discussed briefly.

 Cellular Automata as Prototypes for Physical Phenomena:
nucleation, growth, diffusion and complexity
 Janko Gravner, University of California  Davis
 One of the main selling point of cellular automata
is that rules which are extremely simple to describe
can exhibit interesting phenomena. The talk will, through
several examples, show how interplay between extensive
computer experimentation and theoretical argument sheds
light on connections between local and global structure.
Among the topics addressed will be: approximation by continuum
dynamics, effects of random perturbations, and the role that
phase transitions play in parametrized systems.

 Construction of Periodic Life Patterns
 Dietrich Leithner, German Space Operations Center, Oberpfaffenhofen
 The talk describes methods to construct
periodic patterns such as oscillators, factories and glider guns
in Conway's Game of Life. Gliderbased "classical"
techniques were the first to be developed. These techniques only
allow the construction of some oscillators, namely composite
oscillators with periods that are multiples of certain base
periods and of all glider guns with arbitrary, but pseudo,
periods p >= 14. Since its appearance in 1996, Herschel
technology, invented by David J. Buckingham, has revolutionized the construction of periodic Life patterns. It
is based on stable conduits that transport a particular 7bit
Life object (a Herschel) from one place to another.
Herschel conduits can be chained to form Herschel tracks
and, most importantly, closed Herschel loops. Herschel technology made
it possible for the first time to construct oscillators of all
periods p > =
60
and glider guns of all true periods p > = 62 (initial period limits).
Subsequently both limits were lowered by the introduction of additional
devices, including special glider eaters and oscillating (sparked)
Herschel conduits. Many examples of periodic patterns are given to
illustrate Herschelbased construction techniques. Herschel technology can
also be used for other applications. The talk concludes with an outlook on
possible future developments.

 Complexity of Pattern Formation in Statistical Physics
 Jon Machta, University of Massachusetts
 A number of models in statistical physics can viewed as probabilistic
cellular automata. These include equilibrium models such as the Ising
model and nonequilibrium models such as diffusionlimitedaggregation
(DLA) and Eden growth. In this talk I will describe some of these models
and discuss the computational complexity of generating the (fractal)
patterns produced by them. I will show that natural decision problems
associated with DLA and related models have the property of Pcompleteness.
This suggests that the DLA patterns cannot be generated quickly in
parallel. Other models, such as Eden growth, can be simulated very quickly
given sufficient parallelism. At the end of the talk I will discuss the
appropriateness of "parallel time" as a measure of physical complexity in
statistical physics.

 Physical Worlds
 Norm Margolus, M.I.T.
 Cellular Automata are closely connected to Physics. CA algorithms
embody fundamental properties of physical dynamics such as spatial
locality and finite entropy in a deterministic and exactly computable
format. CAs have been used to model a wide variety of spatially
distributed physical processes.
CA systems can be constructed which have additional attributes that
are basic to physics: processes which are exactly invertible at their
finest scale, which obey exact conservation laws, which support the
evolution of arbitrary complexity, etc. Such systems not only capture
some of the richness of physical dynamics in an informational form,
but they also enhance our ability to harness physics for computation 
algorithms which incorporate microscopic physical constraints such as
locality of interaction and invertibility can be run on microscopic
physical hardware that shares these constraints. In this talk, I will
discuss techniques for bringing CA models closer to physics, and some
of the interesting consequences of doing so.

 How to Predict a Cellular Automaton Quickly or Prove that You (Probably) Can't
 Cris Moore, Santa Fe Institute
 Given a CA's initial conditions, how fast can we predict the state t
timesteps in the future? Clearly we can do this in t steps with a
powerful parallel computer, but in some cases we can do much better. Using some nice algebraic techniques, we will show how to predict a large class of CA's in O(log t) or O(log^2 t) time. These classes include a rule similar to rule 18, with defects that diffuse and annihilate in pairs.
On the other hand, predicting our CA might be Pcomplete, in which
case there is no way to predict it much faster than by explicit simulation
(unless certain widelyheld beliefs in computer science are false). I
will give several examples of such CA's in one, two, and three dimensions,
including Life Without Death, majority voting models, lattice gases, and
sandpiles. These proofs rely on building gadgets into the CA's
initial conditions that implement logical gates, similar to Machta's work
on Ising models and diffusionlimited aggregation. I will also describe
work with Therien et al. on understanding when a CA has the algebraic
potential for Pcompleteness.

 Synthesis of Complex Life Objects from Gliders
 Mark D. Niemiec, Willoughby Hills OH
 In Life, there exist many simple objects, such as stilllifes,
oscillators, and spaceships, which occur with great frequency in
'nature.' There are many other objects, however, which can be
constructed according to Life's rules, but which appear too complex
and artificial to ever occur naturally. This talk deals with
a systematic approach to synthesizing such objects from basic,
commonlyoccurring Life components such as gliders. Techniques
used vary from the highly natural to the highly artificial.
Various generic tools have been developed for systematic synthesis
of large classes of objects. Finally, techniques for development of
new tools are discussed. Each of the points is illustrated by
several examples. This technology, pioneered by many others, and
first codified by David Buckingham, is still in relative infancy,
but demonstrates that even highly artificial objects can evolve
naturally from sufficiently large random sparse fields.
Similar applications in other CA are discussed briefly.

 Virtual Ants and Bees
 Jim Propp, University of Wisconsin
 The behavior of Langton's virtual ants on an infinite square grid lies at
an interesting junction between reversible and nonreversible computation.
On the one hand, the detailed dynamics of ant behavior are fully reversible,
so that no information in an antuniverse is ever truly lost. On the other
hand, ant dynamics are purely transient: no state of an antuniverse will
ever recur as the system evolves. The ability of such a system to perform
computation remains undetermined, but the ants' ability to create large
symmetrical structures is an intriguing clue. The behavior of "bees" (ants
on a hexagonal grid) appears to be similar in many ways, but here we are
hampered by our lack of understanding of "time's arrow" within the system.
Beesystems of a special kind appear to be purely transient, but no proof
of this is known.

 Continuousvalued CAs for Physics, Biology, and the Sheer Gnarl of It
 Rudy Rucker, San Jose State University
 By allowing CAs to have one or several continousvalued state variables,
we can emulate a rich range of pheomena. The CAPOW software I developed with
my SJSU students uses continuousvalued CAs to simulate nonlinear wave equations
in one and two dimensions. The wave algorithm is based on numerical analysis
considerations involving finite difference methods. "ContinuousValued Cellular
Automata for NonLinear Wave Equations," by Daniel Ostrov and Rudy Rucker,
Complex Systems 10, discusses how we reproduced a result obtained by
FermiPastaUlam back at the very dawn of CAs. My students and I are also
working to reproduce some of the reactiondiffusion rules found in Hans
Meinhardt's The Algorithmic Beauty of Shells. CAPOW is externally programmable,
so it is easy to add new rules. If workshop participants have suggestions for new
continuousvalued CA, we will try to implement them. One gnarly rule
of interest replaces the diffusion component of Meinhardt's algorithms
with a wave component, resulting in cellular reactionwave equations.

 Metastability, Nucleation and Growth in the Kinetic Ising Model
 Roberto Schonmann, UCLA
 Kinetic Ising models can be considered as simple statistical
mechanics models with time evolution mechanisms. (They are spinflip
reversible interacting particle systems.) Similarly to the equilibrium
models of statistical mechanics, their study is expected to shed light
on the behavior of realworld systems. Of particular interest is the
effect of the presence of a phase transition on patterns of relaxation
in such models. Simulations and analytical studies have long been
known to indicate the presence of metastable behavior, and eventual
nucleation driven by large droplets of the equilibrium phase in the
midst of the metastable phase. In this talk, rigorous results which
confirm this picture will be presented and, in particular, the role of
droplets of the so called Wulff shape will be stressed as being
of special relevance.
More CA 98
Links:
Main Page
List of Additional Participants
A CA 98 Photo Gallery
CA Resources for Participants
Santa Fe Institute
