Propositional Logic and Cellular Automata on Monoids
Toshikazu Ishida, Shuichi Inokuchi and Yasuo Kawahara
This paper studies Cellular Automata with binary states on monoids making use of formulae in propositional logic, instead of local functions. Also we prove that the multiplication of formulae, defined by monoid action, determines the composition of transition functions of CA. This result converts the reversibility of transition functions to the reversibility of formulae. Several examples of reversible formulae are illustrated. Finally, introducing the Stone topology on configuration spaces, we give a neat proof of Hedlund’s theorem for CA.
Keywords: Cellular automata, monoids, propositional logic, reversibility, stone topology, Hedlund’s theorem.