2005/07/05 by Marcus Pivato, Pivato, Marcus
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #37B15 (primary) #68Q80 (secondary)} #Cellular Automata and Applications #DNA and Biological Computing #Dynamical Systems (math.DS) #FOS: Mathematics #math.DS #msc:37B15 #msc:68Q80 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0507091
21 pages, 9 figures. Final version, to appear in Fundamenta Informatica, 2007
openalex publication_date 2005/07/05 · arxiv created 2007/02/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let L:=ZD be a D-dimensional lattice. Let AL be the Cantor space of L-indexed configurations in a finite alphabet A, with the natural L-action by shifts. A `cellular automaton' is a continuous, shift-commuting self-map F:AL-->AL. An `F-invariant subshift' is a closed, F-invariant and shift-invariant subset X of AL. Suppose x is an element of AL that is X-admissible everywhere except for some small region of L which we call a `defect'. Such defects are analogous to `domain boundaries' in a crystalline solid. It has been empirically observed that these defects persist under iteration of F, and often propagate like `particles' which coalesce or annihilate on contact. We use spectral theory to explain the persistence of some defects under F, and partly explain the outcomes of their collisions.