Article ID Journal Published Year Pages File Type
435485 Theoretical Computer Science 2009 10 Pages PDF
Abstract

Global functions of cellular automata on state spaces equipped with the Cantor topology are well characterized by the Curtis–Hedlund–Lyndon theorem. In this paper, we develop a characterization of global functions of cellular automata on Z, if the state space is equipped by Weyl and Besicovitch topology. The necessary and sufficient condition for a function to be the global map of a cellular automaton is (1) a strong localization property, a condition that strengthen Lipschitz continuity, (2) the set of (Cantor) periodic states are positively invariant and (3) the function commutes (in the Weyl/Besicovitch sense) with the shift operator.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics