## 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.