Complex Systems

Algebraic Properties of the Block Transformation on Cellular Automata Download PDF

Cristopher Moore
Santa Fe Institute

Arthur A. Drisko
University of California, Berkeley

Abstract

By grouping sites together into one, a cellular automaton (CA) with radius can be transformed into one with a two-site neighborhood, which can be thought of as a binary algebra. It is shown that if this block algebra is in one of four large classes of algebras (commutative, associative with identity, inverse property loop, or anticommutative with identity) then the underlying rule only depends on its leftmost and rightmost inputs, and the block algebra is simply the direct product of copies of the underlying algebra. Therefore, although this algebraic approach to CA has been useful to some extent, complex rules on several-site neighborhoods cannot be expected to be equivalent to binary algebras with these simplifying properties.