Commuting Cellular Automata
Cristopher Moore
Santa Fe Institute,
1399 Hyde Park Road,
Santa Fe, NM 87501
Timothy Boykett
Uni Linz,
A-4040 Linz, Austria
and
Time's Up,
Industriezeile 33B A-4020 Linz, Austria
Abstract
The algebraic conditions under which two one-dimensional cellular automata can commute is studied. It is shown that if either rule is permutive, that is, one-to-one in 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, that is, 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).
