Algebraic Properties of the Block Transformation on Cellular Automata

Cristopher Moore and Arthur Drisko

Complex Systems 10(3) (1996) 185-194

By grouping 2r sites together into one, a cellular automaton with radius r can be transformed into one with a two-site neighborhood, which can be thought of as a binary algebra. We show 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 2r copies of the underlying algebra. Therefore, although this algebraic approach to cellular automata has been useful to some extent, we cannot expect complex rules on several-site neighborhoods to be equivalent to binary algebras with these simplifying properties.

Click here to download.

Cris Moore <>