Chaos Nameplat
  • Volume/Page
  • Keyword
  • DOI
  • Citation
  • Advanced
   
 
 
 

You Tube Flickr Twitter UniPHY Group iResearch App Facebook

Chaos / Volume 18 / Issue 4 / REGULAR ARTICLES
FREE

FULL-TEXT OPTIONS:

Chaos 18, 043106 (2008); http://dx.doi.org/10.1063/1.2991106 (15 pages)

The organization of intrinsic computation: Complexity-entropy diagrams and the diversity of natural information processing

David P. Feldman1,2,3, Carl S. McTague2,4, and James P. Crutchfield2,3

1College of the Atlantic, Bar Harbor, Maine 04609, USA
2Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
3Complexity Sciences Center and Physics Department, University of California, Davis, One Shields Ave., Davis, California 95616, USA
4DPMMS, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, England

View MapView Map

(Received 29 June 2008; accepted 30 August 2008; published online 14 October 2008)

Intrinsic computation refers to how dynamical systems store, structure, and transform historical and spatial information. By graphing a measure of structural complexity against a measure of randomness, complexity-entropy diagrams display the different kinds of intrinsic computation across an entire class of systems. Here, we use complexity-entropy diagrams to analyze intrinsic computation in a broad array of deterministic nonlinear and linear stochastic processes, including maps of the interval, cellular automata, and Ising spin systems in one and two dimensions, Markov chains, and probabilistic minimal finite-state machines. Since complexity-entropy diagrams are a function only of observed configurations, they can be used to compare systems without reference to system coordinates or parameters. It has been known for some time that in special cases complexity-entropy diagrams reveal that high degrees of information processing are associated with phase transitions in the underlying process space, the so-called “edge of chaos.” Generally, though, complexity-entropy diagrams differ substantially in character, demonstrating a genuine diversity of distinct kinds of intrinsic computation.

© 2008 American Institute of Physics

Article Outline

  1. INTRODUCTION
    1. Structural complexity
    2. Complexity-entropy diagrams
    3. Surveying complexity-entropy diagrams
  2. ENTROPY AND COMPLEXITY MEASURES
    1. Information-theoretic quantities
    2. Entropy growth and entropy rate
    3. Excess entropy
    4. Intrinsic information processing coordinates
    5. Calculating complexities and entropies
  3. COMPLEXITY-ENTROPY DIAGRAMS
    1. One-dimensional discrete iterated maps
      1. Logistic map
      2. Tent map
    2. Ising spin systems
      1. One-dimensional Ising system
      2. Two-dimensional Ising model
      3. Ising model phase transition
    3. Cellular automata
    4. Markov chain processes
    5. The space of processes: Topological ϵ -machines
  4. DISCUSSION AND CONCLUSION

RELATED DATABASES

Scopus

View This Record in Scopus

Web of Science

View this record in Web of Science

View Web of Science related articles

KEYWORDS and PACS

Keywords

cellular automata, chaos, entropy, Markov processes, nonlinear dynamical systems, phase transformations, probability, random processes, spin systems

PACS

  • 05.45.-a

    Nonlinear dynamics and chaos

  • 02.50.Cw

    Probability theory

  • 02.50.Ga

    Markov processes

  • 05.40.-a

    Fluctuation phenomena, random processes, noise, and Brownian motion

ARTICLE DATA

Digital Object Identifier
http://dx.doi.org/10.1063/1.2991106

PUBLICATION DATA

ISSN

1054-1500 (print)  
1089-7682 (online)

Publisher

$abstract.society.value is a Member of CrossRef American Institute of Physics

  1. J. P. Crutchfield and N. H. Packard, Physica D 7, 201 (1983). [Inspec] [ISI]
  2. R. Shaw, The Dripping Faucet as a Model Chaotic System (Aerial, Santa Cruz, 1984).
  3. S. Wolfram, Physica D 10, 1 (1984). [Inspec] [ISI]
  4. C. H. Bennett, Found. Phys. 16, 585 (1986). [ISI]
  5. B. A. Huberman and T. Hogg, Physica D 22, 376 (1986). [Inspec] [ISI]
  6. P. Grassberger, Int. J. Theor. Phys. 25, 907 (1986).
  7. P. Szépfalusy and G. Györgyi, Phys. Rev. A 33, 2852 (1986). [ISI] [MEDLINE]
  8. K. E. Eriksson and K. Lindgren, Phys. Scr.35, 388 (1987). [Inspec]
  9. M. Koppel, Complex Syst. 1, 1087 (1987).
  10. R. Landauer, Nature (London) 336, 306 (1988). [ISI]
  11. S. Lloyd and H. Pagels, Ann. Phys. 188, 186 (1988).
  12. K. Lindgren and M. G. Norhdal, Complex Syst. 2, 409 (1988). [Inspec]
  13. P. Szepfalusy, Phys. Scr., T T25, 226 (1989).
  14. J. P. Crutchfield and K. Young, Phys. Rev. Lett. 63, 105 (1989). [MEDLINE]
  15. C. H. Bennett, “How to Define Complexity in Physics, and Why,” in Santa Fe Institute Studies in the Sciences of Complexity, edited by W. H. Zurek (Addison-Wesley, Reading, 1990), Vol. VIII, pp. 137–148.
  16. J. P. Crutchfield and K. Young, “Computation at the Onset of Chaos,” in Santa Fe Institute Studies in the Sciences of Complexity, edited by W. H. Zurek (Addison-Wesley, Reading, 1990), Vol. VIII, pp. 223–269.
  17. R. Badii, Phys. Lett. A 160, 372 (1991).
  18. W. Li, Complex Syst. 5, 381 (1991). [Inspec]
  19. J. P. Crutchfield, Physica D 75, 11 (1994). [Inspec] [ISI]
  20. J. E. Bates and H. K. Shepard, Phys. Lett. A 172, 416 (1993).
  21. B. Wackerbauer, A. Witt, H. Atmanspacher, J. Kurths, and A. Schein, Chaos, Solitons Fractals 4, 133 (1994).
  22. W. Ebeling, Physica D 109, 42 (1997). [Inspec] [ISI]
  23. R. Badii and A. Politi, Complexity: Hierarchical Structures and Scaling in Physics (Cambridge University Press, Cambridge, 1997).
  24. D. P. Feldman and J. P. Crutchfield, Phys. Lett. A 238, 244 (1998). [Inspec] [ISI]
  25. D. P. Feldman and J. P. Crutchfield, “Discovering non-critical organization: Statistical mechanical, information theoretic, and computational views of patterns in simple one-dimensional spin systems,” Santa Fe Institute Working Paper No. 98-04-026, http://hornacek.coa.edu/dave/Publications/ DNCO.html.
  26. I. Nemenman and N. Tishby, Physica A 302, 89 (2001). [Inspec]
  27. J. P. Crutchfield and D. P. Feldman, Chaos 15, 25 (2003).
  28. C. R. Shalizi and J. P. Crutchfield, J. Stat. Phys. 104, 817 (2001).
  29. N. H. Packard, J. P. Crutchfield, J. D. Farmer, and R. S. Shaw, Phys. Rev. Lett. 45, 712 (1980).
  30. M. R. Muldoon, R. S. Mackay, D. S. Broomhead, and J. Huke, Physica D 65, 1 (1993). [Inspec] [ISI]
  31. J. P. Crutchfield and B. S. McNamara, Complex Syst. 1, 417 (1987). [Inspec]
  32. D. Auerbach, P. Cvitanović, J.-P. Eckmann, G. Gunaratne, and I. Procaccia, Phys. Rev. Lett. 58, 2387 (1987). [MEDLINE]
  33. A. Fraser, “Chaotic data and model building,” in Information Dynamics, Vol. 256 of NATO ASI Series, edited by H. Atmanspacher and H. Scheingraber (Plenum, New York, 1991), pp. 125–130.
  34. G. Tononi, O. Sporns, and G. M. Edelman, Proc. Natl. Acad. Sci. U.S.A. 91, 5033 (1994). [ISI] [MEDLINE]
  35. T. Wennekers and N. Ay, Neural Comput. 17, 2258 (2005). [MEDLINE]
  36. P. I. Saparin, W. Gowin, J. Kurths, and D. Felsenberg, Phys. Rev. E 58, 6449 (1998). [ISI]
  37. N. Marwan, N. Wessel, U. Meyerfeldt, A. Schirdewan, and J. Kurths, Phys. Rev. E 66, 026702 (2002).
  38. K. Young, U. Chen, J. Kornak, G. B. Matson, and N. Schuff, Phys. Rev. Lett. 94, 098701 (2005). [MEDLINE]
  39. W. Bialek, I. Nemenman, and N. Tishby, Neural Comput. 13, 2409 (2001). [Inspec] [ISI] [MEDLINE]
  40. I. Nemenman, “Information theory and learning: A physical approach,” Ph.D. thesis, Princeton University (2000).
  41. J. P. Crutchfield and D. P. Feldman, Adv. Complex Syst. 4, 251 (2001).
  42. L. Debowski, “Entropic subextensitivity in language and learning,” in Nonextensive Entropy: Interdisciplinary Applications, edited by C. Tsallis and M. Gell-Mann (Oxford University Press, Oxford, 2004), pp. 335–345.
  43. D. P. Feldman and J. P. Crutchfield, Adv. Complex Syst. 7, 329 (2004).
  44. T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, New York, 1991).
  45. J. P. Crutchfield and N. H. Packard, Int. J. Theor. Phys. 21, 433 (1982). [Inspec] [ISI]
  46. M. Gell-Mann and S. Lloyd, Complexity 2, 44 (1996). [Inspec]
  47. H. Atlan, “Natural Complexity and the Self-Creation of Meaning,” in The Science and Praxis of Complexity, edited by S. Aida et al. (United Nations University, Tokyo, 1985), pp. 173–192.
  48. M. Gell-Mann, The Quark and the Jaguar: Adventures in the Simple and the Complex (Freeman, New York, 1994).
  49. G. W. Flake, The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation (MIT, Cambridge, 1999).
  50. J. S. Shiner, M. Davison, and P. T. Landsberg, Phys. Rev. E 59, 1459 (1999). [ISI]
  51. R. Lopez-Ruiz, H. L. Mancini, and X. Calbet, Phys. Lett. A 209, 321 (1995). [Inspec] [ISI]
  52. C. Anteneodo and A. R. Plastino, Phys. Lett. A 223, 348 (1996). [Inspec] [ISI]
  53. X. Calbet and R. Lopez-Ruiz, Phys. Rev. E 63, 066116 (2001). [MEDLINE]
  54. R. López-Ruiz, Int. J. Bifurcation Chaos Appl. Sci. Eng. 11, 2669 (2001). [Inspec] [ISI]
  55. J. P. Crutchfield, D. P. Feldman, and C. R. Shalizi, Phys. Rev. E 62, 2996 (2000). [ISI] [MEDLINE]
  56. P. M. Binder, Phys. Rev. E 62, 2998 (2000). [ISI] [MEDLINE]
  57. K. Young and N. Schuff, Neuroimage 39, 1721 (2008). [MEDLINE]
  58. O. A. Rosso, H. A. Larrondo, M. T. Martin, A. Plastino, and M. A. Fuentes, Phys. Rev. Lett. 99, 154102 (2007). [ISI] [MEDLINE]
  59. M. T. Martin, A. Plastino, and O. A. Rosso, Physica A 369, 439 (2006). [Inspec]
  60. N. H. Packard, “Adaptation toward the edge of chaos,” in Dynamic Patterns in Complex Systems, edited by A. Mandell and M. F. Shlesinger (World Scientific, Singapore, 1988).
  61. S. Kauffman, Origins of Order: Self-Organization and Selection in Evolution (Oxford University Press, New York, 1993).
  62. C. G. Langton, Physica D 42, 12 (1990).
  63. M. M. Waldrop, Complexity: The Emerging Science at the Edge of Order and Chaos (Simon and Schuster, New York, 1992).
  64. T. S. Ray and N. Jan, Phys. Rev. Lett. 72, 4045 (1994). [ISI] [MEDLINE]
  65. P. Melby, J. Kaidel, N. Weber, and A. Hübler, Phys. Rev. Lett. 84, 5991 (2000). [MEDLINE]
  66. M. Bertram, C. Beta, M. Pollmann, A. S. Mikhailov, H. H. Rotermund, and G. Ertl, Phys. Rev. E 67, 036208 (2003). [ISI]
  67. N. Bertschinger and T. Natschläger, Neural Comput. 16, 1413 (2004). [ISI] [MEDLINE]
  68. M. Mitchell and J. P. Crutchfield, Complex Syst. 7, 89 (1993). [Inspec]
  69. K. Rateitschak, J. Freund, and W. Ebeling, “Entropy of sequences generated by nonlinear processes: The logistic map,” in Entropy and Entropy Generation: Fundamentals and Applications, edited by J. S. Shiner (Kluwer, Dordrecht, 1996).
  70. J. Freund, W. Ebeling, and K. Rateitschak, Phys. Rev. E 54, 5561 (1996). [MEDLINE]
  71. T. Schürmann, J. Phys. A 35, 1589 (2002). [ISI]
  72. H. E. Stanley, Rev. Mod. Phys. 71, S358 (1999).
  73. J. M. Yeomans, Statistical Mechanics of Phase Transitions (Clarendon, Oxford, 1992).
  74. J. P. Crutchfield and D. P. Feldman, Phys. Rev. E 55, 1239R (1997).
  75. D. Arnold, Complex Syst. 10, 143 (1996). [Inspec]
  76. K. Lindgren, “Cellular automata and modeling of complex physical systems,” in Springer Proceedings in Physics, edited by P. Manneville, N. Boccara, G. Y. Vichniac, and R. Bidaux (Springer-Verlag, Berlin, 1989), Vol. 46, pp. 27–40.
  77. W. Ebeling, L. Molgedey, J. Kurths, and U. Schwarz, “Entropy, complexity, predictability and data analysis of time series and letter sequences,” in The Science of Disaster: Climate Disruptions, Heart Attacks, and Market Crashes (Springer, Berlin/Heidelberg, 2002).
  78. A. Csordás and P. Szépfalusy, Phys. Rev. A 39, 4767 (1989). [MEDLINE]
  79. Z. Kaufmann, Physica D 54, 75 (1991). [Inspec] [ISI]
  80. P. Grassberger, Phys. Lett. A 128, 369 (1988). [Inspec] [ISI]
  81. P. Grassberger, IEEE Trans. Inf. Theory 35, 669 (1989). [Inspec] [ISI]
  82. H. Herzel, A. O. Schmitt, and W. Ebeling, Chaos, Solitons Fractals 4, 97 (1994). [Inspec] [ISI]
  83. T. Schürmann and P. Grassberger, Chaos 6, 414 (1996)CHAOEH000006000003000414000001. [MEDLINE]
  84. Dudok T. de Wit, Eur. Phys. J. B 11, 513 (1999).
  85. I. Nemenman, “Inference of entropies of discrete random variables with unknown cardinalities,” NSF-ITP-02-52, KITP, UCSB (2002).
  86. H. B. Lin, Elementary Symbolic Dynamics and Chaos in Dissipative Systems (World Scientific, Singapore, 1989).
  87. H. O. Peitgen, H. Jürgens, and D. Saupe, Chaos and Fractals: New Frontiers of Science (Springer-Verlag, Berlin, 1992).
  88. E. Ott, Chaos in Dynamical Systems (Cambridge University Press, Cambridge, 1993).
  89. K. Christensen and N. R. Moloney, Complexity and Criticality (Imperial College Press Advanced Physics Texts) (Imperial College Press, London, 2005).
  90. J. P. Sethna, Statistical Mechanics: Entropy, Order Parameters and Complexity (Oxford Master Series in Physics) (Oxford University Press, New York, 2006).
  91. D. P. Feldman, “Computational mechanics of classical spin systems,” Ph.D. thesis, University of California, Davis (1998).
  92. D. P. Feldman and J. P. Crutchfield, Phys. Rev. E 67, 051103 (2003). [ISI]
  93. V. Spirin, P. L. Krapivsky, and S. Redner, Phys. Rev. E 63, 036118 (2001). [ISI] [MEDLINE]
  94. V. Spirin, P. L. Krapivsky, and S. Redner, Phys. Rev. E 65, 016119 (2001). [ISI]
  95. F. Vazquez, P. L. Krapivsky, and S. Redner, J. Phys. A 36, L61 (2003). [Inspec] [ISI]
  96. E. Erb and N. Ay, J. Stat. Phys. 115, 949 (2004).
  97. S. Wolfram, Rev. Mod. Phys. 55, 601 (1983).
  98. B. Chopard and M. Droz, Cellular Automata Modeling of Physical Systems (Collection Alea-Saclay: Monographs and Texts in Statistical Physics) (Cambridge University Press, Cambridge, 1999).
  99. A. Ilachinski, Cellular Automata (World Scientific, Singapore, 2001).
  100. W. Li, N. H. Packard, and C. G. Langton, Physica D 45, 77 (1990). [Inspec] [ISI]
  101. W. K. Wooters and C. G. Langton, Physica D 45, 95 (1990). [Inspec] [ISI]
  102. C. G. Langton, “Computation at the edge of chaos: Phase-transitions and emergent computation,” Ph.D. thesis, The University of Michigan (1991).
  103. D. P. Feldman and J. P. Crutchfield, “Complexity-entropy surveys of cellular automata,” Physica D (to be submitted).
  104. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, New York, 1995).
  105. C. McTague, C. J. Ellison, and J. P. Crutchfield, “Enumerating process languages,” Phys. Rev. E (to be submitted).
  106. K. Young and J. P. Crutchfield, Chaos, Solitons Fractals 4, 5 (1993). [Inspec] [ISI]

View Scopus articles citing this one (13) Scopus Help

Figures (10) Tables (1)

Figures (click on thumbnails to view enlargements)

FIG.1
Excess entropy E and entropy rate hμ as a function of the parameter r. The top curve is excess entropy. The r values were sampled uniformly as r was varied from 3.4 to 4.0 in increments of 0.0001. The largest L used was L = 30 for systems with low entropy. For each parameter value with positive entropy, 1×107 words of length L were sampled.

FIG.1 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.2
Entropy rate and excess entropy (hμ,E)-pairs for the logistic map. Points from regions of the map in which the bifurcation diagram has one or two (or more) bands are colored differently. There are 3214 parameter values sampled for the one-band region and 3440 values for the two-band region. The r values were sampled uniformly. The one-band region is r ∊ (3.6786,4.0); the two-band region is r ∊ (3.5926,3.6786). The largest L used was L = 30 for systems with low entropy. For each parameter value with positive entropy, 1×107 words of length L were sampled.

FIG.2 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.3
Excess entropy E vs entropy density hμ for the tent map. The L used to estimate P(sL), and so E and hμ, varied depending on the a parameter. The largest L used was L = 120 at low hμ. The plot shows 1200 (hμ,E)-pairs. The parameter was incremented every Δa = 5×10−4 for a ∊ [1,1.2] and then incremented every Δa = 0.001 for a ∊ [1.2,2.0]. For each parameter value with positive entropy, 107 words of length L were sampled.

FIG.3 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.4
Complexity-entropy diagram for the one-dimensional, spin-1/2 antiferromagnetic Ising model with nearest- and next-nearest-neighbor interactions. 105 system parameters were sampled randomly from the following ranges: J1 ∊ [−8,0], J2 ∊ [−8,0], T ∊ [0.05,6.05], and B ∊ [0,3]. For each parameter setting, the excess entropy E and entropy density hμ were calculated analytically.

FIG.4 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.5
Complexity-entropy diagram for the two-dimensional, spin-1/2 antiferromagnetic Ising model with nearest- and next-nearest-neighbor interactions. System parameters were sampled randomly from the following ranges: J1 ∊ [−3,0], J2 ∊ [−3,0], T ∊ [0.05,4.05], and B = 0. For each parameter setting, the excess entropy EI and entropy density hμ were estimated numerically.

FIG.5 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.6
Entropy rate vs temperature, excess entropy vs temperature, and the complexity-entropy diagram for the 2D NN ferromagnetic Ising model. Monte Carlo results for 200 temperatures between 0 and 6. The temperature was sampled more densely near the critical temperature. For further discussion, see text.

FIG.6 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.7
Spatial entropy density hμ and spatial excess entropy E for a random sampling of 103 r = 2, binary 1D CAs.

FIG.7 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.8
Excess-entropy, entropy-rate pairs for 105 randomly selected 4-state Markov chains.

FIG.8 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.9
Complexity-entropy pairs (hμ,E) for all topological binary ϵ-machines with n = 1,…,4 states and for 35 041 of the 35 186 5-state ϵ-machines. The excess entropy is estimated as E(L) = H(L)−Lhμ using the exact value for the entropy rate hμ and a storage-efficient type-class algorithm (Ref. 106) for the block entropy H(L). The estimates were made by increasing L until E(L)−E(L−1)<δ, where δ = 0.0001 for 1, 2, and 3 states; δ = 0.0050 for 4 states; and δ = 0.0100 for 5 states.

FIG.9 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.10
An example topological ϵ-machine for a cyclic process in F5,3. Note that branching occurs only between pairs of successive states in the cyclic chain. The excess entropy for this process is log2 5 ≈ 2.32, and the entropy rate is 3/5.

FIG.10 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

Tables

Table I. The number of topological binary ϵ-machines up to n = 5 causal states (after Ref. 105).

View Table


Close

Google Calendar

ADVERTISEMENT

Your Recent History Recent History Help

Recently Viewed

  1. The organization of intrinsic computation: Complexity-entropy diagrams and the diversity of natural information processing
Go to AIP Home
Copyright © American Institute of Physics
close