Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-30T23:12:38.250Z Has data issue: false hasContentIssue false

Algebraic invariants for crystallographic defects in cellular automata

Published online by Cambridge University Press:  28 November 2006

MARCUS PIVATO
Affiliation:
Department of Mathematics and Computer Science, Wesleyan University, Middletown, CT 06459-0128, USA and Department of Mathematics, Trent University, Peterborough, Ontario, Canada K9L 1Z6 (e-mail: [email protected], [email protected])

Abstract

Let ${\mathcal{A}}^{{\mathbb{Z}}^D}$ be the Cantor space of ${\mathbb{Z}}^D$-indexed configurations in a finite alphabet ${\mathcal{A}}$, and let $\sigma$ be the ${\mathbb{Z}}^D$-action of shifts on ${\mathcal{A}}^{{\mathbb{Z}}^D}$. A cellular automaton is a continuous, $\sigma$-commuting self-map $\Phi$ of ${\mathcal{A}}^{{\mathbb{Z}}^D}$, and a $\Phi$-invariant subshift is a closed, $(\Phi,\sigma)$-invariant subset ${\mathfrak{A}}\subset{\mathcal{A}}^{{\mathbb{Z}}^D}$. Suppose that ${\mathbf{a}}\in{\mathcal{A}}^{{\mathbb{Z}}^D}$ is ${\mathfrak{A}}$-admissible everywhere except for some small region that we call a defect. It has been empirically observed that such defects persist under iteration of $\Phi$, and often propagate like ‘particles’ which coalesce or annihilate on contact. We construct algebraic invariants for these defects, which explain their persistence under $\Phi$, and partly explain the outcomes of their collisions. Some invariants are based on the cocycles of multidimensional subshifts; others arise from the higher-dimensional (co)homology/homotopy groups for subshifts, obtained by generalizing the Conway–Lagarias tiling groups and the Geller–Propp fundamental group.

Type
Research Article
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)