Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Topological Dynamics of 2D Cellular Automata

Author(s): Guillaume Theyssier and Mathieu Sablik
Slot: Array, 11:20-11:40, col. 5


Topological dynamics of cellular automata (CA), inherited from
classical dynamical systems theory, has been essentially studied in
dimension 1. This paper focus on 2D CA and aims at showing that the
situation is different and more complex. The main results are the
existence of non sensitive CA without equicontinuous points, the
non-recursivity of sensitivity constants and the existence of CA
having only non-recursive equicontinuous points. They all show a
difference between the 1D and the 2D case.  Thanks to these new
constructions, we also extend undecidability results concerning
topological classification previously obtained in the 1D case.

websites: Arnold Beckmann 2008-05-18