The Complexity of Permutive Cellular Automata
Jung-Chao Ban, Chih-Hung Chang, Ting-Ju Chen and Mei-Shao Lin
This paper studies one-dimensional permutive cellular automata in two aspects: Ergodic and topological behavior. Through investigating measure theoretic entropy and topological pressure, we show that Parry measure is the unique equilibrium measure whenever the potential function depends on one coordinate. In other words, permutive cellular automata exhibit no phase transition. Furthermore, the existence of snap-back repellers for a cellular automaton infers Li-Yorke chaos and bipermutive cellular automata guarantee the subsistence of snap-back repellers.
Keywords: Cellular automata, permutive, equilibrium measure, phase transition, Parry measure, snap-back repeller, chaos