2005/06/21 by Marcus Pivato, Pivato, Marcus
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #DNA and Biological Computing #math.DS #msc:37B15 #msc:68Q80 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0506417
37 pages, 9 figures, 3 tables
arxiv created 2007/02/14 · arxiv updated 2009/12/01
Let AZ be the Cantor space of bi-infinite sequences in a finite alphabet A, and let sigma be the shift map on AZ. A `cellular automaton' is a continuous, sigma-commuting self-map Phi of AZ, and a `Phi-invariant subshift' is a closed, (Phi,sigma)-invariant subset X of AZ. Suppose x is a sequence in AZ which is X-admissible everywhere except for some small region we call a `defect'. It has been empirically observed that such defects persist under iteration of Phi, and often propagate like `particles'. We characterize the motion of these particles, and show that it falls into several regimes, ranging from simple deterministic motion, to generalized random walks, to complex motion emulating Turing machines or pushdown automata. One consequence is that some questions about defect behaviour are formally undecidable.