Cellular Automata as a Paradigm for Ecological Modeling P. Hogeweg Bioinfnmutica Paduulaan 8 Utrecht, The Netherlands ABSTRACT We review cellular automata as a modeling formalismand discusshow it can be used for modeling (spatial) ecological processes. The implications of this modeling paradigm for ecological observation are stressed. Finally we discuss some shortcom- ings of the cellular-automaton formalism and mention some extensions and generaliza- tions which may remedy these shortcomings. 1. INTRODUCTION Ecological theory comprises two disparate parts: one part is concerned with processes (e.g. population dynamics), and the other part is concerned with spatial patterns (e.g. community ecology). The two parts have little in common: the dynamic models presuppose homogeneity and immediate infor- mation transfer between the different populations (or compartments) and should therefore be considered as point models that do not have any spatial extension. The spatial models do not usually include dynamical processes. The time has come to try and weld the two parts together by developing a theory of "dynamic ecomorphology" (or ecomorphological dynamics). In other words, we will try to incorporate spatial structure in our dynamic models. The cellular-automaton formalism (and extensions thereof) seems to be a suitable one for this purpose. 2. CELLULAR AUTOMATA 2.1. Introduction and Historical Background A cellular automaton is defined as a large tesselation of identical finite-state automata (cells). Each automaton is defined as a triplet: (1, g, W), APPLIED MATHEMATICS AND COMPUTATION27:81-100 (1988) OP. Hogeweg. 1988. 81 82 P. HOGEWEG where I is the set of inputs, S is a set of states (both sets being finite), and W is the next-state function, defined on input-state pairs. The set of inputs is defined as ordered (or nonordered) n-tuples of the states of a finite set of "neighboring" cells. Thus, in a two-dimensional cellular automaton this neighborhood consists typically of four or eight cells, i.e. the adjacent cells in a square tesselation (these neighborhoods are often referred to as the Moore and von Neumann neighborhoods respectively). Typically the automata are simple in the sense that they have very few states (generally not more than two). For a small neighborhood the next-state function therefore consists of a fairly small number of rules (e.g. for the Moore neighborhood and two states it consists of at most 25 rules). The simple cellular automata as defined above are capable of surprisingly complex behavior-complex both in the formal sense (capable of universal computation) and in the intuitive sense (they generate fascinating patterns). Cellular automata were first defined and studied in the 1940s (see [6, 511). The motive behind that work was to study automata which were closer in structure to actual information processing systems than the usual idealized logical nets or Turing machines [6]. Well-known work in this period includes Von Neumann's work on "self-reproduction" and Ulam's work on "cellular auxology" (1962, reprinted in [6]), which pioneered the heuristic use of computers. Ever since, cellular automata have known long periods of dormancy punctuated with sudden periods of enthusiasm and new results. These periods can be linked to the spread of computer hardware. At the beginning of the 1970s when computers became generally available, cellular automata became popular mainly as a result of Conway's (see [17]) game of Life: a very simple e-state &neighborhood cellular automaton capable of universal computation (see e.g. [69, 51. Now that huge parallel processors have become possible (and are in fact being built-e.g. the C.A.M. [SS, 671, ~1x1~5000 [75], and the Connection Machine [25, 26]), there is a revival of interest, the emphasis being mainly on the modeling of physical processes (e.g. fluid dynamics [47, 67, 611. 2.2. Elementary Cellular-Automaton Theory: Methodology and Results In this section we give a short, nonexhaustive survey of cellular-automaton theory. The most striking feature of cellular automata is the simplicity of the rules which produce complicated behavior. Most cellular-automaton theory is concerned with this single issue. For elucidating it one either tries to find the (most) simple roles which produce a certain predefined behavior, or one observes the behavior of a predefined set of cellular automata and tries to classify the behavior relative to the transition functions. The two approaches Cellular Automata for Ecological Modeling 83 are of course not independent: results of the second approach define behavior patterns which can be studied by the first approach. The best-known results stemming from the first (top-down) approach are summarized below. (1) Universal computation. Very simple cellular automata are capable of universal computation. The game of Life [rules: if two of your eight neighbors are "on" (state 1) do not change, if three are "on", turn on; otherwise turn off] is the best-known example, but even simpler rules are possible ([2] with four neighbors; [77-791 with one-dimensional cellular automata). Universal computation in the context of such very simple and seemingly "natural' systems has received much attention and in fact acquires a significance which is not so apparent in the more "artificial" Turing machines. The ultimate fate of "ones" is undecidable and can only be obtained by direct simulation. Only if a pattern becomes apparent in such a simulation (which it may not) can one extrapolate; otherwise one has to "let it live its life." In other words: general predictions cannot be made for such simple and entirely determinis- tic systems. When the notion of "irreducible computation" (i.e., the results cannot be computed faster than by the cellular automaton itself) is combined with this notion of unpredictability, old paradoxes about determinism fade away: one cannot predict the future state and therefore one cannot change the (predetermined) future. In the flamboyant words of Fredkin [14]: "the universe is the most efficient simulation of the universe in the eye of God." This general unpredictability holds also for the statistical properties of the cellular automaton, not just for the specific configuration. Nevertheless, observed regularities can be exploited in order to make partial predictions (see e.g. [19]) because the speed of information transfer in cellular automata is limited and identical configurations change identically. These issues have been discussed repeatedly in the cellular-automata literature (e.g. [77, 78, 80, 83, 17, 181). (2) Seljkpduction. Self-reproduction was first studied by von Neu- mann in combination with universal computability. His rather complicated construct was later simplified significantly by Codd [9]. Langton [42] liberal- ized their criterion of "genuine" self-reproduction and presented a simple solution in which the self-description is stored in a dynamic loop instead of on a static tape. Self-reproduction per se can be generated in a much simpler way, e.g. by the "moduloprime" transition function [76]: if the next state is equal to the sum of the neighboring states modulo the number of states (which should be prime), any initial configuration (in any dimension, for any neighborhood) will reproduce itself after a number of timesteps depending on the size of the configuration. Moduloprime rules initialized with a random 84 P. HOGEWEG configuration show self-similar patterns for which a fractal dimension can be determined [77, 78, 54, 73, 741. (3) Con.~err~Aon laws. Most cellular automata are irreversible (and non- smjective). Starting with the set of all possible initial configurations, the automata will evolve to allow only a small subset of these configurations. In general no global conservation laws hold in such "universes." Because conservation laws are a much-studied feature of the physical universe, special cellular automata which do have interesting conservation properties are worth studying. Particularly interesting is the class of "reversible" cellular automata. Every local configuration then evolves into exactly one other local configuration, so that no information is lost and the computation can be run backwards. Starting from a structured initial configuration, "entropy" in- creases in such reversible models, but on running the automaton backward, the initial configuration will reemerge from a seemingly random configura- tion. The connection between (universal) computation and classical mechanics was first made in the billiard-ball model of computation [15]. By using only bumping balls and mirrors, and restricting initial configurations so that no head-on collisions occur, one can construct any digital computation, because every place where a collision of hard spheres within finite diameter occurs can be seen as a boolean logic gate. Kinetic energy is conserved in this model. This encoding of this billiard-ball model as a cellular automaton is less straightforward than its description would suggest: at first sight the design would need 6 states per cell and a 17-tell neighborhood, and thus many rules, of which a number should never be used. Margolus [46] invented an ingenious encoding for this model in a cellular automaton, in which only two states are used and a logic gate is spread out over four cells. If one uses an alternative updating of blocks of cells, six very simple rules suffice to simulate the billiard-ball model. For extensions and alternatives of this model for particlecollision based reversible cellular automata see [67, 61, 121. Note that these cellular automata can be seen either as models for universal computa- tion or as models of the universe. General conditions for reversible rules have been derived by Grinstein et al. [22] and Guan and He [23]. Working the other way around (i.e., starting with a class of rules and trying to find patterns in the observed behavior), Wolfram [77, 781 studied a set of linear cellular automata with varying number of states (k) and varying extent of neighborhood (r). He initialized the automata with a random configuration of zeros and ones and classified the patterns, observed in the their time evolution, into four classes: CZu.ss1: Evolution to a uniform state independent of the initial config- uration. Cellular Automata for Ecological Modeling 85 CZu.ss2: Evolution to a set of separate simple stable or periodic struc- tures; the position of these structures depends on the initial configuration, but local changes in the initial configuration propagate over a limited area only. CZu.ss 3: Evolution leading to chaotic patterns both in time and in space. A change in initial configuration eventually spreads over the entire automa- ton. These chaotic patterns are similar to chaotic behavior studied in the theory of dynamical systems under the influence of strange attractors. Such chaotic patterns give rise to a type of unpredictability that differs from the unpredictability mentioned above: in this case it depends on the impossibility of describing completely the initial configuration (the configuration of an infinite cellular automaton, or the initial state as a real number of sufficient precision). However, these patterns tend to converge rapidly to some in- variant statistical properties (e.g. fractal dimension, entropy, amplitude of fluctuations in time, etc.). Class 4: Evolution leading to complex localized structures. Sometimes long-lived; in contrast to the situation in class 2 automata, the information propagation is not limited. The cellular automata capable of universal compu- tation fall into this class. Packard and Wolfram [54] extended these studies to two-dimensional cellular automata and found the same behavioral classes, but they also found some additional interesting behavior, such as percolation and nucleation in competing domains. These patterns were studied by eye: the papers contain many beautiful (colored) pictures. This work has inspired much later work on (1) the characterization of the classes in statistical terms (see e.g. [77, 78, 73, 74, 701); (2) the representation of the behavior in other formalisms (e.g. (a) as dynamical systems [77, 78, 111, (b) algebraically [49, 391, (c) stochastically [72], (d) by partial differential equations [52], (e) as field theories [8, 441, or (f) in relation to computation theory (e.g. [79]); and (3) the relationship of the behavioral classes to the transition rules which generate them (e.g. [39]). Often, certain subsets of rules are used in these studies (e.g. additive rules). 2.3. Images of Cellular Automata Cellular automata can be studied from a number of different points of view. 1. As an architecture for fast computation. This image has become inter- esting now that processors have become cheap (they are, in fact, essentially the same as memory, and are cheaper than wire [26]). A 86 P. HOGEWEG number of cellular-automaton machines have already been built (CAM, Connection Machine, PI~IFLWOO), and it is expected that a cellular- automaton machine with 1012 sites and an update cycle of 106 ps for the whole array will be available in a decade [47]. 2. As an alternutive foTma1i.m for the study of computational complexity. As mentioned, this was the original purpose of formulating cellular automata. Much research has been done in this field. The research involves mapping sequential and parallel complexity classes onto each other. 3. As pattern-recognition devices. Some classes of cellular automata can be used as powerful pattern filters: they recognize particular features embedded in much noise, i.e., if the initial pattern is coded as the states of the cellular automaton, the cellular automaton evolves to a stable configuration in which these features are represented (possibly in en- coded form) and the noise is removed. Local pattern transformation methods (see e.g. [58, 591) and pattern segmentation methods [13] can be regarded as cellular automata as well. Likewise, models of e.g. stereopsis, whether interpreted as biological model or as computational technique, are in the form of cellular automata (see e.g. [48, Chapter 31). 4. As modeling devices. Modeling devices are the image of cellular au- tomata with which we are primarily concerned. This image can take several forms (compare [68]). 4.1. As computatioruzl tools for independently formulated models. In this case the cellular automaton is seen as an approximation. In fact, every computer implementation of partial differential equa- tions (PDEs) is a cellular-automaton simulation: of necessity, time and space are discretized and so are the variables. Therefore such models fall into the formal definition of cellular automata, al- though not into their typical image: the number of states is (very) large, and the transition function takes a specific (algebraic) form. 4.2. As models of actual physical phemmwnu. Traditionally most physical phenomena are modeled in terms of continuum models. This practice started in physics at the time when it was mainly continuous phenomena that were studied and has been mimicked by many other sciences (including ecology) even when the primary data on the systems are not in terms of continua but in terms of discrete entities (e.g. organisms). However, the conceptual models of physics are nowadays in terms of discrete particles. Only comparatively recently have models of physical phenomena been formulated in terms of discrete systems, e.g. cellular automata as Cellular Automata for Ecological Modeling 87 an alternative to differential equations rather than as approxima- tion [65]. Examples include fluiddynamic models [47, 84, 611, which are traditionally modeled by the Navier-Stokes equations and approximated by PDE simulations. They are now studied in a cellular-automaton formulation, and the Navier-Stokes equations are shown to approximate them in the macroscopic limit [12]. Note also that these models are entirely deterministic, whereas the discrete micro conceptualization traditionally assumes that the micro entities behave stochastically (see [20]): local information overrides the need for randomness (see also [63]). It is interesting to note that not long ago catastrophe theory [64, 81, 571 became popular because it bridged the gap between a continuous micro- system and discrete macro observations. Cellular automata bridge the gap in the opposite direction: the entirely discrete micro transition rules of cellular automata can give rise to continuous macro behavior (e.g. diffusion etc). However, cellular automata can also give rise to large-scale discontinuities such as those studied in catastrophe applications (see e.g. [l]). 4.3. As "paradigm systems." Paradigm systems [29, 30, 321 are not designed to simulate particular observed phenomena, but rather they embody certain concepts. Thus, a given cellular automaton defines its own universe. The behavior of such a universe can be compared to the observed (hypothesized) behavior of another universe (e.g. "reality"). It turns out [68] that many cellular-au- tomaton universes are inhabited by beings that are most often seen in the menagerie of theoretical physicists. The beings include (1) symmetries and symmetry breaking, (2) conservation laws (in particular in reversible cellular automata; see e.g. [46, 56, 221) (3) a conspicuous arrow of time (in cellular-automaton theory the concept of Gardenof-Eden configurations is well known (Moore, 1962; Myhill, 1963-both reprinted in [6]; see also WI), (4) order parameters and ergodicity (see e.g. [56, 46, 161; the last falsifies an ergodicity conjecture using a cellular-automaton model), and (5) relaxation to chaos (e.g. chemical turbulence: the dynamics of the Belousov-Zhabotinsky reaction can be obtained by a very simple three-state cellular automaton [53]). The most important feature is, however, the appearance of com- plex phenomena and large-scale correlations resulting merely from very simple short-range interactions. 88 P. HOGEWEG Ulam called this approach "imaginary physics" as opposed to "real physics" (which is what is studied in the first two images of cellular-automa- ton modeling). Hogeweg and Hesper [30,34] have argued that "real" science (as opposed to application oriented endeavors) often involves the study of paradigm systems, and that the borderline between the two is not well defined. 3. CELLULAR AUTOMATA AS A PARADIGM FOR ECOLOGICAL MODELING 3.1. On Choosing a Modeling Form&m In many modeling efforts little attention is given to choosing a suitable modeling formalism: the choice is most often made on the basis of habit within a certain research area (e.g., in insect population dynamics discrete timestep models are most often used even in the case of overlapping generations, whereas in other population-dynamics areas continuous models abound, even in the case of nonoverlapping generations). However, the choice of modeling formalisms is important because it determines to a large extent the model potential (e.g., what is easy and what is difficult to model). An important guideline for the choice of models is the classical simplicity principle (Occam's razor), and the modeling formalism determines what can be modeled in a simple way. Moreover, modeling formalisms shape our notion of simplicity. Thus, in classical models, simplicity most often resides in the number of variables and/or in the algebraic form of the interactions (linear versus nonlinear). Cellular-automata models incorporate a quite differ- ent criterion of simplicity: the number of variables is huge (even infinite in an infinite tesselation; see below). However, the number of states of each of the variables is typically small (thus allowing for a qualitative rather than a quantitative description), and the interactions are often nonalgebraic (i.e. they take the form of a set of rules). However, the most important source of simplicity is in the locality (of variables and of the interactions). Note that in population-dynamic models both variables and interactions are global: a change in one population is seen immediately by all members of this and other populations. Another important factor in the choice of modeling formalism relates to what can be observed in the model. In most classical ecological models the models are formulated in terms of observed variables. Such models can be called one-level models. Systems theory has developed a powerful set of tools to generate models which produce observed behavior: given a set of input- output pairs, a model (even a large set of models) can be generated which produces these input-output pairs. In evaluating the applicability of these Cellular Automata forEcological Modeling 89 system-theoretic tools Casti [7] complains that experimentalists are often more interested in finding new observables than in modeling previously observed phenomena; therefore modelers and experimentalists have little ground in common. In my opinion searching for new observables is indeed an important endeavor, both for an experimentalist and for a modeler. The latter can pursue this objective profitably in multilevel models, i.e. when the variables in which the model is formulated are different from those which are to be observed in the model [30, 34. Cellular automata allow for such multilevel modeling in ecology. 3.2. Modeling Vegetation Succession with Cellular Automata 3.2.1. Introduction. In his well-known model of forest succession Horn [36, 371 depicts a forest as consisting of a grid of plots each containing one full-grown tree and some saplings. When the full-grown tree dies, one of the saplings will take over. The model for forest succession which he derives from this mental picture is V(t) = MT(O) where V is a vector of the number of trees of each species, and M is the transition matrix which gives the frequencies with which each tree species will be replaced by each of the other tree species. M can be derived empirically from the frequency of saplings of the various species under each tree species and the mean age of the trees. Elementary linear algebra tells us what will happen to the modeled forest in the long run: irrespective of the initial state, the species composition of the forest will converge to the composition given by the eigenvector associated with the largest eigenvalue of M, i.e. will converge to a climax vegetation. In "pathological" cases when there are two equally large eigenvalues, the final composition will depend on the initial composition. For almost equally large eigenvalues, convergence to the final climax is very slow. If in addition to having differential equations and linear algebra, we also have in our bag of tools cellular automata, the mental picture sketched by Horn points to a model in terms of a cellular automaton: i.e. in terms of a grid of cells with a local transition function dependent on the state of the cell and that of the neighboring cells. The cells are readily identified with the plots, and the state of the cell with the full-grown tree species which inhabits it. Horn's model can be modeled in the cellular-automaton framework using a probabilistic next-state function and an empty neighborhood. His results are determined by the empty neighborhood. The obvious advantage of modeling P. HOGEWEG the envisaged system in the linear-algebra framework is that the global properties of the system can be assessed easily. On the other hand, there are at least two advantages to modeling the envisaged system as a cellular automaton, namely extendability and observability. (1) Extendability. Within the cellular-automaton formalism the assump- tions incorporated in the model become more visible and alternatives to these assumptions present themselves as straightforward extensions. For example, a prerequisite for an empty- neighborhood is the assumption of global seed availability which is everywhere the same and independent of past and present species composition (except possibly for the just-vanished tree in the plot under consideration), whereas modification of the environment (which determines the outcome of the competition between seeds or saplings) is entirely limited to the plot under consideration and depends on the species of the just-vanished tree. Thus, a nonempty neighborhood is certainly a worthwhile alternative, and can be modeled in a large number of different ways (each incorporating specific ecological hypotheses), using either prob- abilistic or deterministic automata. (2) Observability. The model can be studied in ways very similar to the ways in which the "real" system can be studied, because the output of the model is similar in detail to the "real" system and comprises not only the species composition (in time) but also the spatial patterning of the species (see [35]). I Moreover, with respect to the observables of the Horn model (species composition), elementary cellular-automata theory (like nonlinear population models with multiple steady states) gives counterexamples for the results of the Horn model. Convergence to a species composition independent of the initial species composition is still quite possible but not necessary: an initial configuration with identical frequencies of species may even evolve to qualitatively different final states. (Note however that most cellular automata evolve statistically similar patterns, independent of the initial (random) state 177, 781.) As an extreme example consider the following (deterministic) cellular automaton: each cell of the automaton represents a (small) piece of land; its state represents the species occupying this piece of land. Individuals may extend over several cells. Thus there are n states, where n is the number of (potential) species in the area. The cells are arranged in a square lattice, and the eight cells surrounding it (four adjoining, four diagonal) are regarded as the neighborhood, i.e., they influence the plot under consideration. At least some species grow and decline according to the following rules: (1) if a species occupies only one or two cells, it is too small to survive and dies; (2) the species cannot form too dense stands, i.e. it does not remain in a cell Cellular Automata for Ecological Modeling 91 surrounded by more than three cells occupying the same species; (3) an individual occupying at least three cells is in good shape and reproduces (or grows) into surrounding cells; (4) if several species want to grow into a cell, there is a competition hierarchy deciding which one will occupy the cell. In other words, some species behave according to the rules of the game of Life. We therefore expect that such a vegetation will share the properties of the game of Life: survival of species can only be predicted from the initial configuration by explicit simulation, which may take a very long time. It is not only the initial configuration described in terms of the number of cells occupied by each species, but also the specific configuration in which they occur, that determines the outcome of the "succession." Vegetation as a universal computational device may seem somewhat far-fetched, and indeed simple rules which give rise to such a measure of unpredictability are rare (a few per cent) among linear cellular automata, but they seem even rarer among two-dimensional cellular automata because dimensions behaving chaotically mask the universalcomputation features in such systems [77-79,541. Such models do however account for the possibility of a species suddenly "catching on": after a long period of borderline existence, a sudden expansion (possibly followed by a sudden decline). Another example of models in which the final state depends on the initial configuration is the class of cellular automata with "voting" rules, i.e., the next state depends on the number of neighboring cells in the various states. In this case the initial configuration is expressed as the frequency of each state. Twostate automata of this type are (again) the ones most extensively studied (they are in this case instances of "threshold functions" as studied in neural nets). Such rules give rise to two different types of phenomena: nucleation and percolation [68]. (1) NucZeution. Starting with a random initial configuration, many au- tomata turn off during the first steps (being surrounded by too many zeros); the remaining ones then start to grow by filling concavities and stop growing when they acquire a convex shape. However, when two clusters almost meet, new concavities are created and filled. Depending on the frequency, either the entire array becomes filled with ones or clusters of ones remain separated by a sea of zeros. This latter case is only metastable: on an infinite lattice an exceptional fluctuation will grow for ever and cover the entire array in the thermodynamic limit. (2) Percolation. The growth of ones (or zeros) is always limited. Below a certain threshold frequency of ones they form isolated clusters; above this threshold they form a connected network in which islands of zeros remain. Stated more generally, "class 2" cellular automata [54] evolve to a pattern in which different "phases" alternate and possibly compete for space. The 92 P. HOGEWEG boundaries between such phases can behave either as if they had positive surface tension (the boundaries straighten out) or as if they had negative surface tension (more and more convoluted patterns occur in time (see [60]). These patterns, and their multistate analogues, seem very interesting in the context of vegetation succession: both types of behavior seem to occur in vegetations (compare the "balloon effect" [35]). 3.2.2. Some Examples of Cellular-Automaton Models for Succession. In this section we mention some of the current research that is being done in modeling vegetation succession with cellular automata. Much more explora- tory work is however needed to obtain a coherent theory of vegetation succession. Green et al. [21] mention some preliminary results of a cellular automaton designed to study fire based succession in Australian forests. The only interaction between cells is at the time of a fire (which spreads), otherwise there is a linear sequence of states (barren, grassland forest). These authors show that forest zones emerge after random initialization. Levin [43] also reports on a disturbance based succession. Like Green et al., he also uses a neighborhood which is empty except for the impact of a disturbance, the size of which depends on the age of the (randomly chosen) disturbed cell. He shows that the resulting pattern is self-similar at different scales. In contrast, Dees and Hogeweg [85], motivated by data showing different patterns at different scales [35], are studying succession in cellular automata in which the neighborhood is not empty but includes the eight neighbors in a square grid. The (probabilistic) next-state function assigns to a cell a species which is equal to one of the neighboring species (with probabilities equal to their frequencies) or to an "influx species" (with a small probability). The latter probability is varied to obtain different environments: when it is large the local seed production (or clonal expansion) is low, and vice versa. This environmental-quulity parameter is the same for all species (20 or 40 in our simulations): the species differ only in age and influx. These two properties are varied in an r/K selected manner; longevity is inversely related to influx. The resulting succession is shown in Figure l(a)-(d); it is clearly seen that species composition and the patch size change during the succession. More- over, it turns out that the environmentalquality parameter gives rise to a spacetime pattern in differences between plots very similar to the pattern observed in our reference dataset [35]. Initially the temporal difference dominates, whereas later on the spatial differences dominate. In the observed succession these patterns differ when studied at different scales. 3.2.3. Cellular-Automaton Models Versus Field Data. It is an interest- ing exercise to generate data according to some cellular-automaton rule (e.g. Cellular Automata for Ecological Modeling (a) (b) (4 FIG. 1. Vegetation succession in a cellular automaton. one which leads to multiple stable points), and subsequently to build a global model to "explain" these data (e.g. Horn's succession model). If we allow ourselves enough freedom, and confine ourselves to observables shared by both models (in this case species frequencies), this can easily be done. For example, when the next state depends on the neighborhood of the cell under consideration, and we estimate the next state function independently of the neighborhood and average over all observed state transitions, the resulting neighborhood-independent value will approximate what is happening in the succession. Moreover, the different initial states which lead to different final states can be considered as different "environments" requiring a different transition function. In field data we never observe "all possible initial conditions," and we are always forced to choose a lumping of the observa- tions (to obtain statistical averages) and splitting of the observations (to delineate the system). 94 P. HOGEWEG "Data oriented" models, with a minimum of spatial interactions, often seem to give very good predictions (e.g. Shugart's Foret model). By restrict- ing the possible neighborhoods (a Foret plot is supposed to be surrounded by similar plots, and not to be in the middle of a desert), neighborhood-based properties can be replaced by within-plot properties and possibly vice versa. Simplicity and generality, ease of measurement, and applicability can lead to different choices of the model. However, for the time being it seems useful to extend our intuition about what simple, uniform, neighborhood-dependent rules can do with respect to generating patterns which may also occur in ecosystems. 4. EXTENSIONS OF CELLULAR AUTOMATA Cellular automata are in fact a special case of a wider class of formalisms, which Smith [62] called polyautomutu. All polyautomata consist of finite-state automata (cells) which are interconnected, which form each other's input and output neighborhoods, and which change their state synchronously. Dis- tinguishing features include (1) finite versus infinite number of cells (automaton versus space); (2) uniform versus nonuniform (either with respect to automata or with respect to connections; for a recent review of such networks in biology and physics see [71]; well-known nonuniform cellular networks include e.g. neural networks and Kauffman networks [40, 411); (3) deterministic versus nondeterministic; (4) with or without external input/output; and (5) static versus dynamic (in static systems the (number of) cells and interconnections of cells, whether uniform or nonuniform, are fixed; in dynamic systems, however [45, 241, cells and therefore interactions are generated as part of the behavior of a cell). (Note that in this list the properties of cellular automata are mentioned first.) Cellular automata, or their nondeterministic counterparts, possibly with a distributed external input, seem to be well suited for modeling spatial ecological processes if the individual automata (cells) represent (small) areas whose state represents the species which inhabits this area. However, there are two shortcomings of the cellular-automaton formalism which should be mentioned. 4.1. Synchrony Polyautomata are by definition synchronous. This synchrony derives from definitional simplicity: the entire cellular automaton is again a finite-state (for Cellular Automata for Ecological Modeling 95 a finite number of cells) or an infinite-state (for an infinite number of cells) automaton. Synchrony is, however at variance with the localness of cellular automata, which is their major strength. To achieve synchrony one needs a global clock. Particularly in the case of a small number of states (the second major strength of cellular automata), synchrony can influence the qualitative behavior of the system considerably by imposing this global constraint. The author [28] demonstrated this for dynamic polyautomata, where asynchrony led to the disappearance of the interesting structure in a class of such automata. However, we also showed that local synchronization brought back these interesting features. More recently Ingerson and Buvel [38] have studied Wolfram's one-dimensional cellular automata, dropping the syn- chrony constraint. They found some types of self-organizing behavior not found in the synchronous counterparts, where it was apparently masked by irrelevant apparent structure which derives from the synchronization. For example, they found the formation of large coherent regions which compete for space, one side eventually dominating. The transition rules they used showed in the synchronous case self-similarity and periodic limit cycles. Such competing regions (reminiscent of desertification) occur only in two-dimen- sional synchronous cellular automata; apparently this feature benefits from more degrees of freedom, which are supplied either by asynchrony or by more neighbors. Vichniac [68] also showed that synchronization can lead to artefacts, which can only be eliminated by using less straightforward and more complex model formulations: The Ising system of ferromagnetism points to a cellular- automaton model with two states only (up and down). However, synchrony and determinism then lead to large-scale correlations and to (nonphysical) instability. This problem can be overcome by adding more states. Zeigler [82] defines discrete-vent versions of cellular automata, and discusses their use in theoretical physics. Hogeweg and Hesper [29] show that discreteevent cellular automata allow for very elegant and flexible continu- ousdiscrete and discretecontinuous multiple micro-macro transitions. Park et al. [55] defined a filter automaton in which a new state is computed as soon as a state becomes available. They show that as a class these filter automata are equivalent to cellular automata, but they produce space genera- tion values in a different order. Moreover they show that such filter automata can produce interesting behavior (e.g., solitons and collisions which preserve the identity of "particles" are common). Nakamura [50] presents a transformation between synchronous and asynchronous cellular automata and uses this transformation to construct asynchronous cellular automata capable of universal computation. Because synchrony is obviously not a property of natural systems, it should be dropped from the formalism or treated with caution. 96 P. HOGEWEG 4.1.2. Space-Orientedness. A suitable interpretation of cellular au- tomata in an ecological context is that the automata represent small areas and that their state represents the organisms inhabiting this area and/or environ- mental conditions, i.e., the "active" elements are areas, not organisms. Note that the cellular automaton forces this viewpoint on us and precludes the alternative view according to which the "automata" are organisms whose state includes their position in space. The latter view may however lead to conceptually (and possibly also computationally) simpler models. This is particularly the case if the organisms have memory, and can be illustrated by trying to encode Beeler's [4] worm (or memory variants thereof [27]) as a cellular automaton: this encoding is possible, but most solutions are ugly and mask the informational simplicity of the model (see however the elegant particle simulation in cellular automata of Margolus [46]). A nice example of an organism-oriented view of vegetation processes is the work of Bell et al. [3]: on the basis of observed plant architecture they simulate long-term population processes. The organismoriented view requires a nonsynchronous dynamic "polyautomaton" (because of the asynchrony, it is doubtful if we should call it this) in which interactions are established on the basis of spatial proximity [and not on the basis of ancestry as is the case in formal language- oriented dynamical polyautomata (e.g. Gsystems)]. We have developed the MIRROR modeling formalism in order to satisfy this purpose. Efficient imple- mentation of such formalism needs a more flexible architecture than cellular automata have, but it does seem to be possible [32], for example on the Connection Machine [26], which allows for addressable interconnections between cells. 5. CONCLUSION Thus we conclude that cellular automata are a suitable formalism to model space-oriented ecological processes. For organism-oriented ecological processes other formalisms are more suitable. Both types of models need the highly parallel machines which are now being developed. We hope that ecology will meet the challenge which these machines pose. I thank A. P. Dess for supplying the pictures of vegetation succession in cellular automata. 1 thank Dr. B. Hesper for discussions and corrections in the munuscript. REFERENCES 1 K. Aoki and N. Mugibayashi, Cellular automata and coupled chaos developed in a lattice chain of N equivalent switching elements, Phys. Lett. 114A(8, 9):425-429 (1986). Cellular Automata forEcological Modeling 97 2 E. R. Banks, Information Processing and Transmission in CehuIar Automata, MIT MAC-TR-81, 1971. 3 A. D. Bell, D. Roberts, and A. Smith, Branching patterns: The simulation of plant architecture, 1. Theuret. Biol. 81:351-375 (1979). 4 M. Beeler, Patterson's Worm, AI. Memo 290, MIT, 1973. 5 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways forYour Mathemutical Plays, Vol. II, Academic, 1982, Chapter 25. 6 A. W. Burks (Ed.) Essays on Cellular Automata, Univ. of Illinois Press, 1970, 375 PP. 7 J. Casti, 1986. Unpublished manuscript. 8 S. Chen, Cellular processing and statistical mechanics, Lett. Math. Phys. 10:207-212 (1985). 9 E. F. Codd, Cellular Automata, Academic, 1968, 122 pp. 10 J. H. Conway, The game of Life, described in [17, 181. 11 J. Demongeot, J. Cole, and M. Tchuente, Dynamical Systems and CeEZuZar Automata, Academic, 1985. 12 U. Frisch, B. Has&her, and Y. Pomeau, A lattice gas automaton for the Navier-Stokes equations, Phys. Reo. Lett. 56:1505 (1986). 13 J. Fairfield, A cellular approach for image segmentation using Voronoi diagrams, in Cat. no. 85CH22293, IEEE Comput. Sot. Press, 1985. 14 E. Fredkin, Course on celh&r automata, MIT, 1973. 15 E. Fredkin and T. Toffoli, Conservative logic, Internut. T'heoret. Phys. 21:219-253 (1982). 16 P. Gacs, Reliable computation with cellular automata, J. Ccvnput. Systems Sci. 32(1):15-78 (1986). 17 M. Gardner, Mathematical games: The fantastic combinations of John Conway's new solitary game of "Life," Sci. Amer., Oct. 1970, pp. 120-123. 18 M. Gardner, Mathematical games: On cellular automata, self-reproduction, the Garden of Eden and the game of "Life," Sci. Amer., Feb. 1971, pp. 112-117. 19 R. W. Gosper, Exploiting regularities in large ceIluIar spaces, Phys. D lOD:75-80 (1984); reprinted in Cellular Automata (D. Farmer et al, Eds.). 20 P. Grassberger, Chaos and diffusion in deterministic celhrlar automata, Phys. D lOD:52-58 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 21 D. G. Green, R. H. Bradbury, and R. Reichelt, Formal Languages and Biological Pattern, manuscript, 1986. 22 G. Grinstein, C. Jayaprakash, and Y. He, Statistical mechanics of probabilistic ceIh&u automata, Phys. Reo. Lett. 55(23):2527-2531 (1985). 23 P. Guan and Y. He, Exact results for deterministic cellular automata with additive rules, 1. Statist. Phys. 43(3, 4):463-478 (1986). 24 G. T. Herman and G. Rosenberg, Developmental Systems and Languages, North Holland, 1975. 25 W. D. Hihis, The Connection Machine: A computer architecture based on cellular automata, Phys. D lOD:213-228 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 26 W. D. Hillis, The Connection Machine, MIT Press, 1985, 190 pp. 27 P. Hogeweg, Topics in Biological Pattern Analysis, Thesis, R.U. Utrecht, 1976. 98 P. HOGEWEG 28 P. Hogeweg, Locally synchronised developmental systems, conceptual advantages of the discrete event formalism, Internat. J. Gcn. Systems 6:57-73 (1980). 29 P. Hogeweg and B. Hesper, Two predators and a prey in a patchy environment: An application of MICMAC modelling, J. Theoret. Biol. 93:411-432 (1981). 30 P. Hogeweg and B. Hesper, On the role of OBSERVERS in large scale systems, in UKSC Confmence on Computer Simulation, Westbury House, Harrogate, 1981, pp. 420-425. 31 P. Hogeweg and B. Hesper, The ontogeny of the interaction structure in bumble bee colonies: A MIRROR model, Behao. Ecol. Sociobiol. 12:271-283 (1983). 32 P. Hogeweg and B. Hesper, Socioinformatic processes, a MIRROR modelhng methodology, 1. Thearet. BioZ. 113:311-330 (1985). 33 P. Hogeweg and B. Hesper, Interesting events and distributed systems, in SCS Multiconference 1985, pp. 81-87. 34 P. Hogeweg and B. Hesper, Knowledge seeking in variable structure models, in Simulation in the Artificial Intelligence Era (Elzas, Oren, and Klir, Eds.), North Holland, 1986. 35 P. Hogeweg, B. Hesper, C. P. van Schaik, and W. G. Beeftink, Patterns in vegetation succession, an ecomorphological study, in The Population Structure of Vegetation (J. White, Ed.), Dr. W. Junk Publ., 1985, pp. 637-666. 36 H. S. Horn, Markovian processes of forest succession, in Ecology and Evolution of Communities (M. L. Cody and J. M. Diamond, Eds.), Belknap, Harvard U.P., 1975, pp. 196-213. 37 H. S. Horn, Succession, in Theoretical Ecology, Principles and Applications (R. May, Ed.), Blackwell Scientific, 1976, pp. 187-204. 38 T. E. Ingerson and R. L. Buvel, Structure in asynchronous cellular automata, Phys. D lOD:59-68 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 39 E. Jen, Global properties of cellular automata, J. Statist. Phys. 43(1, 2):219-265 (1986). 40 S. A. Kaufmann, Metabolic stability and epigenesis; randomly structured genetic networks, J. Theoret. BioZ. 22:437-467 (1969). 41 S. A. Kauffmann, Emergent properties in random complex automata, Phys. D lOD:145-156 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 42 C. G. Langton, Self-reproduction in cellular automata, Phys. D lOD:135-144 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 43 S. Levin, Presented at the workshop Supercomputers in Landscape Dynamics, Fort Collins, Colo., 1986. 44 D. A. Lind, Applications of ergodic theory and sofic systems to cellular automata, Phys. D lOD:36-44 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 45 A. Lindenmayer, Mathematical models for cellular interactions in development, I, II, J. Theuret. BioZ. 18:280-299, 300-312 (1968). 46 N. Margolus, Physics-like models of computation, Phys. D lOD:81-95 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 47 N. Margolus, T. Toffoli and G. Vichniac, Cellular-automata supercomputers for fluiddynamics modeling, Phys. Reu . Lett. 156( 16): 1694- 1696 (1986). Cellular Automata for Ecological Modeling 99 48 D. Marr, Vision, Freeman, 1982, 397 pp. 49 0. Martin, A. Odlyzko, and S. Wolfram, Algebraic properties of cellular automata, Comm. Math. Phys. 93:219 (1984). 50 K. Nakamura, Synchronous to asynchronous transformation of polyautomata, J. Comput. System Sci. 23:22-37 (1984). 51 J. Von Neumann, Theory of Selfkproducing Automata (edited and completed by A. W. Burks), Univ. of Illinois Press, 1966, 388 pp. 52 S. Omohundro, Modelling cellular automata with partial differential equations, Phys. D lOD:128-134; reprinted in Cellular Automata (D. Farmer et al., Eds.). 53 Y. Oono and M. Kohmoto, Discrete model of chemical turbulence, Phys. Rev. Lett. 55(27):2927-2930 (1985). 54 N. H. Packard and S. Wolfram, Two-dimensional cellular automata, J. Statist. Phys. 38901-946 (1985). 55 J. K. Park, K. Steightz, and W. P. Thurnston, Soliton-like behaviour in automata, Phys. D 19D:423-432 (1986). 56 Y. Pomeaux, Invariant in celhrlar automata. J. Phys. A 17L415-L418 (1984). 57 T. Poston and I. Stewart, Catastrophe Theory and Its Applications, Pitman, 1978, 491 pp. 58 A. Rosenfeld, Picture Processing by Computer, Academic, 1969. 59 A. Rosenfeld, Parallel image processing using cellular arrays, Computer 16:14-20 (1983). 60 R. Rosenzweig, Magnetic fluids, Sci. Amer. 247(4):136 (1982). 61 J. B. Salem and S. Wolfram, Thermodynamics and Hydrodynamics with Cellular Automata, to appear. 62 A. R. Smith III, Survey of polyautomata theory, in Formal Languages, Au- tomata, Development (A. L. Lindenmayer and G. Rosenberg, Eds.), Univ. of Utrecht, 1975. 63 A. R. Smith III, Plants, fractals and formal languages, Comput. Graphics 18(3):1-10 (1984). 64 R. Thorn, Stabilite Structurelle et Morphogenbe, Benjamin, 1972. 65 T. Toffoli, Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics, Phys. D lOD:117-127 (1984) reprinted in Cellular Automata (D. Farmer et al., Eds.). 66 T. Toffoli, CAM, a high performance cellular automata machine, Phys. D 10D 195-204 (1984), reprinted in Cellular Automata (D. Farmer et al., Eds.). 67 T. Toffoli and N. Margolus, The C.A.M.-7 Multiprocessor: A Cellular Automata Machine, Lab. of Computer Science Report LCS-TM-298, MIT, 1985. 68 G. Y. Vichniac, Simulating physics with cellular automata, Phys. D lOD:96-116 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 69 R. Wainwright, Life is universal, in Proceedings of the Winter Simulation Conference, AMC, Washington, 1974. 70 M. S. Waterman, Some applications of information theory to cellular automata, Phys. D lOD:45-51 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 71 G. Weisbuch, Networks of automata and biological organisation, J. Theoret. Biol. 121:255-267 (1986). 100 P. HOGEWEG 72 W. G. Wilburg, On the prediction of local patterns in cellular automata, Phys. D 19D:397-410 (1986). 73 S. J. Willson, Cellular automata can generate fractals, Discrete Appl. Math. 8:91-99 (1984). 74 S. J. Willson, Growth rates and fractional dimensions in cellular automata, Phys. D lOD:69-74 (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 75 S. S. Wilson, The PIXIE-5000,a systolic array processor, in Cat. no. 85CH22293, IEEE Comput. Sot. Press, 1985, pp. 477-483. 76 T. Winograd, A simple algorithm for selfreplication, AI memo 196, MIT, 1970. 77 S. Wolfram, Cellular automata as models for complexity, Nature 311:419 (1984). 78 S. Wolfram, Universality and complexity in cellular automata, Phys. D lOD:vii-xii (1984); reprinted in Cellular Automata (D. Farmer et al., Eds.). 79 S. Wolfram, Computation theory of cellular automata, Comm. Math. Phys. 96:15-57 (1984). 80 S. Wolfram, Undecidability and intractability in theoretical physics, Phys. Rev. Lett. 54(8):735-738 (1985). 81 E. C. Zeeman, Catastrophe Theory, Selected Papers 1972- 1977, Addison-Wesley, 1977, 673 pp. 82 B. P. Zeigler, Discrete event models for cell space simulation, 1. Theoret. Phys. 21:573-588 (1982). 83 K. Zuse, The computing universe, Internat. J. Theuret. Phys. 21:589-600 (1982). 84 T. Toffoli and N. Margolus, Cellular Automata Machines: New Enoimtwnent for Modelling, MIT Press, 1987. 85 A. P. Dees and P. Hogeweg, Spatial versus temporal pattern in a model vegeta- tion, Bioinformatica , internal report (1987).