Cellular Automata Reversible Over Limit Set
Siamak Taaki
Reversibility of dynamics is a fundamental feature of nature, as it is currently believed that all physical processes are reversible in the ultimate microscopic scale. In this paper, we consider cellular automata (CA) whose dynamics are reversible when restricted to the limit set; i.e., those that obey reversibility in equilibrium. We exploit standard topological and combinatorial arguments to show that the limit set, in this case, is a mixing subshift of finite type (SFT), and is reached in finite time. In one dimensional case, any mixing SFT which contains at least one homogeneous configuration, may arise this way. We also discuss the decidability of two related algorithmic questions.