If M is a monoid (e.g. the lattice Z^D), and A is an abelian group, then A^M is a compact abelian group; a linear cellular automaton (LCA) is a continuous endomorphism F:A^M --> A^M that commutes with all shift maps. If F is diffusive, and mu is a harmonically mixing (HM) probability measure on A^M, then the sequence {F^N mu} (N=1,2,3,...) weak*-converges to the Haar measure on A^M, in density. Fully supported Markov measures on A^Z are HM, and nontrivial LCA on A^{Z^D} are diffusive when A=Z/p is a prime cyclic group. In the present work, we provide sufficient conditions for diffusion of LCA on A^{Z^D} when A=Z/n is any cyclic group or when A=[Z/(p^r)]^J (p prime). We show that any fully supported Markov random field on A^{Z^D} is HM (where A is any abelian group).

Marcus Pivato Reem Yassawi

If M is a monoid (e.g. the lattice Z^D), and G is a finite (nonabelian) group, then G^M is a compact group; a `multiplicative cellular automaton' (MCA) is a continuous transformation F:G^M-->G^M which commutes with all shift maps, and where nearby coordinates are combined using the multiplication operation of G. We characterize when MCA are group endomorphisms of G^M, and show that MCA on G^M inherit a natural structure theory from the structure of G. We apply this structure theory to compute the measurable entropy of MCA, and to study convergence of initial measures to Haar measure.

Marcus Pivato

If X is a discrete abelian group and B a finite set, then a cellular automaton (CA) is a continuous map F:B^X-->B^X that commutes with all X-shifts. If g is a real-valued function on B, then, for any b in B^X, we define G(b) to be the sum over all x in X of g(b_x) (if finite). We say g is `conserved' by F if G is constant under the action of F. We characterize such `conservation laws' in several ways, deriving both theoretical consequences and practical tests, and provide a method for constructing all one-dimensional CA exhibiting a given conservation law.

Marcus Pivato

Let M=Z^D be a D-dimensional lattice, and let A be an abelian group. A^M is then a compact abelian group; a `linear cellular automaton' (LCA) is a topological group endomorphism \Phi:A^M --> A^M that commutes with all shift maps. Suppose \mu is a probability measure on A^M whose support is a subshift of finite type or sofic shift. We provide sufficient conditions (on \Phi and \mu) under which \Phi `asymptotically randomizes' \mu, meaning that wk*lim_{J\ni j --> oo} \Phi^j \mu = \eta, where \eta is the Haar measure on A^M, and J has Cesaro density 1. In the case when \Phi=1+\sigma, we provide a condition on \mu that is both necessary and sufficient. We then use this to construct an example of a zero-entropy measure which is asymptotically randomized by 1+\sigma (all previously known examples had positive entropy).

Marcus Pivato Reem Yassawi

A `right-sided, nearest neighbour cellular automaton' (RNNCA) is a continuous transformation F:A^Z-->A^Z determined by a local rule f:A^{0,1}-->A so that, for any a in A^Z and any z in Z, F(a)_z = f(a_{z},a_{z+1}) . We say that F is `bipermutative' if, for any choice of a in A, the map g:A-->A defined by g(b) = f(a,b) is bijective, and also, for any choice of b in A, the map h:A-->A defined by h(a)=f(a,b) is bijective. We characterize the invariant measures of bipermutative RNNCA. First we introduce the equivalent notion of a `quasigroup CA', to expedite the construction of examples. Then we characterize F-invariant measures when A is a (nonabelian) group, and f(a,b) = a*b. Then we show that, if F is any bipermutative RNNCA, and mu is F-invariant, then F must be mu-almost everywhere K-to-1, for some constant K . We use this to characterize invariant measures when A^Z is a `group shift' and F is an `endomorphic CA'.

Marcus Pivato

If L=Z^D and A is a finite set, then A^L is a compact space. A cellular automaton (CA) is a continuous transformation F:A^L--> A^L that commutes with all shift maps. A quasisturmian (QS) subshift is a shift-invariant subset obtained by mapping the trajectories of an irrational torus rotation through a partition of the torus. The image of a QS shift under a CA is again QS. We study the topological dynamical properties of CA restricted to QS shifts, and compare them to the properties of CA on the full shift A^L. We investigate injectivity, surjectivity, transitivity, expansiveness, rigidity, fixed/periodic points, and invariant measures. We also study `chopping': how iterating the CA fragments the partition generating the QS shift.

Marcus Pivato

Let A:={0,1}. A `cellular automaton' (CA) is a shift-commuting transformation of A^{Z^D} determined by a local rule. Likewise, a `Euclidean automaton' is a shift-commuting transformation of A^{R^D} determined by a local rule. `Larger than Life' (LtL) CA are long-range generalizations of J.H. Conway's Game of Life CA, proposed by K.M. Evans. We prove a conjecture of Evans: as their radius grows to infinity, LtL CA converge to a `continuum limit' Euclidean automaton, which we call `RealLife'. We also show that the `life forms' (fixed points, periodic orbits, and propagating structures) of LtL CA converge to life forms of RealLife. Finally we prove a number of existence results for fixed points of RealLife.

Marcus Pivato

Let A^Z be the Cantor space of bi-infinite sequences in a finite alphabet A, and let sigma be the shift map on A^Z. A `cellular automaton' is a continuous, sigma-commuting self-map Phi of A^Z, and a `Phi-invariant subshift' is a closed, (Phi,sigma)-invariant subset X of A^Z. Suppose x is a sequence in A^Z 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.

Marcus Pivato

Let L:=Z^D be a D-dimensional lattice. Let A^L 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:A^L-->A^L. An `F-invariant subshift' is a closed, F-invariant and shift-invariant subset X of A^L. Suppose x is an element of A^L 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.

Marcus Pivato

Let L:= Z^D be the D-dimensional lattice and let A^L be the Cantor space of L-indexed configurations in some finite alphabet A, with the natural L-action by shifts. A `cellular automaton' is a continuous, shift-commuting self-map F of A^L, and an `F-invariant subshift' is a closed, F-invariant and shift-invariant subset X of A^L. Suppose x is a configuration in A^L that 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 F, and often propagate like `particles' which coalesce or annihilate on contact. We construct algebraic invariants for these defects, which explain their persistence under F, 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.

Marcus Pivato