Discrete Baker Transformation for Binary Valued Cylindrical Cellular Automata

摘要

Recently, the discrete baker transformation has been defined for linear cellular automata acting on multi-dimensional tori with alphabet of prime cardinality. Here we specialize to binary valued cylindrical cellular automata and generalizing the discrete baker transformation to non-linear rules. We show that for a cellular automaton, defined on a cylinder of size n = 2~km with m odd, the equivalence classes of rules that map to the same rule under the discrete baker transformation fall into equivalence classes labeled by the set of 2~m cellular automata defined on a cylinder of size m. We also derive the relation between the state transition diagram of a cellular automata rule and that of its baker transformation and discuss cycle periods of the baker transformation for odd n.