Representation of Additive Cylindrical Cellular Automata With Roots of Unity
Burton Voorhees
Binary valued additive cellular automata acting on strings of length n with periodic boundary conditions (cylindrical cellular automata) are represented in terms of the n-th roots of unity. This allows easy derivation of some standard results such as maximum tree heights, cycle periods, and conditions for states to be on cycles. New results are also presented: a method of partitioning the set of rules into classes with similar properties is developed, and the anomalous shift phenomenon in which a rule has maximum cycle period less than the theoretical maximum is explained. A conjecture to the effect that there are no non-trivial anomalous shift rules is put forward and refined with several examples and counter examples.
Keywords: Additive cellular automata, circulant matrices, roots of unity, anomalous shifts