Intro Soup Recipe Shelf Sink Chef
Take me higher...

CA Growth: Introduction

In its simplest form, a cellular automaton (CA) is a sequence of configurations on a lattice which proceeds by iterative application of a local, homogeneous update rule. The ubiquitous example is Conway's Game of Life [Gar], [BCG]. Cellular automata were originally proposed in the late 1940s by Ulam [Ula] and von Neumann [vN] as prototypes for complex interacting systems capable of self-reproduction. Since that time the CA paradigm has been used to model spatial dynamics across the spectrum of applied science, and a vast literature, overwhelmingly empirical, has developed. Seminal papers in the area include [FHP], [Hol], [JM], and [WR]. For some more recent exemplary applications to physics, chemistry and biology, see [AL], [LDKB], [NM], and the review article [EE-K]. Now, as parallel architectures become increasingly prevalent in computer design, modelers continue to be drawn to CA systems and their extensions to inhomogeneous environments and evolutionary dynamics.

During the past half century of active cellular automaton study, rigorous results have been hard to come by. A few exactly solvable models such as the xor rules (e.g., Pascal's Triangle mod 2) have been studied in great detail, especially in one dimension [Lin], [Jen]. Some progress has been made in the formal understanding of rather abstract aspects such as symbolic dynamics, and algorithmic decidability (e.g., [Dura], [Har], [Kar], [Pap]). But there are few theorems and proofs which capture precisely the long-term behavior of specific rules. A general theory is out of the question since a Turing machine can be embedded in a CA [Ban], [Mart], [LN], while examples as simple as Conway's Life are capable of universal computation. Even the most basic parameterized families of CA systems exhibit a bewildering variety of phenomena: self-organization, metastability, turbulence, self-similarity, and so forth. From a mathematical point of view, cellular automata may rightly be viewed as discrete counterparts to nonlinear partial differential equations. As such, they are able to emulate many aspects of the world around us, while at the same time being particularly easy to implement on a computer. The downside is their resistance, for the most part, to traditional methods of deductive analysis.

Our goal in this paper is to present a mathematical overview of one particular CA topic: the theory of growth and asymptotic shape. We will restrict attention to systems on Z2, the two-dimensional integers, in which each lattice site is either empty (0) or occupied (1), and in which the set At of occupied sites at time t grows and attains a limiting geometry. Such growth models are interesting in their own right, but also have application to more general dynamics such as models for excitable media [GHH], [FGG1] and crystals [P], in which they capture the speed and shape of wave propagation. We will first describe our increasingly detailed rigorous analysis of the best-behaved rules, the Threshold Growth models. Next, we examine some simple growth rules with more complex iterates which can nevertheless be determined by a combination of computer experimentation and exact recursion. Then we turn to some rules with behavior so exotic that, at least for now, empirical study seems the only avenue to understanding. We hope that this mix of methods will effectively indicate the current state of knowledge on the subject, and that the exercises and open problems we present will foster further research.

Let us begin with a general description of CA models. At each successive time step, the sites of the system become occupied or vacant according to an update rule T which depends on the configuration in their neighborhoods. Sites use the same update rule whenever they see the same local configuration in their respective neighborhoods. In this manner, starting from an initially occupied set configuration A0 we arrive at the set An of occupied sites after t iterations of rule T. For convenience, this paper will focus on Box neighborhoods, and almost all of our case studies will use the 8 Moore neighbors conveniently described as {N,S,E,W,NE,SE,NW,SW}. Henceforth, let us abbreviate the size of the neighbor set as N. We also restrict attention to totalistic automata, in which the update rule depends only on a cell's state and the number of its occupied neighbors, but not on the arrangement of those neighbors. Thus there are {0,1}-valued maps b(i) and s(i) such that a birth occurs at lattice site x when it "sees" a number of occupied neighbors in the support of b, while the cell at x survives if the number of its occupied neighbors is in the support of s.

Next

Gravner and Griffeath

Take me higher...
Intro Soup Recipe Shelf Sink Chef