Commuting Cellular Automata

Cristopher Moore and Timothy Boykett

Complex Systems 11 (1997) 55-64.

We study the algebraic conditions under which two cellular automata can commute. We show that if either rule is permutive, i.e. one-to-one on its leftmost and rightmost inputs, then the other rule can be written in terms of it; if either rule is a group, then the other is linear in it; and if either is permutive and affine, i.e. linear up to a constant, then the other must also be affine. We also prove some simple results regarding the existence of identities, idempotents (quiescent states) and zeroes (absorbing states).

Click here to download

Cris Moore <>