The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing

Abstract

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 range and different kinds of intrinsic computation across an entire class of system. 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.

arXiv comment18 pages, 12 figures, 2 table; http://users.cse.ucdavis.edu/~cmg/compmech/pubs/oic.htm

References in corpus (15)

• Recurrence Plot Based Measures of Complexity and its Application to Heart Rate Variability Data
• A Statistical Measure of Complexity
• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Entropy estimation of symbol sequences
• Tendency to Maximum Complexity in a Non-Equilibrium Isolated System
• Freezing and Slow Evolution in a Constrained Opinion Dynamics Model
• Fate of Zero-Temperature Ising Ferromagnets
• Freezing in Ising Ferromagnets
• Statistical Complexity of Simple 1D Spin Systems
• Complexity Through Nonextensivity
• Adaptation to the Edge of Chaos in the Self-Adjusting Logistic Map
• Comment on "Simple Measure of Complexity"
• Information theory and learning: a physical approach
• Scaling behaviour of entropy estimates
• When do finite sample effects significantly affect entropy estimates ?

Cited by in corpus (30)

• Causality and the Entropy-Complexity Plane: Robustness and Missing Ordinal Patterns
• Cellular automata as convolutional neural networks
• An analysis of high-frequency cryptocurrencies prices dynamics using permutation-information-theory quantifiers
• A framework for the local information dynamics of distributed computation in complex systems
• Complexity analysis of the turbulent environmental fluid flow time series
• What did Erwin Mean? The Physics of Information from the Materials Genomics of Aperiodic Crystals and Water to Molecular Information Catalysts and Life
• Efficiency characterization of a large neuronal network: a causal information approach
• Quantifiers for randomness of chaotic pseudo random number generators
• The (in)visible hand in the Libor market: an Information Theory approach
• Entropic descriptor of a complex behaviour
• Permutation Complexity via Duality between Values and Orderings
• Analysis of the phase transition in the $2D$ Ising ferromagnet using a Lempel-Ziv string parsing scheme and black-box data-compression utilities
• Characterising information-theoretic storage and transfer in continuous time processes
• Lempel-Ziv complexity analysis of one dimensional cellular automata
• Entropy and hierarchical clustering: characterising the morphology of the urban fabric in different spatial cultures
• Efficiency and credit ratings: a permutation-information-theory analysis
• Is Human Atrial Fibrillation Stochastic or Deterministic?
• Complexity-entropy analysis at different levels of organization in written language
• Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
• Estimating the number of available states for normal and tumor tissues in gene expression space
• Versatile entropic measure of grey level inhomogeneity
• Quantifying Self-Organization with Optimal Wavelets
• Computational capabilities at the edge of chaos for one dimensional system undergoing continuous transitions
• Entropy balance and Information processing in bipartite and non-bipartite composite systems
• Permutation Complexity and Coupling Measures in Hidden Markov Models
• Entropy estimation in bidimensional sequences
• Emergence, Construction, or Unlikely? Navigating the Space of Questions regarding Life's Origins
• Statistical complexity and the road to equilibrium in many-body chaotic quantum systems
• Computation by Convective Logic Gates and Thermal Communication
• Optimality and Complexity in Measured Quantum-State Stochastic Processes