0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ You don't state a very specific question, so I'll just drop some links studying such ideas from different perspectives: arxiv.org/abs/2203.16226 (substitutions acting on Feldman space, as opposed to the standard idea of CA on Besicovitch space), hal.archives-ouvertes.fr/hal-01435026 (computational strength of CA with expansion/shrinking) hal.archives-ouvertes.fr/hal-02461469/document ("dill maps", a family containing substitutions, reverse substitutions and CA), arxiv.org/abs/1704.03916 (mapping class group of a subshift). $\endgroup$
    – Ville Salo
    Nov 29, 2022 at 11:26
  • 1
    $\begingroup$ But no, substitutions and desubstitutions are usually not CA. $\endgroup$
    – Ville Salo
    Nov 29, 2022 at 11:27
  • $\begingroup$ @VilleSalo Thanks again for the references and the helpful comments. So a unifying scheme for substitutions and CA's are dill maps, which I am at least now aware of. I guess the fact that there is a need for such a generalizing definition, indicates that they are not 'two sides of a coin'. $\endgroup$ Nov 29, 2022 at 13:36
  • $\begingroup$ Yet another PoV is transductions between $\zeta$ languages, i.e. you consider two-sided words up to shift relation. I don't have a good reference at hand though. All of these approaches are related, and are different solutions to the problem of not having a canonical way to pick the shift of the image of a substitution. $\endgroup$
    – Ville Salo
    Nov 29, 2022 at 13:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.