Representing infinite words on cellular automata

Francesco Dolce, 11 Apr 2022

A cellular automaton is a dynamical system defined by an infinite set of symbols over an alphabet and a map, called local rule, that transforms every symbol of the string according to its neighbourhood. In this talk, we prove that, given an infinite word \(w\) satisfying some “nice” properties it is possible to construct a \(1\)-dimensional cellular automaton such that \(w\) is represented in a chosen column in its space-time diagram. We describe different cases, including when \(w\) is an automatic sequence or when \(w\) is a Sturmian word of quadratic slope.