Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Topological Dynamics of 2D Cellular Automata

Edit abstract data

Author(s): Guillaume Theyssier and Mathieu Sablik
Slot: Tue, 11:20-11:40, Room 19 (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 Valid HTML 4.01! Valid CSS!