Algebraic Properties of the Block Transformation on Cellular Automata
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.
