Relation between symbolic substitution and cellular automata I think I have read somewhere that there is a connection between symbolic substitutions and cellular automata. I have some basic familiarity on the matter of symbolic substitutions, but I was wondering whether there is some free reference to such a relation?
I am interested for example whether one can say under mild conditions that every substitution is, or induces, a cellular automata?
 A: I'm not sure about this but I now think that the answer is no. I rely on these notes from the website of Jarkko Kari regarding cellular automata.
I am working with the definition of a substitution relying on an expanding\dilating map $D$ and a basic substitution rule $S_0$. More accurately,
$$ D:\mathbb{Z}^d\to \mathbb{Z}^d, \quad D(x_1,...,x_d):=\big(m_1 x_1,...,m_d x_d \big)$$
for some $m_1,...,m_d\in \mathbb{N}$ and $S_0: \mathcal{A}\to \mathcal{A}^{Q_{\mathbf{m}}}$, where $Q_\mathbf{m}:=\prod_{\ell=1}^d\{0, 1,....,m_\ell -1 \}$. So for $\omega \in \mathcal{A}^{\mathbb{Z}^d}$, we have $S(\omega)\in \mathcal{A}^{\mathbb{Z}^d}$ given by
$$ \big[S (\omega) \big] (\mathbf{k})= \Big[ S_0\big(\omega(\mathbf{k}_0)\big) \Big](\tilde {\mathbf{k} }), $$
where $\mathbf{k}_0\in \mathbf{m}\mathbb{Z}^d$ and $\mathbf{k}=\mathbf{k}_0+\tilde{\mathbf{k}}$.
By "Hedlund's theorem" in said lecture notes (Proposition 77), a map would have to commute as a diagram. i.e., $G\circ \mathcal{T}_g = \mathcal{T}_g\circ G$ where $G$ is the possible cellular automaton and $\mathcal{T}_g$ is the shift by $g\in \mathbb{Z}^d$. Hence a symbolic substitution map $S:\mathcal{A}^{\mathbb{Z}^d}\to \mathcal{A}^{\mathbb{Z}^d}$ would be a cellular automaton only if it commutes with all the shifts $\{ \mathcal{T}_g \}_{g\in \mathbb{Z}^d}$.
However, a substitution $S$ is defined as a composition of an expanding\dilating map $D$ and a basic substitution rule $S_0$ which satisfy
$$ S \big( \mathcal{T}_g(\omega) \big) = \mathcal{T}_{D(g)} \big( S(\omega) \big) \quad \text{for all} \quad g\in \mathbb{Z}^d. $$
For that reason whenever the dilating map is not the identity and $S(\omega)$ is not $D(g)-g$-periodic for all $g\in \mathbb{Z}^d$, $S$ will not be a cellular automaton since $\mathcal{T}_{D(g)} \big( S(\omega) \big)  \neq \mathcal{T}_g \big( S(\omega) \big)$. For example, if $S(\omega)$ is an aperiodic configuration which happens when $S$ defines an aperiodic subshift.
I'm not sure about this and would appreciate any input on this argument.
