Progress, gaps and obstacles in the classification of cellular automata
Milan Vispoel, Aisling J. Daly, Jan Baetens
Abstract
Classification is one of the most important problems in the theory of CA. For instance, assessing how CA design choices impact the generated dynamics requires an overview of the types of dynamics that can occur. Nevertheless, an overview and critical comparison that includes works from the last five years is currently lacking. This paper provides such a structured overview, where firstly classifications based on the CA’s rule table are considered, and secondly classifications based on the space–time pattern generated by a CA. The review indicates that most currently available classification schemes are limited to elementary cellular automata and highlights the existing dichotomy in CA research: theoretical research focusing on analytical results from topological dynamics and the theory of computation on the one hand, experimental research focusing on the statistical properties of the simulated space–time patterns on the other hand.