Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems. (English) Zbl 0919.68090
Summary: Our goal in this paper is to present a mathematical overview of one particular CA (Cellular Automaton) topic: the theory of growth and asymptotic shape. We restrict attention systems on \(\mathbb{Z}^2\), the two-dimensional integers, in which each lattice site is either empty (0) or occupied (1), and in which the set \(A_t\) of occupied sites at time \(t\) grows and attains a limiting geometry.
MSC:
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
cellular automatonReferences:
| [1] | Aizenman, M.; Lebowitz, J., Metastability effects in bootstrap percolation, J. Phys. A, 21, 3801-3813 (1988) · Zbl 0656.60106 |
| [2] | E. R. Banks, Universality in cellular automata, in; E. R. Banks, Universality in cellular automata, in |
| [3] | Bennett, C.; Bourzutschky, M., “Life” not critical?, Nature, 350, 468 (1991) |
| [4] | Bak, P.; Chen, K.; Creutz, M., Self-organized criticality in the “Game of Life,”, Nature, 342, 780 (1989) |
| [5] | Berlekamp, E.; Conway, J.; Guy, R., Winning Ways for Your Mathematical Plays (1982), Academic Press: Academic Press New York · Zbl 0485.00025 |
| [6] | Biggins, J., The asymptotic shape of the branching random walk, Adv. in Appl. Probab., 10, 62-84 (1978) · Zbl 0383.60078 |
| [7] | Bohman, T., Discrete Threshold Growth dynamics are omnivorous for box neighborhoods, Trans. Amer. Math. Soc. (1998) · Zbl 0914.60067 |
| [8] | T. Bohman, J. Gravner, Random threshold growth models, 1998; T. Bohman, J. Gravner, Random threshold growth models, 1998 · Zbl 0932.60086 |
| [9] | T. Bohman, J. Gravner, D. Griffeath, Asymptotic shapes for random threshold growth models, 1998; T. Bohman, J. Gravner, D. Griffeath, Asymptotic shapes for random threshold growth models, 1998 |
| [10] | Broadbent, S.; Hammersley, J., Percolation processes. I. Crystals and mazes, Proc. Cambridge Philos. Soc., 53, 629-641 (1957) · Zbl 0091.13901 |
| [11] | Bramson, M.; Neuhauser, C., Survival of one-dimensional cellular automata under random perturbations, Ann. Probab., 22, 244-263 (1994) · Zbl 0793.60107 |
| [12] | Barabasi, A.-L.; Stanley, H., Fractal Concepts in Surface Growth (1995), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0838.58023 |
| [13] | P. Callahan, Patterns, programs, and links for Conway’s game of Life, http://www.cs.jhu.edu/ callahan/lifepage.html; P. Callahan, Patterns, programs, and links for Conway’s game of Life, http://www.cs.jhu.edu/ callahan/lifepage.html |
| [14] | Cox, J. T.; Durrett, R., Some limit theorems for percolation processes with necessary and sufficient conditions, Ann. Probab., 9, 583-603 (1981) · Zbl 0462.60012 |
| [15] | Durand, B., Inversion of 2D cellular automata: Some complexity results, Theoret. Comput. Sci., 134, 387-401 (1994) · Zbl 0938.68737 |
| [16] | Durrett, R., Lecture Notes on Particle Systems and Percolation (1988), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Belmont · Zbl 0659.60129 |
| [17] | Durrett, R.; Griffeath, D., Contact processes in several dimensions, Z. Wahrsch. verw. Gebiete, 59, 535-552 (1982) · Zbl 0483.60089 |
| [18] | Durrett, R.; Griffeath, D., Asymptotic behavior of excitable cellular automata, J. Experiment. Math., 2, 183-208 (1993) · Zbl 0796.60100 |
| [19] | Dobrushin, R.; Kotecky, R.; Shlosman, S., Wulff Construction, A Global Shape from Local Interaction (1992), Am. Math. Soc: Am. Math. Soc Providence · Zbl 0917.60103 |
| [20] | Durrett, R.; Liggett, T., The shape of the limit set in Richardson’s growth model, Ann. Probab., 9, 186-193 (1981) · Zbl 0457.60083 |
| [21] | Durrett, R.; Steif, J., Fixation results for the threshold voter models, Ann. Probab., 21, 232-247 (1993) · Zbl 0769.60092 |
| [22] | Ermentrout, G.; Edelstein-Keshet, L., Cellular automata approaches to biological modeling, J. Theoret. Biol., 160, 97-133 (1993) |
| [23] | Eden, M., Symp. on Information Theory in Biology (1958), Pergamon: Pergamon New York, p. 359 |
| [24] | N. Elkies, The still-Life density problem and its generalizations, 1997; N. Elkies, The still-Life density problem and its generalizations, 1997 · Zbl 0948.91004 |
| [25] | K. Evans, Larger than Life: It’s So Nonlinear, University of Wisconsin, 1996; K. Evans, Larger than Life: It’s So Nonlinear, University of Wisconsin, 1996 |
| [26] | R. Fisch, D. Griffeath, WinCA: A cellular Automaton modeling environment, Windows 3.x/95 software, version 1.0, 1996; R. Fisch, D. Griffeath, WinCA: A cellular Automaton modeling environment, Windows 3.x/95 software, version 1.0, 1996 |
| [27] | Fisch, R.; Gravner, J.; Griffeath, D., Threshold-range scaling of excitable cellular automata, Statist. Comput., 1, 23-39 (1991) |
| [28] | Fisch, R.; Gravner, J.; Griffeath, D., Metastability in the Greenberg-Hastings model, Ann. Appl. Probab., 3, 935-967 (1993) · Zbl 0787.60122 |
| [29] | Frisch, U.; Hasslacher, B.; Pomeau, Y., Lattice-gas automata for the Navier-Stokes equation, Phys. Rev. Lett., 56, 1505-1508 (1986) |
| [30] | Gardner, M., Mathematical games—The fantastic combinations of John Conway’s new solitaire game, Life, Scientific American, 120-123 (October 1970) |
| [31] | Gardner, M., Wheels, Life and Other Amusements (1983), Freeman: Freeman New York · Zbl 0537.00002 |
| [32] | Garzon, M., Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks (1995), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0844.68041 |
| [33] | Greenberg, J.; Hassard, B.; Hastings, S., Pattern formation and periodic structures in systems modeled by reaction-diffusion equations, Bull. Amer. Math. Soc., 84, 1296-1327 (1978) · Zbl 0424.35011 |
| [34] | Gravner, J., The boundary of iterates in Euclidean growth models, Trans. Amer. Math. Soc., 4549-4559 (1996) · Zbl 0869.58030 |
| [35] | J. Gravner, Recurrent ring dynamics in two-dimensional cellular automata, 1996; J. Gravner, Recurrent ring dynamics in two-dimensional cellular automata, 1996 · Zbl 0945.60092 |
| [36] | Gravner, J.; Griffeath, D., Threshold Growth dynamics, Trans. Amer. Math. Soc., 837-870 (1993) · Zbl 0791.58053 |
| [37] | Gravner, J.; Griffeath, D., First-passage times for discrete Threshold Growth dynamics, Ann. Probab., 24, 1752-1778 (1996) · Zbl 0872.60077 |
| [38] | Gravner, J.; Griffeath, D., Multitype Threshold Growth: Convergence to Poisson-Voronoi tessellations, Ann. Appl. Probab., 7, 615-647 (1997) · Zbl 0892.60096 |
| [39] | Gravner, J.; Griffeath, D., Nucleation parameters for discrete threshold growth dynamics, Experiment. Math., 6, 207-220 (1997) · Zbl 0899.60085 |
| [40] | J. Gravner, D. Griffeath, Scaling limits for critical Threshold Growth, 1997; J. Gravner, D. Griffeath, Scaling limits for critical Threshold Growth, 1997 · Zbl 0899.60085 |
| [41] | Greenlaw, R.; Hoover, H.; Ruzzo, W., Limits to Parallel Computation:\(P (1995)\), Oxford Univ. Press: Oxford Univ. Press London · Zbl 0829.68068 |
| [42] | Gaylord, R.; Nishidate, K., Modeling Nature: Cellular Automata Simulations with Mathematics (1996), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0860.68117 |
| [43] | J. Gravner, J. Quastel, Internal DLA and the Stefan problem, 1998; J. Gravner, J. Quastel, Internal DLA and the Stefan problem, 1998 · Zbl 1108.60318 |
| [44] | Griffeath, D., Self-organization of random cellular automata: Four snapshots, (Grimmett, G., Probability and Phase Transitions (1994), Kluwer Academic: Kluwer Academic Dordrecht/Norwell) · Zbl 0827.60083 |
| [45] | D. Griffeath, Primordial Soup Kitchen, http://psoup.math.wisc.edu/kitchen.html; D. Griffeath, Primordial Soup Kitchen, http://psoup.math.wisc.edu/kitchen.html |
| [46] | D. Griffeath, C. Moore, Life without Death is \(P\); D. Griffeath, C. Moore, Life without Death is \(P\) · Zbl 0912.68140 |
| [47] | H. Gutowitz, Frequently asked questions about cellular automata, http://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.html; H. Gutowitz, Frequently asked questions about cellular automata, http://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.html |
| [48] | Hartmanis, J., On the computing paradigm and computational complexity, (Wiederman, J.; Hajek, P., MFCS’95. MFCS’95, Lecture Notes in Computer Science, 969 (1995), Springer-Verlag: Springer-Verlag Berlin/New York), 82-92 · Zbl 1193.68116 |
| [49] | Holland, J., Outline for a logical theory of adaptive systems, and other articles, (Burks, A. W., Essays on Cellular Automata (1970), Univ. of Illinois Press: Univ. of Illinois Press Champaign) |
| [50] | Jen, E., Exact solvability and quasiperiodicity of one-dimensional cellular automata, Nonlinearity, 4, 251-276 (1991) · Zbl 0716.68071 |
| [51] | Johnson, W.; Mehl, R., Reaction kinetics in processes of nucleation and growth, Trans. A.I.M.M.E., 135, 416-458 (1939) |
| [52] | Kari, J., Reversability of 2D cellular automata is undecidable, Physica D, 45, 379-385 (1990) · Zbl 0729.68058 |
| [53] | Kesten, H., First passage percolation and a higher-dimensional generalization, (Durrett, R., Particle Systems, Random Media and Large Deviations (1984), Am. Math. Soc: Am. Math. Soc Providence) · Zbl 0568.60099 |
| [54] | Kesten, H., On the speed of convergence in first-passage percolation, Ann. Appl. Probab., 4, 76-107 (1994) · Zbl 0824.60100 |
| [55] | Kesten, H.; Schonmann, R., On some growth models with a small parameter, Probab. Theory Related Fields, 101, 435-468 (1995) · Zbl 0820.60084 |
| [56] | Krug, J.; Spohn, H., Kinetic roughening of growing surfaces, (Godreche, C., Solids far from Equilibrium (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 479-582 |
| [57] | Langton, C., Studying artificial life with cellular automata, Physica D, 22, 120-149 (1986) |
| [58] | Lawler, G.; Bramson, M.; Griffeath, D., Internal diffusion limited aggregation, Ann. Probab., 14, 2117-2140 (1992) · Zbl 0762.60096 |
| [59] | Lawniczak, A.; Dab, D.; Kapral, R.; Boon, J.-P., Reactive lattice gas automata, Physica D, 47, 132-158 (1991) · Zbl 0717.76133 |
| [60] | Liggett, T., Interacting Particle Systems (1985), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0559.60078 |
| [61] | Lind, D., Applications of ergodic theory and sofic systems to cellular automata, Physica D, 10, 36-44 (1984) · Zbl 0562.68038 |
| [62] | Lindgren, K.; Nordahl, M., Universal computation in simple one-dimensional cellular automata, Complex Systems, 4, 299-318 (1990) · Zbl 0724.68072 |
| [63] | Margolus, N., CAM-8: A Virtual Processor Cellular Automata Machine (1995), MIT Laboratory for Computer Science |
| [64] | Martin, B., A universal cellular automaton in quasi-linear time and its \(Smn\), Theoret. Comput. Sci., 123, 199-237 (1994) · Zbl 0801.68116 |
| [65] | Minsky, M., Computation: Finite and Infinite Machines (1972), Prentice Hall: Prentice Hall New York |
| [66] | Mountford, T., Critical lengths for semi-oriented bootstrap percolation, Stochastic Process. Appl., 95, 185-205 (1995) · Zbl 0821.60092 |
| [67] | M. Niemiec, Life Page, http://home.sprynet.com/interserv/mniemiec/lifepage.htm; M. Niemiec, Life Page, http://home.sprynet.com/interserv/mniemiec/lifepage.htm |
| [68] | Newman, C.; Piza, M., Divergence of shape fluctuations in two dimensions, Ann Probab., 23, 977-1005 (1995) · Zbl 0835.60087 |
| [69] | Nowak, M.; May, R., Evolutionary games and spatial chaos, Nature, 359, 826-829 (1992) |
| [70] | Packard, N., Cellular Automaton Models for Dendritic Crystal Growth (1985), Institute for Advanced Study |
| [71] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading · Zbl 0833.68049 |
| [72] | Packard, N.; Wolfram, S., Two-dimensional cellular automata, J. Statist. Phys., 38, 901-946 (1985) · Zbl 0625.68038 |
| [73] | Richardson, D., Random growth in a tesselation, Proc. Cambridge Philos. Soc., 74, 515-528 (1973) · Zbl 0295.62094 |
| [74] | Sander, L., Fractal growth processes, Nature, 322, 789-793 (1986) |
| [75] | Schonmann, R., On the behavior of some cellular automata related to bootstrap percolation, Ann. Probab., 20, 174-193 (1992) · Zbl 0742.60109 |
| [76] | Taylor, J.; Cahn, J.; Handwerker, C., Geometric models of crystal growth (Overview No. 98-1), Acta Met., 40, 1443-1474 (1992) |
| [77] | Toffoli, T.; Margolus, N., Cellular Automata Machines—A New Environment for Modeling (1987), MIT Press: MIT Press Cambridge · Zbl 0655.68055 |
| [78] | Toom, A., Cellular automata with errors: Problems for students of probability, (Snell, J. L., Topics in Contemporary Probability and Its Applications (1995), CRC Press: CRC Press Boca Raton) · Zbl 0864.60078 |
| [79] | Ulam, S., Random processes and transformations, Proc. (1950) Int. Congr. Math. (1952), p. 264-275 · Zbl 0049.09511 |
| [80] | Vichniac, G., Simulating physics with cellular automata, Physica D, 10, 96-115 (1984) · Zbl 0563.68053 |
| [81] | H. von Koch, 1904; H. von Koch, 1904 |
| [82] | von Neumann, J., (Burks, A., Theory of Self-Reproducing Automata (1966), Univ. of Illinois Press: Univ. of Illinois Press Champaign) |
| [83] | Weiner, N.; Rosenblueth, A., The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle, Arch. Inst. Cardiol. Mexico, 16, 205-265 (1946) · Zbl 0134.37904 |
| [84] | Witten, T.; Sander, L., Diffusion limited aggregation, Phys. Rev. Lett., 47, 1400-1403 (1981) |
| [85] | Willson, S., On convergence of configurations, Discrete Math., 23, 279-300 (1978) · Zbl 0395.52005 |
| [86] | Willson, S., Cellular automata can generate fractals, Discrete Appl. Math., 8, 91-99 (1984) · Zbl 0533.68051 |
| [87] | Wolfram, S., Cellular Automata and Complexity (1994), Addison-Wesley: Addison-Wesley Menlo Park · Zbl 0823.68003 |
| [88] | S. Wolfram, 1995; S. Wolfram, 1995 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
