PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatiotemporal Dynamics of Conway's Game of Life in the Entropy--Complexity Plane

Lucas Malacarne Astore, Alejandro C. Frery, Petrônio Cândido de Lima e Silva, Frederico Gadelha Guimarães

arXiv:2610.31708v1nlin.CDcs.ITmath.IT

TL;DR

The paper asks how the spatial information organization of Conway’s Game of Life evolves over time, a question not fully addressed by measures of living-cell density. It maps generations to the entropy–complexity plane using ordinal-pattern analysis and finds that trajectories converge toward a stable region, with saturation and apparent convergence varying across initial densities.

  • Problem

    Living-cell density can be similar across configurations with substantially different spatial organization, motivating analysis of how GoL’s spatial informational organization evolves over time.

    Source: §1 · p. 3

  • Method

    The paper linearizes each GoL generation with a Peano-Hilbert traversal, extracts ordinal patterns, and represents permutation entropy and statistical complexity in the H × C plane.

    Source: §1 · p. 3, §5 · pp. 9–10

  • Results

    Across tested configurations, trajectories converge toward a stable region, with approximately exponential early decay followed by bit-depth-limited saturation whose onset and apparent rate vary with initial density.

    Source: §8 · p. 19

  • Takeaways & Limitations

    The entropy–complexity representation provides a complementary way to investigate the long-term informational structure of GoL beyond population-based entropy analyses.

    Source: §1 · p. 3

    Fitting log-distance regression across the full trajectory may bias estimated convergence rates toward faster convergence when configurations saturate earlier.

    Source: §7.3 · p. 18

Abstract

from arXiv · show

We investigate the dynamics of Conway's Game of Life (GoL) through the lens of Ordinal Pattern analysis. Each GoL generation is transformed into a one-dimensional time series, from which ordinal patterns are extracted to characterize its underlying dynamics. The resulting ordinal distributions are then represented in the Entropy--Statistical Complexity ($H \times C$) plane, enabling a quantitative analysis of the system's evolution. We evaluate different encoding strategies, including patch sizes and linearization methods, and assess their impact on the resulting $H \times C$ trajectories. Finally, we characterize the emergent dynamics in terms of convergence behavior, trajectory patterns, and statistical complexity, showing how the proposed entropy--complexity framework provides insights into the dynamics of cellular automata.

1. Introduction

The paper asks how GoL’s spatial information organization changes over time, using an entropy–complexity representation to complement analyses based on living-cell populations. It motivates this approach because similar cell densities can conceal different spatial arrangements.

1. Introduction

  • Entropy measures uncertainty, but alone it cannot distinguish organizations with similar uncertainty; statistical complexity adds information about structural organization beyond randomness.This motivates considering entropy and complexity jointly for cellular-automaton dynamics.Source: §1 · p. 3
  • Similar living-cell densities can correspond to substantially different spatial arrangements, so population-based measures alone do not describe the organization of a GoL configuration.The paper therefore asks how that spatial organization evolves over time.Source: §1 · p. 3
  • Each generation is linearized with a Peano-Hilbert curve, converted to ordinal patterns, and represented by permutation entropy and statistical complexity in the H × C plane.Following the sequence of generation-level points traces changes in the spatial configuration’s informational organization.Source: §1 · p. 3, Figure 1 · p. 4
  • The study introduces a representation of GoL’s spatiotemporal evolution in the entropy–complexity plane, using Peano-Hilbert traversal and ordinal patterns to complement population-based entropy analyses.The authors describe this as the first such characterization to their knowledge.Source: §1 · p. 3

2. Cellular Automata

The section introduces cellular automata as locally updated lattices that can produce diverse dynamics, then presents GoL and information-theoretic approaches to characterizing its behavior. It motivates measures that describe both disorder and structured organization.

2. Cellular Automata

  • A cellular automaton is a lattice of finite-state cells updated synchronously by a local rule based on neighboring states, and such systems can exhibit stable, periodic, or chaotic behavior.The section also presents Wolfram’s four-class taxonomy, including complex Class IV behavior with localized structures and long-range interactions.Source: §2 · pp. 4–5

2.1. Conway’s Game of Life

  • GoL is a two-dimensional binary cellular automaton whose cells update synchronously according to their eight Moore neighbors, with survival at two or three neighbors and birth at exactly three.The section identifies GoL with Wolfram Class IV and notes its Turing completeness.Source: §2.1 · pp. 5–6

2.2. Complexity and Entropy in Cellular Automata

  • Prior GoL studies use entropy and information measures to characterize population-level disorder, while coarse-grained entropy has also been used to describe spatial organization.Population measures do not capture the full spatial organization of configurations; the section motivates combining uncertainty and structural organization in the H × C plane.Source: §2.2 · pp. 6–7
  • The λ parameter is the fraction of rule-table entries that produce active states; low values generally correspond to ordered behavior, while high values are associated with chaotic dynamics.The section places the “edge of chaos” between these regimes and describes the H × C plane as a complementary way to analyze disorder and statistical complexity.Source: §2.2 · p. 7

3. Peano-Hilbert Curve

The Peano-Hilbert curve maps a multidimensional lattice to a one-dimensional sequence while tending to keep spatially close cells close in the ordering. This makes a generation’s spatial organization suitable for one-dimensional ordinal-pattern analysis.

3. Peano-Hilbert Curve

  • The Peano-Hilbert curve linearizes a multidimensional grid, such as a CA lattice, while preserving locality so spatially close cells tend to remain close in the resulting ordering.The paper applies it to lattices of dimension 2^K × 2^K and represents each generation as a sequence of cell states.Source: §3 · p. 7
  • The resulting sequence can be treated as a time series, allowing ordinal-pattern methods developed for one-dimensional temporal data to analyze the automaton’s spatial organization.The traversal scans the grid while preserving spatial structure.Source: §3 · p. 7

4. Ordinal Patterns

Ordinal patterns encode the relative ordering of successive time-series values, yielding a distribution used to quantify permutation entropy and statistical complexity. These measures place each time series in the H×C plane, where trajectories characterize changes in the information structure of GoL dynamics.

4.1. Definition

  • Ordinal patterns represent the relative ordering of successive observations, and their empirical distribution characterizes a time series independently of its absolute amplitudes.A sliding window yields one of D! possible patterns; their relative frequencies form the distribution P.Source: §4.1 · pp. 7–8

4.2. Permutation Entropy

  • Normalized permutation entropy measures ordinal-pattern diversity, ranging from 0 for a single pattern to 1 for a uniform distribution.Entropy alone does not distinguish distributions with different degrees of structural organization.Source: §4.2 · p. 8, §4.3 · p. 9

4.3. Statistical Complexity

  • Statistical complexity complements entropy by quantifying organization in the ordinal-pattern distribution; single-pattern and uniform distributions both have vanishing complexity.Intermediate entropy and complexity values characterize distributions with both disorder and non-trivial structure.Source: §4.3 · p. 9

4.4. The entropy–complexity plane

  • The H×C plane represents each time series using normalized permutation entropy and statistical complexity, allowing dynamical regimes to be compared by disorder and structural organization.For GoL, the trajectory in this plane characterizes changes in the information structure of its spatiotemporal dynamics.Source: §4.4 · p. 9

5. Proposed Method

The method maps each GoL generation to an H×C point by encoding its lattice as a time series and measuring ordinal-pattern entropy and complexity. It also estimates convergence to a steady state and examines how encoding choices affect estimate stability.

5. Proposed Method

  • Each generation is Hilbert-traversed, grouped into b-bit blocks, and converted to a time series whose ordinal-pattern distribution yields normalized entropy and Jensen-Shannon complexity.Repeating this process across generations produces the trajectory on the H×C plane.Source: §5 · pp. 9–10

5.2. Convergence to the Regime

  • Convergence is estimated by fitting an exponential relaxation model to the Euclidean distance from the trajectory to its estimated steady-state point.The logarithmic transform makes parameter estimation a linear regression; the fitted rate r determines the half-life ln(2)/r.Source: §5.2 · pp. 10–12

5.3. Time Series Length 𝓁

  • Bit-depth jointly determines time-series length and encoded state-space size, so changing it can affect both estimate reliability and the granularity of the spatial representation.Increasing bit-depth reduces the number of observations while increasing the number of possible encoded states.Source: §5.3 · p. 12

5.3.1. Sensitivity Analysis

  • The sensitivity analysis compares converged H×C reference points and their variability across lattice sizes and bit-depths using 30 independent realizations per configuration.The simulations fix initial live-cell density at 50%, embedding dimension at 6, and duration at 10,000 generations; the analysis assesses sensitivity to lattice size and encoding granularity.Source: §5.3.1 · pp. 12–13

6. Experimental Design

The experimental design uses GoL simulations on square lattices with toroidal boundaries, random initial states, and 10,000 generations. It varies embedding dimension and Peano-Hilbert bit-depth.

6. Experimental Design

  • Experiments use random initial configurations on a 1024 × 1024 lattice with toroidal boundaries for 10,000 generations, varying embedding dimensions 5 and 6 and bit-depths 2^3 to 2^5.The simulations use the soup initialization strategy, with the proportion of live cells specified by ρ0.Source: §6 · p. 13

7. Results

The results show that lattice size, bit-depth, initial density, and embedding dimension shape the entropy–complexity estimates and trajectories. At 16-bit resolution, trajectories exhibit an initial decay toward a discretization-limited plateau, while fitted convergence rates vary across configurations.

7.1. Time Series Length Analysis

  • Bit-depth separates the steady-state trajectories: increasing b from 8 to 32 raises H* by roughly 0.30, from about 0.28 to 0.58.At L=128, C* also rises from about 0.24 to 0.40; the reported curves occupy separated bands across the two measures.Source: §7.1 · p. 14, Figure 4 · p. 14
  • At L=1024, H* and C* become stable, so the study adopts that lattice size for subsequent analyses.The sensitivity analysis compared L∈{128,256,512,1024,2048} and bit-depths 8, 16, and 32.Source: §7.1 · p. 14, Figure 4 · p. 14

7.2. Entropy–Complexity Plane

  • For ρ0=80%, trajectories remain in the low-entropy, low-complexity region; for ρ0=10%, increasing bit-depth shifts trajectories toward higher values of both measures.For ρ0=30% and 50%, trajectories follow well-defined curves and reach regions whose locations vary with encoding bit-depth.Source: §7.2 · pp. 14–15, Figure 5 · p. 15, Figure 6 · p. 16

7.3. Convergence to the Steady State

  • For ρ0=10% and embedding dimension 5, H* rises from 0.295 at 8 bits to 0.424 at 16 bits and 0.593 at 32 bits, while C* rises from 0.219 to 0.277 and 0.299.The reported bit-depth trend holds generally across initial fractions and embedding dimensions, with a larger effect on entropy than on complexity.Source: §7.3 · pp. 15–16
  • At 32 bits and embedding dimension 5, ρ0=80% has H*=0.223 and C*=0.174, below the approximately 0.59–0.61 and 0.30 values for ρ0∈{10,30,50}.The authors describe the 80% condition as a qualitatively different, lower-entropy and lower-complexity regime.Source: §7.3 · p. 16
  • At ρ0=50% and 32 bits, increasing embedding dimension from 5 to 6 changes H* from 0.610 to 0.577 and C* from 0.300 to 0.351.The authors interpret this pattern as capturing additional structural regularities.Source: §7.3 · p. 16
  • Logarithmic-distance fits approximate convergence across configurations, but fitting the full trajectory may bias estimated rates toward faster convergence when saturation begins early.Post-saturation points can pull the fit downward; the reported R2 values range from 0.807 to 0.920, with a separately stated maximum of 0.925.Source: §7.3 · pp. 17–18
  • Across four initial densities at D=6 and b=16, log-distance initially decays approximately linearly before saturating; higher densities reach the plateau earlier.The 10% condition continues decaying past generation 7500 and has greater variance in the saturated regime.Source: §7.3 · pp. 17–18, Figure 8 · p. 18

8. Final Considerations

The Peano–Hilbert encoding and ordinal-pattern analysis represent each generation as an entropy–complexity point, revealing distinct trajectories by initial density that converge toward a stable region. The trajectories show approximately exponential early decay followed by a bit-depth-limited plateau.

8. Final Considerations

  • Each generation is encoded through a Peano–Hilbert traversal, converted into ordinal patterns, and represented by Shannon permutation entropy and Jensen–Shannon statistical complexity.The resulting trajectory tracks the CA dynamics in the H×C plane.Source: §8 · p. 18
  • Changing the initial live-cell fraction produces markedly different H×C paths and convergence points.The study uses lattices of 1024×1024 and simulations of up to 10000 generations.Source: §8 · pp. 18–19
  • Across tested configurations, trajectories converge toward a stable H×C region, with approximately exponential early decay followed by a bit-depth-limited plateau.Higher initial densities tend to reach the plateau earlier; lower-density configurations show greater variance in the saturated regime.Source: §8 · p. 19
  • The framework is presented as a robust, scalable way to characterize transient and steady-state CA behavior; future work proposes applying it to the two-dimensional Ising model.The proposed study would examine whether the framework can characterize its order-disorder transition and criticality signatures.Source: §8 · p. 19

A. Thinning the parametric space

A preliminary sweep on a smaller lattice explored simulation durations and initial densities, then evaluated each simulation across embedding dimensions and bit depths. Tail-averaged H×C values were used to estimate steady-state points and reduce the influence of transient fluctuations.

A. Thinning the parametric space

  • The preliminary analysis used a 256×256 lattice to identify informative parameter configurations while reducing the configurations needed for later experiments.The study computed each trajectory’s tail mean, parameterized by υ, as an estimate of its steady-state point.Source: A. Thinning the parametric space · p. 19
  • The sweep combined 12 simulations across three durations and four initial densities, then analyzed each using four embedding dimensions and five bit depths, yielding 240 experiments.Each trajectory’s final portion was averaged to estimate (H*, C*) while reducing transient-fluctuation influence.Source: A. Thinning the parametric space · p. 19
  • The selected υ values were determined for each simulation duration before evaluating the effects of the remaining parameters.The duration-specific selections followed the initial tail-averaging procedure.Source: A. Thinning the parametric space · pp. 19–20

A.1. Estimation of 𝜐

The tail-window parameter υ was varied to test the stability of steady-state and decay estimates. The study adopts υ=2000 for subsequent experiments because it lies within the stable range for both tested initial densities.

A.1. Estimation of υ

  • The longest pre-convergence trajectories occurred at ρ0=30% and ρ0=50%, so these densities were selected for the υ sensitivity analysis.The text distinguishes them from the 10% and 80% initial-density cases.Source: §A.1 · p. 20
  • The sensitivity test varied υ from 1000 to 8000 generations on the 10000-generation trajectory and reestimated the decay rate and half-life.Candidate windows represented 10% to 80% of the trajectory length.Source: §A.1 · p. 20
  • For υ≤2000, both tested densities yielded stable estimates with R²≥0.94; the study adopted υ=2000 for subsequent experiments.At υ=4000, R² fell to 0.906 for ρ0=30%, while ρ0=50% remained at R²=0.944; the stable window therefore depends on configuration.Source: §A.1 · p. 20

A.2. Parametric study

The parametric study compares simulation horizons, initial densities, embedding dimensions, and bit depths to select configurations that preserve informative coverage of the H×C plane. Longer runs can capture later entropy minima, while encoding choices alter the represented complexity and state range.

A.2. Parametric study

  • The adopted tail window was υ=2000, within the stable regime for both tested densities at D=6 and bit depth 8.For υ≤2000, the estimates were stable and nearly identical; estimates deteriorated as the window incorporated transient dynamics.Source: Figure 9 · p. 21
  • Changing ρ0 altered the final-state regions in the H×C plane, so the study retained ρ0∈{10, 30, 50, 80}.The higher-density initial configurations showed particularly distinct behavior.Source: §A.2 · p. 21
  • For D=3 and D=4, increasing bit depth tended to lower estimated complexity; D=5 and D=6 preserved a broader complexity range and were retained.The latter dimensions were described as a more expressive representation of the dynamical states.Source: §A.2 · p. 21
  • Bit depth b=2 concentrated configurations toward the lower-left of the H×C plane, whereas b=8, b=16, and b=32 provided broader coverage and were retained.The b=2 encoding permits only four distinct states; b=2 and b=4 were excluded from subsequent analysis.Source: §A.2 · p. 21
  • The main experiments restricted embedding dimension to D∈{5, 6} and bit depth to b∈{8, 16, 32}, retaining all four initial densities and three durations.This reduced the configuration space while preserving parameter regimes with greater variation and informative plane coverage.Source: §A.2 · p. 21
  • Median minimum-entropy time rose from approximately 2700 generations at T=3000 to 3400 at T=5000 and 3600 at T=10000; the study retained T=10000.The distributions widened with longer horizons, and secondary late-minimum clusters appeared around 4300–4400 generations at T=5000 and 6400–8000 at T=10000.Source: §A.2 · p. 20, Figure 10 · p. 22
Loading 2610.31708v1…