PaperlayerView exact revision on arXiv

Source-linked AI summary

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

David P. Feldman, Carl S. McTague, James P. Crutchfield

arXiv:0806.4789v1nlin.CDnlin.CG

TL;DR

The paper addresses how to compare the intrinsic computation of very different dynamical and stochastic systems when randomness alone does not capture organization. It uses complexity-entropy diagrams built from structural complexity and randomness measures, finding diverse system-specific relationships rather than a universal curve. These diagrams provide a common, parameter-free view of how systems store, organize, and transform information.

  • Problem

    Randomness measures alone do not capture the organization and structural information processing of diverse dynamical systems.

  • Method

    The paper uses complexity-entropy diagrams to compare structural complexity and randomness across maps, cellular automata, Ising models, Markov chains, and topological ϵ-machines.

  • Results

    The surveyed systems exhibit diverse complexity-entropy diagrams, with no universal curve or even qualitative similarity across classes.

  • Takeaways & Limitations

    Complexity-entropy diagrams provide a common, parameter-free view for comparing intrinsic information processing across different system classes.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Randomness measures alone do not capture organization, structure, memory, or correlations in natural systems. The paper therefore uses structural complexity and complexity-entropy diagrams to compare intrinsic computation across systems without relying on system parameters.

  • Randomness measures such as entropy rate, Lyapunov exponents, and fractal dimensions quantify unpredictability but not organization or structure.
  • Structural complexity complements randomness by capturing organization, memory, regularity, symmetry, and pattern.
  • The paper rejects prescribing a universal complexity-versus-entropy shape, because useful complexity measures should directly reflect how correlations are organized.
  • Complexity-entropy diagrams plot structural complexity against randomness and reveal whether complexity is a single-valued function of entropy.
  • The diagrams characterize intrinsic computation from system configurations without requiring equations of motion, Hamiltonians, or parameters.
  • The survey addresses the historical expectation of a universal curve and reports that complexity-entropy relationships vary widely across systems.

C. Surveying Complexity-Entropy Diagrams

The survey compares structure and randomness across diverse deterministic, stochastic, and computational systems using shared information-theoretic descriptions. Its central conclusion is that these systems exhibit many distinct complexity-entropy behaviors rather than one general relationship.

  • The survey covers maps of the interval, cellular automata, one- and two-dimensional Ising models, Markov chains, and minimal finite-state machines.
  • The main result is a large range of complexity-entropy behaviors, with no universal curve, general transition, or qualitative similarity across systems.
  • The analysis represents processes as distributions over bi-infinite one-dimensional sequences with symbols drawn from a finite alphabet.
  • A process’s support is the set of allowed sequences, or equivalently the formal language of finite words occurring in its infinite sequences.
  • Order-R Markov chains are characterized by conditional factorization into length-R words, so current words determine the distribution of future symbols.
  • The information-theoretic setup defines entropy, joint entropy, conditional entropy, and mutual information to quantify uncertainty and dependence.

B. Entropy Growth and Entropy Rate

Entropy growth tracks uncertainty in increasingly long blocks, while the entropy rate captures the irreducible randomness remaining per symbol. The entropy rate is also equivalent to metric entropy and thermodynamic entropy density in the stated settings.

  • Block entropy is the total Shannon entropy of length-L sequences and grows monotonically with block length.
  • For stationary processes, block entropy grows approximately linearly for sufficiently large L, motivating the entropy rate hµ.
  • The finite-length estimate hµ(L) is the average uncertainty of the next symbol given the previous L−1 symbols.
  • As L increases, hµ(L) decreases toward hµ, because conditioning on more variables cannot increase entropy.
  • The limiting entropy rate hµ represents the irreducible randomness that persists after statistics over increasingly long blocks are incorporated.

C. Excess Entropy

Excess entropy measures organization and memory by tracking how entropy-rate estimates converge to their asymptotic value. It quantifies large-scale correlations and the information shared between a process’s past and future.

  • The convergence of hµ(L) to hµ provides information about a process’s organization, structure, and correlations.
  • Excess entropy sums the finite-length entropy overestimates hµ(L) − hµ and measures the information needed to infer the actual per-symbol randomness.
  • Large excess entropy indicates regularities or correlations that emerge only at large scales, making it a measure of global structure.
  • Excess entropy is the mutual information between adjacent semi-infinite blocks, measuring how knowledge of one half reduces uncertainty about the other.
  • For a time series, excess entropy is the amount of information shared between the past and the future.
  • Excess entropy is the y-intercept of the asymptotic linear growth of block entropy and can be interpreted as the cost of amnesia.

D. Intrinsic Information Processing Coordinates

The paper represents intrinsic computation with entropy rate hµ and excess entropy E, using their pairs to distinguish randomness from stored or organized information.

  • The excess entropy E and entropy rate hµ specify the large-L asymptotic form of block entropy.
  • For binary order-R Markov processes, excess entropy has a special upper bound derived from mutual information between adjacent R-blocks.
  • Periodic processes have hµ = 0 and E = log2 p, where E measures the information needed to distinguish p cycle phases.

E. Calculating Complexities and Entropies

The study estimates entropy and complexity from sequence probabilities, primarily through simulation, and uses observed configurations to compare parameterized process classes without requiring their generating equations.

  • Information-theoretic quantities depend on sequence probabilities P(sL), obtained analytically, by simulation, or sometimes in closed form.
  • Simulation estimates word frequencies through finite length L using a dynamically generated parse tree, after an initial topological-entropy estimate sets parse-tree sparseness.
  • The survey’s direct estimates are generally accurate to at least 1%, but finite data prevent taking the L →∞ limit exactly.
  • Simulation can reliably estimate entropy rate and excess entropy from sufficiently large data without knowing equations of motion or hidden states.
  • The survey compares parameterized system classes by representing each system with a pair of numbers measuring randomness and intrinsic computation.
  • Interval maps generate binary symbolic sequences through a generating partition, allowing continuous-state dynamics to be analyzed through observed sequences.

1. Logistic Map

The logistic and tent maps produce distinct complexity-entropy relationships: logistic-map complexity is multivalued at fixed entropy, whereas the tent map follows a richer diagram organized by a simple overall relation.

  • Logistic Map: For the logistic map, excess entropy E and entropy rate hµ vary in a complicated manner as parameter r changes continuously.
  • Logistic Map: During logistic-map period doubling, hµ = 0 and E = log2 p, so each period doubling increases excess entropy by one bit.
  • Logistic Map: The complexity-entropy diagram reveals that E is not a function of hµ: a single entropy-rate value can correspond to multiple excess-entropy values.
  • Logistic Map: The logistic-map diagram is self-similar, nonuniformly clustered, bounded below, and apparently excludes some E values at a given hµ.
  • Logistic Map: At finite hµ, the logistic-map diagram shows no apparent phase transition; unbounded E occurs at hµ = 0 as period doublings accumulate.
  • Tent Map: For the tent map, hµ = log2 a when a ∈[1, 2], while hµ = 0 when a ∈[0, 1], and E is estimated from binary word distributions.
  • Tent Map: At tent-map band-merging points, the symbolic process has hµ = 2^-n and E = n, representing n bits of phase information.
  • Tent Map: The tent-map diagram is richer than E = −log2 hµ, although that expression captures its overall shape; unlike the logistic map, E appears single-valued at each hµ.

B. Ising Spin Systems

The paper applies complexity-entropy diagrams to Ising spin systems, using excess entropy to measure structural organization alongside entropy density as unpredictability. For one-dimensional antiferromagnetic systems, parameters are sampled and these quantities are calculated analytically.

  • Ising models are spatially extended statistical-mechanical systems used to study cooperative phenomena and order-disorder transitions.
  • The analysis considers spin-1/2 Ising models with nearest- and next-nearest-neighbor interactions.The Hamiltonian includes coupling constants J1 and J2 and an external field B.
  • Complexity-entropy diagrams pair entropy density with excess entropy to compare unpredictability and structural organization.Entropy density is measured in bits per spin and permits comparison with systems lacking a well-defined temperature.
  • 105 parameter settings were sampled for the one-dimensional antiferromagnetic model, with E and hµ calculated analytically.The sampled ranges were J1, J2 ∈ [−8, 0], T ∈ [0.05, 6.05], and B ∈ [0, 3].

1. One-Dimensional Ising System

One- and two-dimensional antiferromagnetic Ising systems produce structured complexity-entropy diagrams with periodic ground states, forbidden or bounded regions, and related qualitative organization. The two-dimensional system additionally supports complex spatial structures when nearest- and next-nearest-neighbor couplings are similar.

  • 1. One-Dimensional Ising System: One-dimensional next-nearest-neighbor Ising systems yield 10^5 complexity-entropy pairs from analytically calculated hµ and E values.The calculation uses exact transfer-matrix methods and the model’s order-2 Markovian structure.
  • 1. One-Dimensional Ising System: Periodic configurations with periods 1, 2, 3, and 4 appear as batcape tips at hµ = 0 and correspond to different ground states.For a binary periodic sequence of period p, E = log2 p and hµ = 0.
  • 1. One-Dimensional Ising System: Antiferromagnetic one-dimensional systems leave forbidden regions in the complexity-entropy plane, while low-entropy almost-periodic states persist as randomness increases.
  • 1. One-Dimensional Ising System: The one-dimensional diagram has the upper bound E ≤ 2 − 2hµ for a system with at most four Markov states.
  • 1. One-Dimensional Ising System: The logistic map lacks the Ising diagram’s low-entropy almost-periodic region because parameter changes produce higher-period bifurcations rather than added randomness.
  • 2. Two-Dimensional Ising Model: The two-dimensional model shows a near-linear upper bound E ≤ 5(1 − hµ) and periodic bands corresponding to checkerboard and staircase ground-state patterns.The diagram contains 4,500 numerically estimated complexity-entropy pairs from Monte Carlo-generated configurations.
  • 2. Two-Dimensional Ising Model: When J1 ≈ J2, low-temperature horizontal or vertical strips generate EI values above 3 and indicate complex spatial structure.
  • 2. Two-Dimensional Ising Model: The one- and two-dimensional diagrams are qualitatively similar despite the two-dimensional model having a critical phase transition and the one-dimensional model lacking one.

3. Ising Model Phase Transition

For the two-dimensional ferromagnetic Ising model, excess entropy peaks near the critical temperature, while plotting it against entropy density rounds the peak. Cellular-automaton diagrams instead show no intermediate-entropy peak and nearly obey a linear upper bound.

  • 3. Ising Model Phase Transition: At the finite-lattice critical estimate Tc ≈ 2.42, hµ ≈ 0.57 and E ≈ 0.413, with excess entropy maximized near criticality.The estimated Tc exceeds the infinite-system value Tc ≈ 2.27 because the simulation uses a finite lattice.
  • 3. Ising Model Phase Transition: The complexity-entropy diagram for the temperature sweep is a single curve because entropy is single-valued in temperature.
  • 3. Ising Model Phase Transition: The complexity peak is rounded in the complexity-entropy diagram because entropy density changes rapidly near Tc.The same peak appears sharper when excess entropy is plotted directly against temperature.
  • C. Cellular Automata: The cellular-automaton study samples a space of 2^25 ≈ 4.3 × 10^9 binary radius-2 rules rather than examining every rule.Spatial sequences were measured on a lattice with 5 × 10^4 sites after a transient of 5 × 10^4 iterations.
  • C. Cellular Automata: For sampled binary radius-2 one-dimensional cellular automata, no sharp excess-entropy peak appears at an intermediate hµ.The maximum excess entropy decreases moderately rapidly with increasing hµ.
  • C. Cellular Automata: The cellular-automaton diagrams nearly respect the upper bound E ≤ 4(1 − hµ), while retaining a range of excess entropies for nearly every hµ except hµ = 1.

D. Markov Chain Processes

The Markov-chain comparison shows a sharp linear upper bound in the complexity-entropy diagram, while differing parametrizations can produce substantially different diagram structures.

  • Markov-chain diagrams: 105 randomly selected 4-state Markov chains lie beneath the sharp upper bound E = 2 − 2hµ.These are order-2 Markov chains over a binary alphabet.
  • Model structure: Order-2 binary Markov chains encode dependence on the previous two sites and have 12 independent transition parameters.Their 4 × 4 transition matrix has 16 entries, with row normalization reducing the independent count.
  • Comparison with Ising systems: The 1D next-nearest-neighbor Ising systems form a proper subset of the 4-state Markov chains, yet their complexity-entropy diagrams differ markedly.The Ising family has only three independent parameters and samples process space differently.
  • Parametrization: Different parametrizations of the same model class, sampled uniformly over parameters, yield complexity-entropy diagrams with different structural properties.Thus, diagram geometry depends on how the process space is sampled, not only on the underlying model class.

E. The Space of Processes: Topological ǫ-Machines

Topological ǫ-machines provide a parameter-free way to enumerate process structures and map their entropy rates and excess entropies. Their diagrams contain vertical towers and highly structured, highly entropic processes beyond decreasing linear bounds.

  • Parameter-free process space: Computational mechanics represents each process by an optimal, minimal, unique ǫ-machine, enabling a direct, parameter-free exploration of process space.The paper inverts the usual process-to-representation direction by enumerating ǫ-machines and calculating each pair (hµ, E).
  • Enumeration: Binary topological ǫ-machines are systematically enumerated up to five causal states after identifying machines equivalent under state or symbol relabeling.The enumeration counts isomorphically distinct machines and plots their complexity-entropy pairs.
  • Diagram organization: The topological ǫ-machine diagram contains distinct vertical iso-entropy families, with minimum complexity E = 0 for single-state machines.The plotted set includes machines from one through four states and 35,041 of 35,186 five-state machines.
  • Cyclic processes: For cyclic processes, maximal excess entropy is E = log2 5 ≈ 2.3219, achieved by zero-entropy period-5 processes and related partially random cycles.The family F5,b includes positive-entropy examples with the same maximal excess entropy; for F5,3, hµ = 3/5.
  • Cyclic-process bounds: For Fp,b, excess entropy grows without bound as p increases, while hµ approaches 0 for fixed b and approaches 1 as b approaches p.The family F5,b forms an upper bound for the complexity-entropy diagram.
  • Upper-bound structure: The families Fp,b generate prominent vertical towers and show that topological ǫ-machines include highly entropic, highly structured processes not constrained by decreasing linear upper bounds.This contrasts with earlier process classes bounded by E ≤ R(1 − hµ).
  • Interpretation: Enumerating topological ǫ-machines reveals a rich diversity of intrinsic computation independent of conventional model-class parametrizations.The analysis systematically probes a subset of processes in which structure dominates.

IV. DISCUSSION AND CONCLUSION

Across maps, cellular automata, Ising systems, Markov chains, and ǫ-machines, complexity-entropy diagrams reveal fundamentally different organizations of intrinsic computation. The survey therefore rejects a universal complexity-entropy curve while supporting diagrams as a common comparative and diagnostic tool.

  • Cross-model comparison: Complexity-entropy diagrams compare diverse systems despite their parameters controlling different aspects of allowed configurations and configuration probabilities.The survey spans maps, cellular automata, Ising models, Markov chains, and topological ǫ-machines.
  • Cellular automata and maps: The cellular-automaton diagram lacks the forbidden low-excess-entropy region seen for the logistic map.This contrast indicates different organization of intrinsic computation between the two process classes.
  • Ising systems and maps: For a given entropy rate hµ, excess entropy E can be arbitrarily small, while Ising systems exhibit robust almost-periodic low-entropy configurations near well-defined ground states.The logistic map does not appear to show such almost-periodic low-entropy configurations.
  • Scope of the ǫ-machine comparison: The topological ǫ-machine diagram is parameter free but intentionally biased toward high-complexity, high-entropy processes because all branching probabilities are chosen fairly.This sampling choice limits how the diagram should be interpreted.
  • Practical utility: The diversity of diagrams supports using observed configurations to compare information processing and to identify an appropriate model class for a system.The diagram’s organization can provide clues about which model class fits the observed system.
  • Conclusion: There is no universal complexity-entropy curve, and even qualitative similarities across diagrams are not guaranteed.The diagrams instead capture distinctive structures in the intrinsic information-processing capabilities of process classes.
Loading 0806.4789v1…