I recently asked this on Math Stackexchange recently in this thread. I was told that there is a relation between symbolic substitutions and cellular automata. I'm vaguely familiar with Cobham's theorem, but I was wondering whether there is a possibly more direct relation. I will appreciate any input or directions on this question.
I believe that a substitution would generally not be cellular automaton. My substitution is given by 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"(Proposition 77 in these lecture notes by Jarkko Kari), 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. Though I am not sure of this reasoning.
It seems to me that under some conditions the desubstitution of $S$ would be a cellular automaton if it is well defined. For example, I think that $S^{-1}\vert_{S\big( \mathcal{A}^{\mathbb{Z}^d} \big)}$ should be a cellular automaton with a neighbourhood $Q_{2m}$ and the local rule coming from the substitution rule $S_0$.
Since I am newly acquainted to these topics, I thought that there may also be a more obvious connection which I missed. I would appreciate any references to any such results.
