Topological Dynamics of Cellular Automata: Dimension Matters |
| |
Authors: | Mathieu Sablik Guillaume Theyssier |
| |
Affiliation: | 1. LATP, UMR 6632??CNRS, Universit?? de Provence, CMI, Universit?? de Provence, Technop?le Chateau-Gombert, 39, rue F. Joliot Curie, 13453, Marseille Cedex 13, France 2. LAMA, UMR 5127??CNRS, Universit?? de Savoie, Campus Scientifique, 73376, Le Bourget-du-lac Cedex, France
|
| |
Abstract: | Topological dynamics of cellular automata (CA), inherited from classical dynamical systems theory, has been essentially studied in dimension 1. This paper focuses on higher dimensional CA and aims at showing that the situation is different and more complex starting from dimension 2. The main results are the existence of non sensitive CA without equicontinuous points, the non-recursivity of sensitivity constants, the existence of CA having only non-recursive equicontinuous points and the existence of CA having only countably many equicontinuous points. They all show a difference between dimension 1 and higher dimensions. Thanks to these new constructions, we also extend undecidability results concerning topological classification previously obtained in the 1D case. Finally, we show that the set of sensitive CA is only $varPi _{2}^{0}$ in dimension 1, but becomes $varSigma _{3}^{0}$ -hard for dimension 3. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|