Advertisement

Cellular Automata Models of Disorder And Organization

  • Gérard Y. Vichniac
Conference paper
Part of the NATO ASI Series book series (volume 20)

Abstract

Cellular automata are mathematical objects introduced in 1948 by J. von Neumann and S. Ulam to “abstract the logical structure of life” [1], Since then, they have established themselves as unique tools to analyze the emergence of global organization, complexity, and pattern formation from the iteration of local operations between simple elements. They have also been extensively used as models of universal computation, and are being increasingly applied to a variety of concepts from physics and chemistry[2]. They are in fact versatile enough to offer analogies with almost all the themes discussed at this meeting (in particular: self-organization, dissipative systems, spatial vs. thermal fluctuations, neural networks, optimization, ergodicity-breaking, and ultrametricity)

Keywords

Cellular Automaton Ising Model Transition Rule Vote Rule Boolean Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [1]
    A. W. Burks, Essays on Cellular Automata (University of Illinois Press, 1970).zbMATHGoogle Scholar
  2. [2]
    D. Farmer, T. Toffoli, and S. Wolfram (eds), Cellular Automata (North-Holland, 1984).zbMATHGoogle Scholar
  3. [3]
    T. Toffoli, Cellular Automata Mechanics, Tech. Rep. no. 208, Comp. Comm. Sci. Dept., The University of Michigan (1977).Google Scholar
  4. [4]
    G. Y. Vichniac, Physica 10D (1984) 96–115; reprinted in [2].MathSciNetGoogle Scholar
  5. [5]
    B. Hayes, Scientific American, 250:3 (1984), 12–21.CrossRefGoogle Scholar
  6. [6]
    M. Creutz, to appear in Ann. Phys. (N. Y.). Google Scholar
  7. [7]
    R. C. Brower, R. Giles, and G. Vichniac, to appear.Google Scholar
  8. [8]
    G. Enting, J. Phys. C 10 (1977) 1379–1388.CrossRefGoogle Scholar
  9. [9]
    E. Domany and W. Kinzel, Phys. Rev. Lett. 53 (1984) 311–314.CrossRefMathSciNetGoogle Scholar
  10. [10]
    W. Kinzel, Z. Phys. B 58 (1985) 229–244.CrossRefzbMATHMathSciNetGoogle Scholar
  11. [11]
    A. L. Toom, in Locally Interacting Systems and their Applications in Biology, R. L. Dobrushin, V. I. Kryukov, and A. L. Toom (eds), Lecture Notes in Mathematics, no 653 (Spinger-Verlag, 1978); and in Multicomponent Random Systems, R. L. Dobrushin (ed), in Adv. in Probabilities, Vol. 6 (Dekker, 1980), pp. 549–575.Google Scholar
  12. [11a]
    A. L. Toom, in Multicomponent Random Systems, R. L. Dobrushin (ed), in Adv. in Probabilities, Vol. 6 (Dekker, 1980), pp. 549–575.Google Scholar
  13. [11b]
    A. L. Toom, R. L. Dobrushin (ed), in Adv. in Probabilities, Vol. 6 (Dekker, 1980), pp. 549–575.Google Scholar
  14. [12]
    P. Gacs and J. Reif, in Proceedings of the Seventeenth ACM Symposium on the Theory of Computing, Providence, R. I., 1985 (ACM, 1985), pp. 388–395.Google Scholar
  15. [13]
    C. H. Bennett and G. Grinstein, Phys. Rev. Lett. 55 (1985) 657–660.CrossRefGoogle Scholar
  16. [14]
    H. Hartman and G. Y. Vichniac, this volume.Google Scholar
  17. [15]
    S. A. Kauffman, this volume; Physica 10D (1984) 145–156; reprinted in [2].MathSciNetGoogle Scholar
  18. [16]
    N. H. Margolus, Physica 10D (1984) 85–95; reprinted in [2].MathSciNetGoogle Scholar
  19. [17]
    T. Toffoli, Physica 10D (1984) 195–204; reprinted in [2].MathSciNetGoogle Scholar
  20. [18]
    H. M. Goldstine and J. von Neumann, unpublished (1946), reprinted in J. von Neumann’s Complete Works, Vol. 5 (Pergamon, 1961), pp. 1–32.Google Scholar
  21. [18a]
    J. von Neumann’s Complete Works, Vol. 5 (Pergamon, 1961), pp. 1–32.Google Scholar
  22. [19]
    Proceedings of the Conference on Physics of Computation, Part II: Computational models of physics, R. Landauer and T. Toffoli (eds), Int. J. Theor. Phys. 21 (1982) no 6–7.Google Scholar
  23. [20]
    R. P. Feynman, The Character of Physical Law (MIT Press, 1967), pp. 57–58.Google Scholar
  24. [21]
    M. Gardner, Scientific American 223:4 (1970) 120–123.CrossRefGoogle Scholar
  25. [22]
    E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways, vol 2. (Academic Press, 1982) Chap. 25; M. Gardner, Wheels, Life and other Mathematical Amusements (Freeman, 1982); W. Poundstone, The Recursive Universe, (W. Morrow, 1985).zbMATHGoogle Scholar
  26. [22a]
    M. Gardner, Wheels, Life and other Mathematical Amusements (Freeman, 1982)Google Scholar
  27. [22b]
    W. Poundstone, The Recursive Universe, (W. Morrow, 1985).Google Scholar
  28. [23]
    S. Lem, “Non Serviam,” in A Perfect Vacuum: Perfect Reviews of Nonexistent Books (Harcourt Brace Jovanovich, 1978).Google Scholar
  29. [24]
    R. Penrose, “Lessons From the Game of Life,” Review of W. Poundstone’s book[22], The New York Times, March 17, 1985, VII, 34:2.Google Scholar
  30. [24a]
    W. Poundstone’s, The New York Times, March 17, 1985, VII, 34:2.Google Scholar
  31. [25]
    F. Dyson, Disturbing the Universe (Harper and Row, 1979).Google Scholar
  32. [26]
    J. von Neumann, Theory of Self-Reproducing Automata (edited and completed by A. W. Burks), (University of Illinois Press, 1966).Google Scholar
  33. [27]
    E. F. Codd, Cellular Automata (Academic Press, 1968).zbMATHGoogle Scholar
  34. [28]
    C. G. Langton, Physica 10D (1984) 135–144; reprinted in [2].Google Scholar
  35. [29]
    J. S. Langer, in Discover, Jan. 1984, p. 76.Google Scholar
  36. [30]
    E. Goles, this volume; and in Comportement dynamique de réseaux d’automates, Thèse, Grenoble 1985.Google Scholar
  37. [31]
    J. Cahn, in Critical Phenomena in Alloys, Magnets, and Superconductors, R. E. Mills, E. Ascher and R. J. Jaffee (eds) (McGraw-Hill, 1971).Google Scholar
  38. [32]
    B. Halperin and P. C. Hohenberg, Rev. Mod. Phys. 49 (1977) 435–479.CrossRefGoogle Scholar
  39. [33]
    G. Grest and P. Srolovitz, Phys. Rev. B30 (1984) 5150–5155.Google Scholar
  40. [34]
    P. Grassberger, Physica 10D (1984) 52–58; reprinted in [2].MathSciNetGoogle Scholar
  41. [35]
    S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Science 220 (1983) 671–680; S. Kirkpatrick and G. Toulouse, J. Physique, in press.CrossRefzbMATHMathSciNetGoogle Scholar
  42. [36]
    S. Wolfram, Physica 10D (1984) 1–35; reprinted in [2].MathSciNetGoogle Scholar
  43. [37]
    N. H. Packard and S. Wolfram, J. Stat. Phys. 38 (1985) 901–946.CrossRefzbMATHMathSciNetGoogle Scholar
  44. [38]
    G. Y. Vichniac, SIAM J. Alg. Disc. Meth. 5 (1984) 596–602.CrossRefzbMATHMathSciNetGoogle Scholar
  45. [39]
    N. H. Margolus, private communication.Google Scholar
  46. [40]
    F. Fogelman-Soulié, this volume; and Contribution à une théorie du calcul sur réseaux, Thèse, Grenoble (1985).Google Scholar
  47. [41]
    A. E. Gelfand and C.C. Walker, Ensemble Modeling (Marcel Dekker, 1984).zbMATHGoogle Scholar
  48. [42]
    N. H. Packard, in Dynamical Systems and Cellular Automata, J. Demongeot, E. Goles, and M. Tchuente (eds) (Academic Press, 1985), pp. 123–137.Google Scholar
  49. [43]
    H. Atlan, F. Fogelman-Soulié, J. Salomon, and G. Weisbuch, Cybernet. Systems, 12 (1981) 103–121.CrossRefMathSciNetGoogle Scholar
  50. [44]
    T. Toffoli and N. Margolus, in preparation.Google Scholar
  51. [45]
    I. Oppenheim and R. D. Levine, Physica 99A (1979) 383–402.Google Scholar
  52. [46]
    J. E. Mayer and M. G. Mayer, Statistical Mechanics (2nd ed.) (Wiley, 1977).zbMATHGoogle Scholar
  53. [47]
    R. C. Tolman, The Principles of Statistical Mechanics (Oxford University Press, 1938; Dover, 1979).Google Scholar
  54. [48]
    R. Balian, Y. Alhassid, and H. Reinhardt, to appear in Physics Reports. Google Scholar
  55. [49]
    R. G. Brewer and E. L. Hahn, Scientific American 251:6 (1984) 50–57.CrossRefGoogle Scholar
  56. [50]
    K. Huang, Statistical Mechanics (Wiley, 1963).Google Scholar
  57. [51]
    P. C. W. Davies, The Physics of Time Asymmetry (University of California Press, 1977).Google Scholar
  58. [52]
    J. Hardy, O. de Pazzis, and Y. Pomeau, Phys. Rev. A 13 (1976) 1949–1961.CrossRefGoogle Scholar
  59. [53]
    T. Toffoli, Physica 10D (1984) 117–127; reprinted in [2].MathSciNetGoogle Scholar
  60. [54]
    Y. Pomeau, J. Phys. A 17 (1984) L415–L418.CrossRefMathSciNetGoogle Scholar
  61. [55]
    See the papers of Mézard, Solla et al. and Virasoro, this volume; and M. Mézard, G. Parisi, N. Sourlas, G. Toulouse, and M. Virasoro, Phys. Rev. Lett. 52 (1984) 1156–1159.CrossRefGoogle Scholar
  62. [56]
    G. Sorkin, private communication.Google Scholar
  63. [57]
    S. A. Solla, G. B. Sorkin, and S. R. White, this volume.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • Gérard Y. Vichniac
    • 1
  1. 1.Laboratory for Computer ScienceMassachusetts Institute of TechnologyCambridgeUSA

Personalised recommendations