- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Reviews of Modern Physics

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Statistical mechanics of cellular automata

Stephen Wolfram

Stephen Wolfram

  • The Institute for Advanced Study, Princeton, New Jersey 08540

PDF

Rev. Mod. Phys. 55, 601 – Published 1 July, 1983

DOI: https://doi.org/10.1103/RevModPhys.55.601

Abstract

Cellular automata are used as simple mathematical models to investigate self-organization in statistical mechanics. A detailed analysis is given of "elementary" cellular automata consisting of a sequence of sites with values 0 or 1 on a line, with each site evolving deterministically in discrete time steps according to definite rules involving the values of its nearest neighbors. With simple initial configurations, the cellular automata either tend to homogeneous states, or generate self-similar patterns with fractal dimensions ≃ 1.59 or ≃ 1.69. With "random" initial configurations, the irreversible character of the cellular automaton evolution leads to several self-organization phenomena. Statistical properties of the structures generated are found to lie in two universality classes, independent of the details of the initial state or the cellular automaton rules. More complicated cellular automata are briefly considered, and connections with dynamical systems theory and the formal theory of computation are discussed.

View figure in article

References (115)

  1. Abelson, H. and A. A. diSessa, 1981, Turtle Geometry: The Computer as a Medium for Exploring Mathematics (MIT Press, Cambridge)
  2. Aggarwal, S., 1973, "Local and global Garden of Eden theorems," University of Michigan technical report No. 147
  3. Aladyev, V., 1974, "Survey of research in the theory of homogeneous structures and their applications," Math. Biosci. 22, 121
  4. Aladyev, V., 1976, "The Behavioural Properties of Homogeneous Structures," Math. Biosci. 29, 99
  5. Alekseev, V. M., and M. V. Yakobson, 1981, "Symbolic dynamics and hyperbolic dynamic systems," Phys. Rep. 75, 287
  6. Amoroso, S. and G. Cooper, 1971, "Tessellation structures of reproduction of arbitrary patterns," J. Comput Syst. Sci. 5, 455
  7. Apostol, T. M., 1976, Introduction to Analytic Number Theory (Springer, Berlin)
  8. ApSimon, H. G., 1970a, "Periodic forests whose largest clearings are of size 3," Philos. Trans. R. Soc. London, Ser. A 266, 113
  9. ApSimon, H. G., 1970b, "Periodic forests whose largest clearings are of size n≥4," Proc. R. Soc. London, Ser. A 319, 399
  10. Arbib, M. A., 1969, Theories of Abstract Automata (Prentice-Hall, Englewood Cliffs)
  11. Atrubin, A. J., 1965, "A one-dimensional real-time iterative multiplier," IEEE Trans. Comput. EC-14, 394
  12. Baer, R. M., and H. M. Martinez, 1974, "Automata and biology," Ann. Rev. Biophys. 3, 255
  13. Banks, E. R., 1971, "Information processing and transmission in cellular automata," MIT Project MAC report No. TR-81
  14. Barricelli, N. A., 1972, "Numerical testing of evolution theories," J. Statist. Comput. Simul. 1, 97
  15. Berlekamp, E. R., 1968, Algebraic Coding Theory (McGraw-Hill, New York)
  16. Berlekamp, E. R., J. H. Conway, and R. K. Guy, 1982, Winning Ways for Your Mathematical Plays (Academic, New York), Vol. 2, Chap. 25
  17. Buckingham, D. J., 1978, "Some facts of life," Byte 3, 54
  18. Burks, A. W., 1970, Essays on Cellular Automata (University of Illinois, Urbana)
  19. Burks, A. W., 1973, "Cellular Automata and Natural Systems," Proceedings of the 5th Congress of the Deutsche Gessellschaft für Kybernetik, Nuremberg
  20. Butler, J. T., and S. C. Ntafos, 1977, "The vector string descriptor as a tool in the analysis of cellular automata systems," Math. Biosci. 35, 55
  21. Codd, E. F., 1968, Cellular Automata (Academic, New York)
  22. Cole, S. N., 1969, "Real-time computation by n- dimensional iterative arrays of finite-state machines," IEEE Trans. Comput. C-18, 349
  23. Conway, J. H., 1970, unpublished
  24. Deutsch, E. S., 1972, "Thinning algorithms on rectangular, hexagonal and triangular arrays," Commun. ACM 15, 827
  25. Farmer, J. D., 1982a, "Dimension, fractal measures, and chaotic dynamics," in Evolution of Order and Chaos in Physics, Chemistry and Biology, edited by H. Haken (Springer, Berlin)
  26. Farmer, J. D., 1982b, "Information dimension and the probabilistic structure of chaos," Z. Naturforsch. 37a, 1304
  27. Fine, N. J., 1947, "Binomial coefficients modulo a prime," Am. Math. Mon. 54, 589
  28. Fischer, P. C., 1965, "Generation of primes by a onedimensional real-time iterative array," J. ACM 12, 388
  29. Flanigan, L. K., 1965, "An experimental study of electrical conduction in the mammalian atrioventricular node," Ph.D. thesis (University of Michigan)
  30. Fredkin, E., 1981, unpublished Fredkin, E.PERQ computer demonstration (Three Rivers Computer Corp.)
  31. Gach, P., G. L. Kurdyumov, and L. A. Levin, 1978, "Onedimensional uniform arrays that wash out finite islands," Probl. Peredachi. Info., 14, 92
  32. Gardner, M., 1971, "Mathematical Games," Sci. Amer. 224, February, 112 ibid.224March, 106 ibid.224April, 114
  33. Gardner, M., 1972, "Mathematical Games," Sci. Amer. 226, January, 104
  34. Geffen, Y., A. Aharony, B. B. Mandelbrot, and S. Kirkpatrick, "Solvable fractal family, and its possible relation to the backbone at percolation," Phys. Rev. Lett. 47, 1771
  35. Gerola, H. and P. Seiden, 1978, "Stochastic star formation and spiral structure of galaxies," Astrophys. J. 223, 129
  36. Glaisher, J. W. L., 1899, "On the residue of a binomial-theorem coefficient with respect to a prime modulus," Q. J. Math. 30, 150
  37. Golomb, S. W., 1967, Shift Register Sequences (Holden-Day, San Francisco)
  38. Grassberger, P., 1982, "A new mechanism for deterministic diffusion," Wuppertal preprint WU B 82-18
  39. Greenberg, J. M., B. D. Hassard, and S. P. Hastings, 1978, "Pattern formation and periodic structures in systems modelled by reaction-diffusion equations," Bull. Am. Math. Soc. 84, 1296
  40. Griffeath, D., 1970, Additive and Cancellative Interacting Particle Systems (Springer, Berlin)
  41. Haken, H., 1975, "Cooperative phenomena in systems far from thermal equilibrium and in nonphysical systems," Rev. Mod. Phys. 47, 67
  42. Haken, H., 1978, Synergetics, 2nd ed. (Springer, Berlin)
  43. Haken, H., 1979, Pattern Formation by Dynamic Systems and Pattern Recognition (Springer, Berlin)
  44. Haken, H., 1981, Chaos and Order in Nature (Springer, Berlin)
  45. Hardouin-Duparc, J., 1974, "Paradis terrestre dans l'automate cellulaire de conway," R.A.I.R.O. 8 R-3, 63
  46. Hardy, G. H. and E. M. Wright, 1979, An Introduction to the Theory of Numbers, 5th ed. (Oxford University Press, Oxford)
  47. Harris, B., 1960, "Probability distributions related to random mappings," Ann. Math. Stat. 31, 1045
  48. Harvey, J. A., E. W. Kolb, and S. Wolfram, 1982, unpublished
  49. Herman, G. T., 1969, "Computing ability of a developmental model for filamentous organisms," J. Theor. Biol. 25, 421
  50. Honsberger, R., 1976, "Three surprises from combinatorics and number theory," in Mathematical Gems II, Dolciani Math. Expositions (Mathematical Association of America, Oberlin), p. 1
  51. Hoogland, A., et al., 1982, "A special-purpose processor for the Monte Carlo simulation of Ising spin systems," Delft preprint
  52. Hopcroft, J. E., and J. D. Ullman, 1979, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, Reading)
  53. Kauffman, S. A., 1969, "Metabolic stability and epigenesis in randomly constructed genetic nets," J. Theor. Biol. 22, 437
  54. Kimball, S. H., et al., 1958, "Odd binomial coefficients," Am. Math. Mon. 65, 368
  55. Kitagawa, T., 1974, "Cell space approaches in biomathematics," Math. Biosci. 19, 27
  56. Knuth, D. E., 1973, Fundamental Algorithms (Addison-Wesley, Reading)
  57. Knuth, D. E., 1981, Seminumerical Algorithms, 2nd ed. (Addison-Wesley, Reading)
  58. Kosaraju, S. R., 1974, "On some open problems in the theory of cellular automata," IEEE Trans. Comput. C-23, 561
  59. Landauer, R., 1979, "The role of fluctuations in multistable systems and in the transition to multistability," Ann. N.Y. Acad. Sci. 316, 433
  60. Langer, J. S., 1980, "Instabilities and pattern formation in crystal growth," Rev. Mod. Phys. 52, 1
  61. Levy, Y. E., 1982, "Some remarks about computer studies of dynamical systems," Phys. Lett. A 88, 1
  62. Lifshitz, E. M., and L. P. Pitaevskii, 1981, Physical Kinetics (Pergamon, New York)
  63. Lindenmayer, A., 1968, "Mathematical models for cellular interactions in development," J. Theoret. Biol. 18, 280
  64. MacWilliams, F. J., and N. J. A. Sloane, Theory of Error-Correcting Codes (North-Holland, Amsterdam)
  65. Mandelbrot, B., 1977, Fractals: Form, Chance and Dimension (Freeman, San Francisco)
  66. Mandelbrot, B., 1982, The Fractal Geometry of Nature (Freeman, San Francisco)
  67. Manna, Z., 1974, Mathematical Theory of Computation (McGraw-Hill, New York)
  68. Manning, F. B., 1977, "An approach to highly integrated, computer-maintained cellular arrays," IEEE Trans. Comput. C-26, 536
  69. Margolus, N., 1982, private communication
  70. Martin, O., A. Odlyzko, and S. Wolfram, 1983, "Algebraic properties of cellular automata," Bell Laboratories report (January, 1983)
  71. McIlroy, M. D., 1974, "The numbers of 1's in binary integers: bounds and extremal properties," SIAM J. Comput. 3, 255
  72. Miller, J. C. P., 1970, "Periodic forests of stunted trees," Philos. Trans. R. Soc. London, Ser. A 266, 63
  73. Miller, J. C. P., 1980, "Periodic forests of stunted trees," Philos. Trans. R. Soc. London Ser. A 293, 48
  74. Minsky, M. L., 1967, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs)
  75. Moore, E. F., 1962, "Machine Models of Self-Reproduction," Proceedings of a Symposium on Applied Mathematics 14, 17, reprinted in Essays on Cellular Automata, edited by A. W. Burks (University of Illinois, Urbana, 1970), p. 187
  76. Nicolis, G. and Prigogine, I., 1977, Self-Organization in Nonequilibrium Systems (Wiley, New York)
  77. Nicolis, G.Prigogine, I.Nicolis, G., G. Dewel, and J. W. Turner, editors, 1981, Order and Fluctuations in Equilibrium and Nonequilibrium Statistical Mechanics, Proceedings of the XVIIth International Solvay Conference on Physics (Wiley, New York)
  78. Nishio, H., 1981, "Real time sorting of binary numbers by 1-dimensional cellular automata," Kyoto University report
  79. Ott, E., 1981, "Strange attractors and chaotic motions of dynamical systems," Rev. Mod. Phys. 53, 655
  80. Pearson, R., J. Richardson, and D. Toussaint, 1981, "A special purpose machine for Monte-Carlo simulation," Santa Barbara preprint NSF-ITP-81-139
  81. Peterson, W. W., and E. J. Weldon, Error-Correcting Codes, 2nd ed. (MIT Press, Cambridge)
  82. Preston, K., M. J. B. Duff, S. Levialdi, Ph. E. Norgren, and J.-I. Toriwaki, 1979, "Basics of Cellular Logic with Some Applications in Medical Image Processing," Proc. IEEE 67, 826
  83. Prigogine, I., 1980, From Being to Becoming (Freeman, San Francisco)
  84. Renyi, A., 1970, Probability Theory (North-Holland, Amsterdam)
  85. Roberts, J. B., 1957, "On Binomial Coefficient Residues," Can. J. Math. 9, 363
  86. Rosen, R., 1981, "Pattern Generation in Networks," Prog. Theor. Biol. 6, 161
  87. Rosenfeld, A., 1979, Picture Languages (Academic, New York)
  88. Rosenfeld, A.Schewe, P. F., editor, 1981, "Galaxies, the Game of Life, and Percolation," in Physics News, Amer. Inst. Phys. Pub. R-302, 61
  89. Schulman, L. S., and P. E. Seiden, 1978, "Statistical mechanics of a dynamical system based on Conway's game of life," J. Stat. Phys. 19, 293
  90. Shannon, C. E., 1951, "Prediction and entropy of printed English," Bell Syst. Tech. J., 30, 50
  91. Sierpinski, W., 1916, "Sur une courbe dont tout point est un point de ramification," Pr. Mat.-Fiz. 27, 77 Oeuvres Choisis, (Państowe Wydawnictwo Naukowe, Warsaw) Vol. II, p. 99
  92. Smith, A. R., 1971, "Simple computation-universal cellular spaces," J. ACM 18, 339
  93. Sternberg, S. R., 1980, "Language and architecture for parallel image processing," in Pattern Recognition in Practice, edited by E. S. Gelesma and L. N. Kanal (North-Holland, Amsterdam), p. 35
  94. Stevens, P. S., 1974, Patterns in Nature (Little, Brown, Boston)
  95. Stolarsky, K. B., 1977, "Power and exponential sums of digital sums related to binomial coefficient parity," SIAM J. Appl. Math. 32, 717
  96. Sutton, C., 1981, "Forests and numbers and thinking backwards," New Sci. 90, 209
  97. Thom, R., 1975, Structural Stability and Morphogenesis (Benjamin, New York)
  98. Thompson, D'A. W., 1961, On Growth and Form, abridged ed. edited by J. T. Bonner (Cambridge University, Cambridge, England)
  99. Toffoli, T., 1977a, "Computation and construction universality of reversible cellular automata," J. Comput. Sys. Sci. 15, 213
  100. Toffoli, T., 1977b, "Cellular automata mechanics," Ph.D. thesis, Logic of Computers Group, University of Michigan
  101. Toffoli, T., 1980, "Reversible computing," MIT report MIT/LCS/TM-151
  102. Toffoli, T., 1983, "Squareland: a hardware cellular automaton simulator," MIT LCS preprint, in preparation
  103. Turing, A. M., 1936, "On computable numbers, with an application to the Entscheidungsproblem," Proc. London Math. Soc. Ser. 2, 42, 230 Proc. London Math. Soc. Ser. 243, 544E, reprinted in The Undecidable, edited by M. David (1965; Hewlett, New York), p. 115
  104. Turing, A. M., 1952, "The chemical basis of morphogenesis," Philos. Trans. R. Soc. London, Ser. B 237, 37
  105. Ulam, S., 1974, "Some ideas and prospects in biomathematics," Ann. Rev. Bio., 255
  106. von Neumann, J., 1963, "The general and logical theory of automata," in J. von Neumann, Collected Works, edited by A. H. Taub, 5, 288
  107. von Neumann, J., 1966, Theory of Self-Reproducing Automata, edited by A. W. Burks (University of Illinois, Urbana)
  108. Wainwright, R. T., 1971-73, Lifeline, 1-11
  109. Wainwright, R. T., 1974, "Life is Universal!," Proceedings of the Winter Simulation Conference, Washington, D.C., ACM, p. 448
  110. Waksman, A., 1969, "A model of replication," J. ACM 16, 178
  111. Willson, S., 1982, "Cellular automata can generate fractals," Iowa State University, Department of Mathematics, preprint
  112. Witten, T. A. and L. M. Sander, 1981, "Diffusion-limited aggregation, a kinetic critical phenomenon," Phys. Rev. Lett. 47, 1400
  113. Wolfram, S., et al., 1981, "SMP Handbook," Caltech
  114. Wolfram, S., 1982a, "Cellular automata as simple selforganizing systems," Caltech preprint CALT-68-938 (submitted to Nature)
  115. Wolfram, S., 1982b, "Geometry of binomial coefficients," to be published in Am. Math. Monthly

Outline

Information

Rev. Mod. Phys. 55, 601– Published 1 July, 1983

    © 1983 American Physical Society

    Sign In to Your Journals Account

    Filter

    Filter

    Article Lookup

    Enter a citation