Idea Transcript
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in JAMES E. HANSON IBM T.J. Watson Research Center, Yorktown Heights, USA Article Outline Glossary Definition of the Subject Introduction Synchronization Domains in One Dimension Particles in One Dimension Emergent Phenomena in Two and Higher Dimensions Future Directions Bibliography Glossary Cellular automaton A spatially-extended dynamical system in which spatially-discrete cells take on discrete values, and evolve according to a spatially-localized discrete-time update rule. Emergent phenomenon A phenomenon that arises as a result of a dynamical system’s intrinsic dynamical behavior. Domain A spatio-temporal region of a cellular automation that conforms to a specific pattern. Particle A spatially-localized region of a cellular automaton that exists as a boundary or defect in a domain, and persists for a significant amount of time. Definition of the Subject In a dynamical system, an “emergent” phenomenon is one that arises out of the system’s own dynamical behavior, as opposed to being introduced from outside. Emergent phenomena are ubiquitous in the natural world; as just one example, consider a shallow body of water with a sandy bottom. It often happens that small ridges form in the sand. These ridges emerge spontaneously, have a characteristic size and shape, and move across the bottom in a characteristic way – all due to the interaction of the sand and the water. In cellular automata (CA), the system’s state consists of an N-dimensional array of discrete cells that take on discrete values and the dynamics is given by a discrete time update rule (see below). The “phenomena” that emerge in CA therefore necessarily consist of spatio-temporal patterns and/or statistical regularities in the cell values.
Therefore, the study of emergent phenomena is CA is the study of the spatio-temporal patterns and statistical regularities that arise spontaneously in cellular automata. Introduction The study of emergent phenomena in cellular automata dates back at least to the beginnings of the modern era of CA investigation inaugurated by Stephen Wolfram and collaborators. Indeed, it was a central theme of the landmark paper that introduced the four “Wolfram classes” [15] shown in Fig. 1. Ever since, emergent phenomena have been the driving force behind a great deal of CA research. To be genuinely emergent, a phenomenon must arise out of configurations in which it is not present; and furthermore, to be of any significance, it must do so with nonvanishing likehood, and persist for a measurable amount of time. Thus the proper study of emergent phenomena in CA excludes from consideration a broad subcategory of systems in which the initial condition and update rule are chosen a priori to exhibit some particular structural feature (lattice gases are a representative example). The fact that such systems are CA is an implementation detail; the CA is merely a substrate or means for the simulation of higher-order structures. Note also that the essential issue is not whether the phenomena were intentionally designed into the CA rule; it is whether they arise naturally with any degree of frequency from configurations in which they are not present. Notation and Terminology A cellular automaton (CA) consists of a discrete N-dimensional array of sites or cells and a discrete-time local update rule applied to all cells in parallel. The location of a cell is given by the N integer-valued coordinates fi; j; k; : : :g. Cells take on values in a discrete set or alphabet, conventionally written 0; 1; : : : ; k 1, with k the alphabet size. An assignment of values to cells is called the configuration of those cells. The value 0 is sometimes treated as a special “quiescent” value, particularly in rules that obey the quiescence condition (: : : 0 : : :) D 0. The local update rule determines the value of a cell at time t C 1 as a function of the values at time t of the cells around it. Typical neighborhoods are symmetrical, centered on the cell to be updated, and are parametrized by the radius r, which is the greatest distance from the center cell to any cell in the neighborhood. An assignment of values to the cells in a neighborhood is called a parent neighborhood, denoted by , and the value () to which that par-
325
326
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 1 Examples of Wolframs four qualitative classes. a Class 1: Spatio-temporally uniform configuration of ECA 32. b Class 2: Separated simple or periodic structures of ECA 44. c Class 3: Chaotic space-time pattern of ECA 90. d Class 4: Complex localized structures of Binary radius-2 CA 1771476584. In all cases the initial condition is random. In this and subsequent figures, cells with value 0 are shown as white squares, cells with value 1 are black
ent neighborhood is mapped under the local update rule is its child value. The set of ordered pairs f; ()g is the rule table. The speed of light of a CA is the maximal rate at which information about a cell’s value may travel; in general it is given by the radius r. In two dimensions there are two common alternatives for the neighborhood’s shape: the von Neumann neighborhood includes the center cell and its four neighbors up, down, left, and right; and the Moore neighborhood, which also includes the four cells diagonally adjacent to the center cell. The so-called elementary cellular automata (ECA) are one-dimensional CA with k D 2, r D 1; a cell is denoted i , takes on values in f0; 1g and evolves over time accordi D ( ti1 ; ti ; tiC1 ). A neighborhood ing to the rule tC1 consists of three consecutive cells, so there are 8 distinct parent neighborhoods and 256 different rule tables. It is convenient to refer to an elementary CA by its rule number, which is determined as follows. The different parent neighborhoods are regarded as numbers in base k and are arranged in decreasing numerical order, from left to
right. Immediately beneath each parent neighborhood its child value () is written. The rule number is obtained by regarding the sequence of child symbols as another number, again in base k. This numbering scheme may be used for one-dimensional CA with any k and r, and may be extended to higher-dimensional CA by the adoption of a convention for assigning numerical values to parent neighborhoods. Different formulations of the local update rule are possible for CA in which symmetry or other constraints are present. For example, one important subclass of CA rules are the totalistic rules, in which the child value depends only on the sum of the values in the parent neighborhood, not on their positions. Totalistic rules may also be assigned a rule number, by writing down the different possible sums of cell values in the parent neighborhood in order, writing the child cell beneath each such sum, and interpreting the sequence of child cells as a number. In describing patterns in one-dimensional configurations, it is convenient to adopt a simplified form of regular expression notation, as follows:
Cellular Automata, Emergent Phenomena in
symbols 0, 1, . . . , k 1 denote literal cell values the symbol ˙ denotes a “wild card” that may take on any value in the alphabet the expression x denotes any number of repetitions of the pattern x [: : :] denotes grouping concatenation denotes spatial adjacency. For example, 0 represents any number of consecutive 0s, while [10] 1 is any configuration consisting of some number of repetitions of the pattern 10 followed by a 1: e. g., 101, 10101, 1010101, and so forth. Synchronization Possibly the simplest type of emergent phenomenon in CA is synchronization, which is the growth of spatial regions in which all cells have the same value. A synchronized region remains synchronized over time (except possibly at its borders) and it may either temporally invariant (i. e., the cell values to not change in time) or periodic (the cells all cycle together through the same temporal sequence of values). The temporal periodicity in the latter case is not greater than the alphabet size k. About the trivial case in which the CA rule maps all neighborhoods to the same value (e. g., ECA 0 or ECA 255), there is little to be said. However, other cases exist in which the synchronized regions emerge only gradually. Characteristic examples in one dimension are shown in Fig. 1a and c. It is evident from these examples that any initial condition can be roughly, but usefully, described in terms of four patterns: (a) pattern 0 , which represents the synchronized regions; (b,c) boundary regions 0 ˙ and ˙ 0 ; and (d) ˙ for the interior of the non-synchronized regions. The behavior of the boundary regions determines whether the synchronized regions grow or shrink. For example, in ECA 32 (Fig. 1a), the parent neighborhoods in the boundary region are D f0˙ ˙; ˙ ˙ 0g, all of which have child value 0; this means that the synchronized region grows as fast as is possible. Also not that since the only parent neighborhood that is not mapped to 0 is D 101. the time taken for a given configuration in ECA 32 to reach a globally synchronized state is governed by the length of the longest region of pattern [10] 1. In general, the growth (or shrinkage) of synchronized regions is determined by the aggregate behavior of the neighborhoods that occur its boundaries; if they recede from each other, the region will grow. The boundaries need not move at the speed of light; the left and right boundaries need not move at the same speed; and their motion need not be perfectly uniform over time.
Cellular Automata, Emergent Phenomena in, Figure 2 Synchronization and phase defects: a ECA 55. b ECA 17
Figure 2a shows ECA 55, in which synchronized regions with temporal period p D 2 emerge from random initial conditions. Note, however, that multiple distinct synchronized regions persist indefinitely. This is an example of a temporal phase defect, which is a boundary between spatio-temporal regions that have the same overall pattern, but one of which is ahead of the other in time. In general, phase defects need not be stationary: an example is shown in Fig. 2b. Also note that for CA with k > 2 it is possible for several different synchronized patterns to emerge and coexist. For example, consider a CA with k D 3 in which the pattern 0 is temporally invariant, while 1 and 2 are mapped into each other to form a period-2 cycle. Domains in One Dimension Synchronization is a special case of a more general emergent phenomenon, the domain. A domain is spatial region that conforms to some specific pattern which persists over time. As has been seen in the case of synchronization, the emergence of a domain is governed by the behavior of its boundaries. An important subclass of domain is the regular domain, in which the spatial pattern may be expressed in terms of a regular language (or equivalently, a finite state machine) [11]. As defined in [9], a regular domain has two properties: all spatial sequences of cells in the domain are in a given regular language; and (2) the set of all sequences in that regular language is itself temporally invariant or periodic. Regular domains are a powerful tool for identifying and analyzing emergent phenomena in CA of one dimension. Generalization to two or more dimensions has proven challenging, though [12] made a significant step in that direction. In studying domains in CA, it is useful to pass the space-time data through a domain filter to help visualize them. A domain filter, which may be constructed for any regular domain, maps every cell that is in the domain to a chosen value (0, say) and maps all cells not in the domain to other values in a prescribed way. Multi-domain filters may be constructed in a similar fashion, to map cells
327
328
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 3 Raw and domain-filtered space-time diagrams of ECA 54
Cellular Automata, Emergent Phenomena in, Figure 4 Raw and domain-filtered ECA 18
in any of a set of distinct domains 1 ; 2 ; : : : onto distinct values 1 ; 2 ; : : :. See [3] for details. An illustrative example is ECA 54, shown in Fig. 3. On the left is the unfiltered data; and on the right, the same dat after passing through the domain filter for ECA 54’s primary domain. The domain has temporal period p D 2 and alternates between patterns [0001] and [110] The two patterns line up to form the interlocking white and black “T” shapes visible in the unfiltered data. As the filtered plot clearly shows, the cells not in the domain have patterns of their own; this will be discussed in the next section. For now, it is sufficient to note that, in addition to the temporal phase defects seen in the emergence of temporally periodic synchronized regions, domains with nontrivial spatial structure may also show spatial phase defects, in which the pattern, in effect, skips or slips by a few cells. The spatial regions that make up a domain may themselves contain disorder; such domains are called chaotic. ECA 90 is the archetypical example of this see Fig. 1c.
From a random initial condition, ECA 90 quickly evolves so that entire configuration is in the domain [0˙ ] . ECA 18 see Fig. 4a, attempts to do the same, except that the global synchronization is frustrated by long-lived spatial phase defects. This is clearly visible in the filtered spacetime diagram shown in Fig. 4b. In this case the boundaries of the domain are inherently ambiguous: the pattern [0˙ ] [00] [˙ 0] contains exactly one spatial phase defect, but it may be regarded as lying anywhere in the central [00] region. The filter used maps all cells in regions that contain a spatial phase defect to 1s. A single CA may support the emergence of multiple different domain patterns. In many cases one domain dominates and will eventually take over. But this is not always true. An interesting case in which two domains, both chaotic, compete on roughly equal status, is binary radius-2 rule 2614700074, shown in Fig. 5. The two domains have patterns 0 D [0˙ ] and 1 D [110˙ ] , respectively. In the filtered plot, cells in 0 are shown in white, cells in 1 are gray, and all other cells are black.
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 5 Multiple coexisting chaotic domains
It appears that by about t D 200 0 appears to be winning, but in fact, by about t D 700, the entire configuration was in 1 , where it remained indefinitely. Depending on the initial condition, one or the other domain was always found to eventually take over with 0 winning about 80% of the time. The coexistence of multiple domains, each with its own spatial structure, gives rise to a large number of possible interfaces. in general, the number of distinct interface types is governed by the complexity of the pattern in each domain; for 2614700074 it turns out that there are 8 distinct possibilities. Six of these show qualitatively distinct behavior, and are plotted (in filtered form only) in Fig. 6. Note that of the six interfaces, two show a quickly growing region in which defects continually multiply, three of them appear to remain spatially localized, and one (at bottom left) is ambiguous. Particles in One Dimension An immediate consequence of the emergence of domains is the simultaneous emergence of boundaries between them. These boundaries may be phase defects, as mentioned in Sect. “Synchronization”, but they may also take the form of particles. A particle is a small region of cells that separates two domains, persists for a relatively long period of time and remains spatially localized. Particles may be stationary or may move; they may themselves exhibit a pattern that is temporally invariant, periodic, or even disordered.
Cellular Automata, Emergent Phenomena in, Figure 6 Domain interfaces in the CA of Fig. 5
Solitons An interesting type of particle emerges in the so-called soliton CA, shown in Fig. 7. These CA rules received their name in analogy with the solitons of fluid dynamics, which are solitary traveling waves with the interesting
property that two solitons may collide, interact, and pass safely through each other, ultimately recovering their original form as if no collision had taken place. In soliton CA, something similar occurs.
329
330
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 7 Examples of solitons in the one-dimensional Filtering Rule
In the simplest case, k D 2, the quiescence condition holds with the usual quiescent symbol 0. The solitons or particles embedded in a large lattice of 0s are finite sequences of 1s and 0s that are both temporally periodic (up to a spatial shift) and can collide and pass through each other without being destroyed. A particle consists of a finite sequence of basic strings of length r C 1 (where r is the CA radius). The leftmost cell of a particle is always a nonquiescent cell. A particle is bounded on the right by a sequence of r C 1 quiescent cells. Under the action of the CA rule, a particle may move to the left or right, may grow or shrink, but ultimately will come back to its original configuration after a finite time p – though possibly shifted by some number of cells. The ratio of the shift and temporal period p determines the particle’s velocity V defined in the obvious way: V D (spatial shift)/(temporal period). A particle may even temporarily split into two or more smaller particles, so long as eventually they rejoin to form the original configuration. And, as the name implies, two particles with different velocities may collide and pass through each other without being destroyed. Particles and Defects Defined by Domains Given the wide variety of domains that arise in CA, the resultant variety of particles that they support is apparently limitless. However, two simple examples may suffice to illustrate these phenomena: ECA 18 and ECA 54, both of which were discussed in the previous section. Particles in ECA 18 The spatial phase defects that occur in the domain of ECA 18 (see Fig. 4b) appear, on casual inspection, to be moving more or less at random. It turns out that to a very good approximation, an isolated defect performs a random walk on the lattice [4,7]. When two of them meet, they mutually annihilate. This behavior is purely deterministic, of
Cellular Automata, Emergent Phenomena in, Figure 8 Long-term behavior of ECA 18
course; it is caused entirely by the iterated action of the update rule on the initial condition. In effect, the disorder in the domains is causing disorder in the motion of their boundaries. For small systems, and eventually on all systems, finite-size effects cause departures from statistical randomness; but otherwise, except for a few highly atypical system-sizes, the defects’ behavior is statistically indistinguishable from random motion. Figure 8 shows the long-term behavior of a random initial condition on a relatively large lattice. Particles in ECA 54 ECA 54 represents an interesting case which can serve to illustrate many the emergent phenomena in one dimensional CA [1,10]. The primary domain gives rise to the so-called “fundamental particles” ˛, ˇ and , shown in Fig. 9. The unfiltered space-time diagrams are shown on the left, and their filtered counterparts on the right. The interactions between the fundamental particles are shown in Fig. 10. In the filtered figures, the numbers inscribed in the black squares are the different outputs of the domain filter; each different sequence of numbers represents a different way in which the domain pattern has been violated. The long-term behavior of the particles can be seen in Fig. 11. The ˇs decay relatively quickly, leaving only ˛s and s – except for rare cases where a ˇ is created by the interaction in Fig. 10e and persists for a short while, and rarer cases where some other pattern is momentarily present. (Note that the scale of the figure is so compressed that only the ˛s are visible.) It appears, and is borne out by numerical experiments, that the number of ˛s decays extremely slowly, and that the system settles into a state in which the ˛s are roughly equidistant, but move back and forth slightly in a disordered way. Unlike the case of ECA 18, the domains are not disordered, so the particle motion cannot be caused by disorder in the domain. Instead, it comes from the ˛– interactions.
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 9 Fundamental particles in ECA54
Emergent Phenomena in Two and Higher Dimensions As might be expected, the emergent phenomena in CA of more than one spatial dimension are at once richer and less systematically studied. All of the phenomena that are observed in one dimension have their analogues in higher dimensions: domains and particle abound. In 2 or more dimensions, “particle” is no longer synonymous with “boundary”; one sees particles that are entirely surrounded by a domain, and spatially-extended boundaries that separate domains. Fundamentally new types of emergent phenomena appear as well. Domains, Particles, and Interfaces Many of the coherent structures found to exist in Conway’s famous Game of Life can be observed to arise spontaneously from random initial conditions, so they properly fall into the category of emergent phenomena. In Fig. 12
Cellular Automata, Emergent Phenomena in, Figure 10 Pairwise interactions between fundamental particles in ECA 54
a configuration of 100x100 cells is shown at four successive times t D 0; 50; 900; 1350. From the random initial condition, a background pattern of 0s quickly emerges, against which there exist a rich variety of particles and disordered structures. By t D 1350 the configuration has settled to its final state, in which only a few particles remain, all of which are stationary and have temporal period p D 1 or p D 2. At intermediate times, various moving structures may be identified: see, for example, the “glider” at t D 900, about halfway between the center and the top. In moving
331
332
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 11 Long-term behavior of ECA 54
about, these inevitably collide with each other or with the stationary particles, eventually leading to the final state. Interestingly enough, a minor variation on the rule gives rise to the patterns shown in Fig. 13. Small regions of horizontal or vertical stripes emerge quickly. Boundaries between them settle down. By t D 100, a few nonstriped areas persist, along with a few “dotted lines” that
take the place of a stripe, and in which the “dots” oscillate. The non-striped areas eventually all disappear. The dotted lines persist indefinitely. As these examples suggest, 2-dimensional CA support the emergence of synchronized regions, “domains”, and particles in close analogy to 1-D CA. The striped regions in Fig. 13 are an example of a two-dimensional, temporallyinvariant domain. Fundamentally new features also appear in two and higher dimensions as well. The most obvious of these is the spatially-extended interface or boundary between two adjacent domains. Unlike the one-dimensional case, in which particles and interfaces are more or less the same thing, interfaces in two dimensions are themselves one-dimensional. A characteristic example is seen in the voting rule, a 2-D binary CA with von Neumann neighborhood, in which the child cell is determined by the majority of the the local update rule maps a the child cell is equal to the value held by the majority of cells in the parent neighborhood, or if the vote is a tie, by a 0. Figure 14a shows a snapshot at t D 50 of the voting rule starting from a random initial condition. The system has organized itself into
Cellular Automata, Emergent Phenomena in, Figure 12 Conway’s Game of Life, starting from a random initial condition. a t D 0. b t D 50. c t D 900. d t D 1350
Cellular Automata, Emergent Phenomena in
Cellular Automata, Emergent Phenomena in, Figure 13 Variant on Conway’s Game of Life, starting from the same random initial condition as in Fig. 12. a t D 10. b t D 100
regions of two domain patterns. The pattern has stabilized by this time and does not change thereafter. A stochastic variation on the voting rule uses a random variable to break tie votes, resulting it patterns such as Fig. 14b, c and d. Over time, the long boundaries gradually straighten, and small regions of one domain embedded in the other gradually shrink.
A number of extensive tours of patterns observed in selected 2-d CA may be found online; see, for example, [8,14]. Spiral Waves Another important class of patterns in 2-D CA are expanding wavelike patterns, as shown in Fig. 15. These are typical of the class of rules called cyclic CA [5], and generally evolve to configurations of spirals (as shown). These patterns are not domains in the usual sense, because they have a geometric center. The shape of the spiral is closely related to the shape of the parent neighborhood. Starting from a random initial condition, eventually some number of centers form out from which the spiral waves emanate. Quasiperiodicity The final phenomenon to be mentioned here is an intriguing form of emergent phenomenon fundamentally differ-
Cellular Automata, Emergent Phenomena in, Figure 14 Two variants of voter rule. a Voter rule at t D 50. This configuration is time-invariant. b Voter rule with random tie-breaking at t D 50. c Voter rule with random tie- breaking at t D 250. d Voter rule with random tie-breaking at t D 750
Cellular Automata, Emergent Phenomena in, Figure 15 Spiral waves. a Cyclic CA with k D 16, von Neumann neighborhood. b Cyclic CA with k D 16, Moore neighborhood
333
334
Cellular Automata, Emergent Phenomena in
ent from what has been discussed above: the emergence of quasiperiodic oscillations in coarse statistical properties of the configuration (such as, percentage of 1s). [2,6] The evidence consists of return maps, in which the fraction mt of 1s at time t, is plotted against the fraction m tC1 at time t C 1. A synchronized system would show a return map consisting of a single point: m t D m tC1 . A periodic system would show a sequence of points for the different values of m at the different temporal phases of the sequence, and would have m t D m tCp , where p is the period. The observed return plots, however, showed the characteristic shape of quasiperiodic behavior in nonlinear dynamical systems, which is a sequence of points that eventually map out a roughly continuous, closed curve in the plane. This quasiperiodic behavior was found to occur only in CA of dimension N > 3. Future Directions This short survey has only been able to hint at the vast wealth of emergent phenomena that arise in CA. Much work yet remains to be done, in classifying the different structures, identifying general laws governing their behavior, and determining the the causal mechanisms that lead them to arise. For example, there are as yet no general techniques for determining whether a given domain is stable in a given CA; for characterizing the set of initial conditions that will eventually give rise to it; or for working out the particles that it supports. In CA or two or more dimensions, a large body of descriptive results are available, but these are more frequently anecdotal than systematic. A significant barrier to progress has been the lack of good mathematical techniques for identifying, describing, and classifying domains. One promising development in this area is an information-theoretic filtering technique that can operate on configurations of any dimension [13]. Bibliography Primary Literature 1. Boccara N, Nasser J, Roger M (1991) Particlelike structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules. Phys Rev A 44:866 2. Chate H, Manneville P (1992) Collective behaviors in spatially extended systems with local interactions and synchronous updating. Profress Theor Phys 87:1 3. Crutchfield JP, Hanson JE (1993) Turbulent pattern bases for cellular automata. Physica D 69:279 4. Eloranta K, Nummelin E (1992) The kink of cellular automaton rule 18 performs a random walk. J Stat Phys 69:1131 5. Fisch R, Gravner J, Griffeath D (1991) Threshold-range scaling of excitable cellular automata. Stat Comput 1:23–39
6. Gallas J, Grassberger P, Hermann H, Ueberholz P (1992) Noisy collective behavior in deterministic cellular automata. Physica A 180:19 7. Grassberger P (1984) Chaos and diffusion in deterministic cellular automata. Phys D 10:52 8. Griffeath D (2008) The primordial soup kitchen. http://psoup. math.wisc.edu/kitchen.html 9. Hanson JE, Crutchfield JP (1992) The attractor-basin portrait of a cellular automaton. J Stat Phys 66:1415 10. Hanson JE, Crutchfield JP (1997) Computational mechanics of cellular automata: An example. Physica D 103:169 11. Hopcroft JE, Ullman JD (1979) Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading 12. Lindgren K, Moore C, Nordahl M (1998) Complexity of two-dimensional patterns. J Stat Phys 91:909 13. Shalizi C, Haslinger R, Rouquier J, Klinker K, Moore C (2006) Automatic filters for the detection of coherent structure in spatiotemporal systems. Phys Rev E 73:036104 14. Wojtowicz M (2008) Mirek’s cellebration. http://www.mirekw. com/ca/ 15. Wolfram S (1984) Universality and complexity in cellular automata. Physica D 10:1
Books and Reviews Das R, Crutchfield JP, Mitchell M, Hanson JE (1995) Evolving Globally Synchronized Cellular Automata. In: Eshelman LJ (ed) Proceedings of the Sixth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo Gerhardt M, Schuster H, Tyson J (1990) A cellular automaton model of excitable medai including curvature and dispersion. Science 247:1563 Gutowitz HA (1991) Transients, Cycles, and Complexity in Cellular Automata. Phys Rev A 44:R7881 Henze C, Tyson J (1996) Cellular automaton model of three-dimensional excitable media. J Chem Soc Faraday Trans 92:2883 Hordijk W, Shalizi C, Crutchfield J (2001) Upper bound on the products of particle interactions in cellular automata. Physica D 154:240 Iooss G, Helleman RH, Stora R (ed) (1983) Chaotic Behavior of Deterministic Systems. North-Holland, Amsterdam Ito H (1988) Intriguing Properties of Global Structure in Some Classes of Finite Cellular Automata. Physica 31D:318 Jen E (1986) Global Properties of Cellular Automata. J Stat Phys 43:219 Kaneko K (1986) Attractors, Basin Structures and Information Processing in Cellular Automata. In: Wolfram S (ed) Theory and Applications of Cellular Automata. World Scientific, Singapore, pp 367 Langton C (1990) Computation at the Edge of Chaos: Phase transitions and emergent computation. Physica D 42:12 Lindgren K (1987) Correlations and Random Information in Cellular Automata. Complex Syst 1:529 Lindgren K, Nordahl M (1988) Complexity Measures and Cellular Automata. Complex Syst 2:409 Lindgren K, Nordahl M (1990) Universal Computation in Simple One-Dimensional Cellular Automata. Complex Syst 4:299 Mitchell M (1998) Computation in Cellular Automata: A Selected Review. In: Schuster H, Gramms T (eds) Nonstandard Computation. Wiley, New York
Cellular Automata, Emergent Phenomena in
Packard NH (1984) Complexity in Growing Patterns in Cellular Automata. In: Demongeot J, Goles E, Tchuente M (eds) Dynamical Behavior of Automata: Theory and Applications. Academic Press, New York Packard NH (1985) Lattice Models for Solidification and Aggregation. Proceedings of the First International Symposium on Form, Tsukuba Pivato M (2007) Defect Particle Kinematics in One-Dimensional Cellular Automata. Theor Comput Sci 377:205–228
Weimar J (1997) Cellular automata for reaction-diffusion systems. Parallel Comput 23:1699 Wolfram S (1984) Computation Theory of Cellular Automata. Comm Math Phys 96:15 Wolfram S (1986) Theory and Applications of Cellular Automata. World Scientific Publishers, Singapore Wuensche A, Lesser MJ (1992) The Global Dynamics of Cellular Automata. Santa Fe Institute Studies in the Science of Complexity, Reference vol 1. Addison-Wesley, Redwood City
335