JCA HomeIssue Contents

Generalized Reversibility of Topological Dynamical Systems and Cellular Automata
Kuize Zhang and Lijun Zhang

In this paper, we characterize the reversibility of topological dynamical systems over the limit sets. We define a new concept of generalized inverse systems for topological dynamical systems, and prove that (i) a topological dynamical system has a generalized inverse system if and only if it is injective over its limit set and its limit set is reached in finite time, and (ii) if a topological dynamical system has a generalized inverse system, these two systems have the same topological entropy. For cellular automata (CAs), a particular class of topological dynamical systems, we prove some additional properties: (iii) A CA has a generalized inverse CA if and only if it is injective over its limit set. (iv) It is undecidable whether a given CA has a generalized inverse CA.

Keywords: Topological dynamical system, cellular automaton, generalized reversibility, limit set, topological entropy, undecidability, Drazin inverse

Full Text (IP)