Volume 34, Issue 3 (2025)

Fast Simulation of Cellular Automata by Self-Composition

Joseph Natal
Institute for Beam Physics and Technology
Karlsruhe Institute of Technology
Hermann-Von-Helmholtz-Platz 1
Eggenstein-Leopoldshafen, Baden-Wuerttemberg 76344, Germany
Oleksiy Al-saadi
Department of Computer Science, Sonoma State University
1801 East Cotati Avenue
Rohnert Park, CA 94928, United States

Abstract

Computing the configuration of any one-dimensional cellular automaton at generation n can be accelerated by constructing and running a composite rule with a radius proportional to log n. The new automaton is the original one, but with its local rule function composed with itself. Consequently, the asymptotic time complexity to compute the configuration of generation n is reduced from $O\left(n^2\right)$-time to $O\left(n^2/\log n\right)$ but with $O\left(n^2/{\left(\log n\right)}^3\right)$-space, demonstrating a time-memory tradeoff. Experimental results are given in the case of rule 30.

Keywords: cellular automata; time complexity; rule 30; nonlinear systems

Cite this publication as: J. Natal and O. Al-saadi, “Fast Simulation of Cellular Automata by Self-Composition,” Complex Systems, 34(3), 2025 pp. 259–271.
https://doi.org/10.25088/ComplexSystems.34.3.259