Linear cellular automata, aperiodic order & invariant measures

The event is taking part on the Tuesday, Nov 27th 2018 at 15:30
Theme/s: Applied Mathematics
Location of Event: Alan Turing Building Room 306
This event is a: Public Seminar

Abstract: Cellular automata are dynamical systems where both time and space are discrete.
The rule determining the dynamics does not change over time, and is given by a local rule which outputs the future state of a cell as a function of the current states of the cells in its neighbourhood. One question which interests researchers is to what extent a specific cellular automaton is capable of universal computation, i.e.
whether it can simulate a universal Turing machine. A related question is to study the evolution of an initial condition under the cellular automaton over time. At one extreme, when does it converge to a random condition? At another, can it converge to a self similar condition? This question can be re-phrased in terms of measures, asking what measures are invariant under space (the horizontal shift map) and time (the cellular automaton map). Clearly, this would depend on the cellular automaton in question.

Linear cellular automata are a well studied family, which are tractable in the sense that it is possible to answer some of these questions for this family. In our study, the cells are labelled with Fp , the field of cardinality prime p, and initial condi- tions consist of bi-infinite sequences on Fp . The cellular automaton Ö is an Fp-linear map. A spacetime diagram U for Ö is a two-dimensional configuration such that the (n+1)-st row is the image of the n-th row under Ö. Each spacetime diagram defines a closed space X(U) of configurations that are invariant under horizontal or vertical shifting. A measure µ supported on X(U) which is invariant under the horizontal and vertical shifts yields a measure which is invariant under space and time.

We investigate the nature of spacetime diagrams of linear cellular automata with initial conditions that are p-automatic: these are sequences which exhibit aperiodic order. We show that the spacetime diagrams obtained are themselves automatic in nature, hence also exhibit aperiodic order. This gives us a methodology to produce, and compute, nontrivial closed sets and nontrivial measures that are invariant under both the shift map and the cellular automaton. We will compare our constructions to those defined and used by Kitchens, Schmidt and Einsiedler.

Report an error on this page

External Speakers

Reem Yassawi, (Lyon University)