Quantifying self-organization in cyclic cellular automata

by | Jul 29, 2005 | Research Publications

Author(s):

  • Shalizi, Cosma R.
  • Shalizi, Kristina Lisa

Abstract:

Cyclic cellular automata (CCA) are models of excitable media. Started from random initial conditions, they produce several different kinds of spatial structure, depending on their control parameters. We introduce new tools from information theory that let us calculate the dynamical information content of spatial random processes. This complexity measure allows us to quantitatively determine the rate of self-organization of these cellular automata, and establish the relationship between parameter values and self-organization in CCA. The method is very general and can easily be applied to other cellular automata or even digitized experimental data.

Document:

https://arxiv.org/abs/nlin/0507067

References:
  1. W. R. Ashby, “Principles of the self-organizing dynamic system,”Journal of General Psychology37, pp. 125–128, 1947.
  2. G. Nicolis and I. Prigogine,Self-Organization in Nonequilibrium Systems: From Dissipative Structures toOrder through Fluctuations, John Wiley, New York, 1977.
  3. R. M. D’Souza and N. H. Margolus, “Thermodynamically reversible generalization of diffusion limitedaggregation,”Physical Review E60, pp. 264–274, 1999. URLhttp://arxiv.org/abs/cond-mat/9810258.
  4. R. Fisch, J. Gravner, and D. Griffeath, “Cyclic cellular automata intwo dimensions,” inSpatial StochasticProcesses: A Festschrift in Honor of Ted Harris on His Seventieth Birthday, K. Alexander and J. Watkins,eds., pp. 171–188, Birkh ̈auser, Boston, 1991. URLhttp://psoup.math.wisc.edu/papers/cca.zip.
  5. R. Fisch, J. Gravner, and D. Griffeath, “Threshold-range scaling of excitable cellular automata,”Statisticsand Computing1, pp. 23–39, 1991. URLhttp://psoup.math.wisc.edu/papers/tr.zip.
  6. A. T. Winfree,When Time Breaks Down: The Three-Dimensional Dynamics of Electrochemical Waves andCardiac Arrhythmias, Princeton University Press, Princeton, 1987.
  7. C. Gershenson and F. Heylighen, “When can we call a system self-organizing?” E-print, 2003. URLhttp://arxiv.org/abs/nlin.AO/0303020.
  8. C. R. Shalizi,Causal Architecture, Complexity and Self-Organization inTime Series and Cellular Automata.PhD thesis, University of Wisconsin-Madison, 2001. URLhttp://bactra.org/thesis/.
  9. C. H. Bennett, “Dissipation, information, computational complexity and the definition of organization,” inEmerging Syntheses in Science, D. Pines, ed., pp. 215–234, Santa Fe Institute, Santa Fe, New Mexico, 1985.
  10. C. H. Bennett, “On the nature and origin of complexity in discrete, homogeneous locally-interacting sys-tems,”Foundations of Physics16, pp. 585–592, 1986.
  11. C. H. Bennett, “How to define complexity in physics, and why,” inComplexity, Entropy, and the Physicsof Information, W. H. Zurek, ed., pp. 137–148, Addison-Wesley, Reading, Massachusetts, 1990.
  12. S. Wolfram, “Statistical mechanics of cellular automata,”Reviews of Modern Physics55, pp. 601–644, 1983.Reprinted in [35].
  13. Y. L. Klimontovich,Turbulent Motion and the Structure of Chaos: A New Approach to the Statistical Theoryof Open Systems, Kluwer Academic, Dordrecht, 1990/1991. Translated by Alexander Dobroslavsky fromTurbulentnoe dvizhenie i struktura khaosa: Novyi podkhod kstatisticheskoi teorii otkrytykh sistem(Moscow:Nauka).
  14. P. B. Medawar,Pluto’s Republic, pp. 209–227, Oxford University Press, Oxford, 1982.
  15. R. F. Fox,Energy and the Evolution of Life, W. H. Freeman, New York, 1988.
  16. R. Badii and A. Politi,Complexity: Hierarchical Structures and Scaling in Physics, Cambridge UniversityPress, Cambridge, 1997.
  17. D. P. Feldman and J. P. Crutchfield, “Measures of statistical complexity: Why?,”Physics Letters A238,pp. 244–252, 1998.
  18. G. L. Sewell,Quantum Mechanics and Its Emergent Macrophysics, Princeton University Press, Princeton,New Jersey, 2002.
  19. A. N. Kolmogorov, “Three approaches to the quantitative definition of information,”Problems of Informa-tion Transmission1, pp. 1–7, 1965.
  20. R. J. Solomonoff, “A formal theory of inductive inference,”Information and Control7, pp. 1–22 and 224–254, 1964. URLhttp://world.std.com/∼rjs/pubs.html.
  21. M. Li and P. M. B. Vitanyi,An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, 1993.
  22. J. Rissanen,Stochastic Complexity in Statistical Inquiry, World Scientific, Singapore, 1989.
  23. P. Grassberger, “Toward a quantitative theory of self-generated complexity,”International Journal of The-oretical Physics25, pp. 907–938, 1986.
  24. J. P. Crutchfield and K. Young, “Inferring statistical complexity,”Physical Review Letters63, pp. 105–108,1989.
  25. C. R. Shalizi and J. P. Crutchfield, “Computational mechanics:Pattern and prediction,structure and simplicity,”Journal of Statistical Physics104, pp. 817–879, 2001.URLhttp://arxiv.org/abs/cond-mat/9907176.
  26. C. R. Shalizi and C. Moore, “What is a macrostate? from subjective measurements to objective dynamics.”E-print, 2003. URLhttp://arxiv.org/abs/cond-mat/0303625.
  27. S. Kullback,Information Theory and Statistics, Dover Books, New York, 2nd ed., 1968. First edition NewYork: Wiley, 1959.
  28. P. W. Holland, “Statistics and causal inference,”Journal of the American Statistical Association81, pp. 945–970, 1986.
  29. S. M. Zoldi and H. S. Greenside, “Karhunen-Loeve decomposition of extensive chaos,”Physical ReviewLetters78, pp. 1687–1690, 1997. URLhttp://arxiv.org/abs/chao-dyn/961007.
  30. S. M. Zoldi, J. Liu, K. M. S. Bajaj, H. S. Greenside, and G. Ahlers, “Extensive scaling and nonuniformity ofthe Karhunen-Loeve decomposition for the spiral-defect chaos state,”Physical Review E58, pp. 6903–6906,1998. URLhttp://arxiv.org/abs/chao-dyn/9808006.
  31. K. Lindgren, C. Moore, and M. Nordahl, “Complexity of two-dimensional patterns,”Journal of StatisticalPhysics91, pp. 909–951, 1998. URLhttp://arxiv.org/abs/cond-mat/9804071.
  32. D. H. Rothman and S. Zaleski,Lattice-Gas Cellular Automata: Simple Models of Complex Hydrodynamics,Cambridge University Press, Cambridge, England, 1997.
  33. T. M. Liggett,Interacting Particle Systems, Springer-Verlag, Berlin, 1985.
  34. M. E. J. Newman, “The structure and function of complex networks,”SIAM Review45, pp. 167–256, 2003.URLhttp://arxiv.org/abs/cond-mat/0303516.
  35. S. Wolfram,Cellular Automata and Complexity: Collected Papers, Addison-Wesley, Reading, Massachusetts,1994. URLhttp://www.stephenwolfram.com/publications/books/ca-reprint/.