Koopman spectral analysis of elementary cellular automata.

Area of Science:

• Complex Systems
• Dynamical Systems Theory
• Theoretical Computer Science

Background:

• Elementary Cellular Automata (ECA) are simple models exhibiting complex behavior.
• Koopman operator theory provides a linear framework for analyzing nonlinear dynamical systems.
• Understanding ECA dynamics is crucial for fields ranging from physics to computation.

Purpose of the Study:

• To apply Koopman spectral analysis to elementary cellular automata.
• To establish a connection between Koopman eigenfunctions and conserved quantities in ECA.
• To investigate the relationship between Koopman eigenvalues and Wolfram's classification of ECA.

Main Methods:

• Lifting ECA dynamics to a higher-dimensional space using one-hot encoding.
• Representing the Koopman operator as the transpose of the state-transition network's adjacency matrix.
• Calculating Koopman eigenvalues and eigenfunctions for all ECA rules on a 13-cell lattice.

Main Results:

• Koopman eigenvalues were found to be zero or on the unit circle.
• Eigenvalues directly indicate system properties such as reversibility and the number of connected components.
• The spectral properties of the Koopman operator successfully reflect Wolfram's ECA classification.

Conclusions:

• Koopman spectral analysis offers a powerful tool for characterizing ECA.
• This approach provides a unified framework for understanding ECA dynamics and classification.
• The study demonstrates the utility of Koopman theory in analyzing discrete dynamical systems.