Complex Systems

Cellular Automata as Algebraic Systems Download PDF

John Pedersen
Department of Mathematics, University of South Florida,
Tampa, Florida 33620-5700, USA


Infinite cellular automata have been studied mostly using empirical and statistical techniques, with some combinatorial analysis. Here we show how concepts of universal algebra such as subdirect decomposition and chains of varieties can be applied to their study. Cellular automata with ultimately periodic behavior are shown to correspond to varieties of groupoids. Relationships between these varieties are analyzed.