Spacetime Symmetries, Invariant Sets, and Additive Subdynamics of Cellular Automata
Skip to main content
eScholarship
Open Access Publications from the University of California

UC Davis

UC Davis Previously Published Works bannerUC Davis

Spacetime Symmetries, Invariant Sets, and Additive Subdynamics of Cellular Automata

  • Author(s): Rupe, Adam
  • Crutchfield, James P
  • et al.
Abstract

Cellular automata are fully-discrete, spatially-extended dynamical systems that evolve by simultaneously applying a local update function. Despite their simplicity, the induced global dynamic produces a stunning array of richly-structured, complex behaviors. These behaviors present a challenge to traditional closed-form analytic methods. In certain cases, specifically when the local update is additive, powerful techniques may be brought to bear, including characteristic polynomials, the ergodic theorem with Fourier analysis, and endomorphisms of compact Abelian groups. For general dynamics, though, where such analytics generically do not apply, behavior-driven analysis shows great promise in directly monitoring the emergence of structure and complexity in cellular automata. Here we detail a surprising connection between generalized symmetries in the spacetime fields of configuration orbits as revealed by the behavior-driven local causal states, invariant sets of spatial configurations, and additive subdynamics which allow for closed-form analytic methods.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View