Spectral Domain Boundaries in Cellular Automata

Issue title: Special issue on DLT'04

Article type: Research Article

Authors: Pivato, Marcus

Affiliations: Dept. of Mathematics & Computer Science, Wesleyan University, Middletown CT, USA and Dept. of Mathematics, Trent University, Peterborough, Ontario, Canada. E-mail: [email protected]

Abstract: Let A^{Z^D} be the Cantor space of Z^D-indexed configurations in a finite alphabet A, and let σ be the Z^D-action of shifts on A^{Z^D}. A cellular automaton is a continuous, σ-commuting self-map Φ of A^{Z^D}, and a Φ-invariant subshift is a closed, (Φ, σ)-invariant subset u ⊂ A^{Z^D}. Suppose a ∈ A^{Z^D} is u-admissible everywhere except for some small region we call a defect. It has been empirically observed that such defects persist under iteration of Φ, and often propagate like 'particles' which coalesce or annihilate on contact. We use spectral theory to explain the persistence of some defects under Φ, and partly explain the outcomes of their collisions.

Keywords: Cellular automaton, subshift, defect, kink, domain boundary

Journal: Fundamenta Informaticae, vol. 78, no. 3, pp. 417-447, 2007