Cristopher Moore
Paper #: 95-09-080
By grouping several sites together into one, a cellular automaton can be transformed into another with more states and a smaller neighborhood; if the neighborhood has just two sites, we can think of the resulting CA rule as a binary operation. We show that if the blocked rule satisfies an identity which holds for a broad class of algebras, then the underlying rule must have essentially the same structure, and must depend only on its leftmost and rightmost inputs; roughly speaking, that the blocks’ transformation cannot turn a nonlinear rule into a linear one.