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 One-Dimensional Cellular Automata

12:00 - 1:00

LUNCH

1:00

SELF-ORGANIZED OUTINGS

Options, subject to interest and self-transport, 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) 995-1996

MONDAY

9:00

COFFEE

9:30 - 10:20

Nick Gotts:
Self-organised 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:
Continuous-valued 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 One-Dimensional Cellular Automata

Matthew Cook, Hungary

Elementary 1-D 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 1-D rules. I will discuss methods and ideas that are useful for constructive proofs of computational ability in one-dimensional 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 long-term evolution of "random" initial patterns.

Self-organised 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, self-organised 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 self-organised 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. Glider-based "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 7-bit 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 Herschel-based 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 non-equilibrium models such as diffusion-limited-aggregation (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 P-completeness. 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 time-steps 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 P-complete, in which case there is no way to predict it much faster than by explicit simulation (unless certain widely-held 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 diffusion-limited aggregation. I will also describe work with Therien et al. on understanding when a CA has the algebraic potential for P-completeness.

Synthesis of Complex Life Objects from Gliders

Mark D. Niemiec, Willoughby Hills OH

In Life, there exist many simple objects, such as still-lifes, 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, commonly-occurring 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 non-reversible computation. On the one hand, the detailed dynamics of ant behavior are fully reversible, so that no information in an ant-universe is ever truly lost. On the other hand, ant dynamics are purely transient: no state of an ant-universe 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. Bee-systems of a special kind appear to be purely transient, but no proof of this is known.

Continuous-valued CAs for Physics, Biology, and the Sheer Gnarl of It

Rudy Rucker, San Jose State University

By allowing CAs to have one or several continous-valued state variables, we can emulate a rich range of pheomena. The CAPOW software I developed with my SJSU students uses continuous-valued CAs to simulate nonlinear wave equations in one and two dimensions. The wave algorithm is based on numerical analysis considerations involving finite difference methods. "Continuous-Valued Cellular Automata for Non-Linear Wave Equations," by Daniel Ostrov and Rudy Rucker, Complex Systems 10, discusses how we reproduced a result obtained by Fermi-Pasta-Ulam back at the very dawn of CAs. My students and I are also working to reproduce some of the reaction-diffusion 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 continuous-valued 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 reaction-wave 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 spin-flip reversible interacting particle systems.) Similarly to the equilibrium models of statistical mechanics, their study is expected to shed light on the behavior of real-world 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.