Commutation of Cellular Automata Rules
Burton Voorhees
Faculty of Science, Athabasca University,
Box 10,000, Athabasca, AB T0G 2R0, Canada
Abstract
This paper addresses the following problem: Given a one-dimensional cellular automata (CA) defined over 
with a rule represented by an operator 
, determine all one-dimensional rules over which commute with . It is shown that the set of all such rules is given by the solution set of a system of nonlinear Diophantine equations. This result is generalized to cover cellular automata whose rules obey a relation first studied by Ito, and to the case of idempotent rules. Connections are shown between the results presented in this paper and work on the commuting block map problem [2--4], which is known to have significance for the study of Bernoulli shift systems.
