Cyclic cellular automaton
The cyclic cellular automaton is a cellular automaton rule developed by David Griffeath and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a modular value exactly one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior.
As with any cellular automaton, the cyclic cellular automaton consists of a regular grid of cells in one or more dimensions. The cells can take on any of n states, ranging from 0 to n − 1. The first generation starts out with random states in each of the cells. In each subsequent generation, if a cell has a neighboring cell whose value is the successor of the cell's value, the cell is "consumed" and takes on the succeeding value. (Note that 0 is the successor of n − 1; see also modular arithmetic.) More general forms of this type of rule also include a threshold parameter, and only allow a cell to be consumed when the number of neighbors with the successor value exceeds this threshold.
The one-dimensional cyclic cellular automaton has been extensively studied by Robert Fisch, a student of Griffeath. Starting from a random configuration with n = 3 or n = 4, this type of rule can produce a pattern which, when presented as a time-space diagram, shows growing triangles of values competing for larger regions of the grid.
The boundaries between these regions can be viewed as moving particles which collide and interact with each other. In the three-state cyclic cellular automaton, the boundary between regions with values i and i + 1 (mod n) can be viewed as a particle that moves either leftwards or rightwards depending on the ordering of the regions; when a leftward-moving particle collides with a rightward-moving one, they annihilate each other, leaving two fewer particles in the system. This type of ballistic annihilation process occurs in several other cellular automata and related systems, including Rule 184, a cellular automaton used to model traffic flow.
In the n = 4 automaton, the same two types of particles and the same annihilation reaction occur. Additionally, a boundary between regions with values i and i + 2 (mod n) can be viewed as a third type of particle, that remains stationary. A collision between a moving and a stationary particle results in a single moving particle moving in the opposite direction.
However, for n ≥ 5, random initial configurations tend to stabilize quickly rather than forming any non-trivial long-range dynamics. Griffeath has nicknamed this dichotomy between the long-range particle dynamics of the n = 3 and n = 4 automata on the one hand, and the static behavior of the n ≥ 5 automata on the other hand, "Bob's dilemma", after Bob Fisch.
Two or more dimensions
In two dimensions, with no threshold and the von Neumann neighborhood or Moore neighborhood, this cellular automaton generates three general types of patterns sequentially, from random initial conditions on sufficiently large grids, regardless of n. At first, the field is purely random. As cells consume their neighbors and get within range to be consumed by higher-ranking cells, the automaton goes to the consuming phase, where there are blocks of color advancing against remaining blocks of randomness. Important in further development are objects called demons, which are cycles of adjacent cells containing one cell of each state, in the cyclic order; these cycles continuously rotate and generate waves that spread out in a spiral pattern centered at the cells of the demon. The third stage, the demon stage, is dominated by these cycles. Almost surely, every cell of the automaton eventually enters a repeating cycle of states, where the period of the repetition is either n or (for automata with n odd and the von Neumann neighborhood) n + 1. The same eventually-period behavior occurs also in higher dimensions. Small structures can also be constructed with any even period between n and 3n/2. Merging these structures, configurations can be built with a global super-polynomial period.
For larger neighborhoods, similar spiraling behavior occurs for low thresholds, but for sufficiently high thresholds the automaton stabilizes in the block of color stage without forming spirals. At intermediate values of the threshold, a complex mix of color blocks and partial spirals, called turbulence, can form. For appropriate choices of the number of states and the size of the neighborhood, the spiral patterns formed by this automaton can be made to resemble those of the Belousov-Zhabotinsky reaction in chemistry, although other cellular automata more accurately model the excitable medium that leads to this reaction.
- ^ Fisch (1990a,1990b,1992).
- ^ Belitsky and Ferrari (2005).
- ^ Bob's Dilemma. Recipe 29 in David Griffeath's Primordial Soup Kitchen.
- ^ Bunimovich and Troubetzkoy (1994); Dewdney (1989); Fisch, Gravner, and Griffeath (1992); Shalizi and Shalizi (2003); Steif (1995).
- ^ Matamala and Moreno (2004)
- ^ Turbulent Equilibrium in a Cyclic Cellular Automaton. Recipe 6 in David Griffeath's Primordial Soup Kitchen.
- Belitzky, Vladimir; Ferrari, Pablo A. (1995). "Ballistic annihilation and deterministic surface growth". Journal of Statistical Physics 80 (3–4): 517–543. doi:10.1007/BF02178546.
- Bunimovich L. A.; Troubetzkoy, S. E. (1994). "Rotators, periodicity, and absence of diffusion in cyclic cellular automata". Journal of Statistical Physics 74 (1–2): 1–10. doi:10.1007/BF02186804.
- Dewdney, A. K. (1989). "Computer Recreations: A cellular universe of debris, droplets, defects, and demons". Scientific American (August): 102–105.
- Fisch, R. (1990a). "The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics". Journal of Theoretical Probability 3 (2): 311–338. doi:10.1007/BF01045164.
- Fisch, R. (1990b). "Cyclic cellular automata and related processes". Physica D 45 (1–3): 19–25. doi:10.1016/0167-2789(90)90170-T. Reprinted in Gutowitz, Howard A. (ed.) (1991). Cellular Automata: Theory and Experiment. MIT Press/North-Holland. pp. 19–25. ISBN 0-262-57086-6.
- Fisch, R. (1992). "Clustering in the one-dimensional three-color cyclic cellular automaton". Annals of Probability 20 (3): 1528–1548. doi:10.1214/aop/1176989705.
- Fisch, R.; Gravner, J.; Griffeath, D. (1991). "Threshold-Range Scaling of Excitable Cellular Automata". Statistics and Computing 1: 23–39. doi:10.1007/BF01890834.
- Matamala, Martín; Moreno, Eduardo (2004). "Dynamic of cyclic automata over Z^2". Theoretical Computer Science 322 (2): 369–381. doi:10.1016/j.tcs.2004.03.018.
- Shalizi, Cosma Rohilla; Shalizi, Kristina Lisa (2003). "Quantifying self-organization in cyclic cellular automata". In Lutz Schimansky-Geier, Derek Abbott, Alexander Neiman and Christian Van den Broeck (eds.). Noise in Complex Systems and Stochastic Dynamics. Bellingham, Washington: SPIE. pp. 108–117. arXiv:nlin/0507067.
- Steif, Jeffrey E. (1995). "Two applications of percolation to cellular automata". Journal of Statistical Physics 78 (5–6): 1325–1335. doi:10.1007/BF02180134.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states … Wikipedia
Asynchronous cellular automaton — Cellular automata, as with other multi agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells … Wikipedia
Movable cellular automaton — method Movable cellular automaton actively changed self neighbors by means switching neighbors state from linked to unlinked and vice versa (modeling of contact interaction) Method type Continuous/Discrete Discrete … Wikipedia
Majority problem (cellular automaton) — The majority problem, or density classification task is the problem of finding one dimensional cellular automaton rules that accurately perform majority voting. Using local transition rules, cells cannot know the total count of all the ones in… … Wikipedia
Belousov-Zhabotinsky reaction — A Belousov Zhabotinsky reaction, or BZ reaction, is one of a class of reactions that serve as a classical example of non equilibrium thermodynamics, resulting in the establishment of a nonlinear chemical oscillator. The only common element in… … Wikipedia
CCA — can refer to:*California Charter Academy *California College of the Arts *California Culinary Academy *Canadian Canoe Association *Canadian Centre for Architecture *Canadian Council on Africa *Canadian Comedy Awards *Canadian Cricket Association… … Wikipedia
Rule 110 — The Rule 110 cellular automaton (often simply Rule 110) is a one dimensional two state cellular automaton with the following rule table:Interesting propertiesAround 2000, Matthew Cook verified a 1985 conjecture by Stephen Wolfram by proving that… … Wikipedia
Rule 184 — is a one dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:* Rule 184 can be used as a simple model for… … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Langton's ant — after 11000 steps. A red pixel shows the ant s location. Langton s ant is a two dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of … Wikipedia