Suppose we have a cellular automaton on $\mathbb Z^n$ with cell values in the finite set $V$, with update function $u : V^{\mathbb Z^n} \to V^{\mathbb Z^n}$, and similarly another cellular automaton on $\mathbb Z^m$ with values in $V'$, with update function $u' : V'^{\mathbb Z^m} \to V'^{\mathbb Z^m}.$

This is to say that $u$ and $u'$ are shift-invariant continuous maps on the infinite product spaces $V^{\mathbb Z^n}$ and $V'^{\mathbb Z^m}$, respectively.

Now suppose that $n > m$, and we have a map $\phi : V^{\mathbb Z^n} \to V'^{\mathbb Z^m}$ with the following properties:

  1. $\phi$ "commutes" with $u$ and $u'$: $\phi \circ u = u' \circ \phi$; and
  2. for any point $p \in \mathbb Z^m$, the map $f \mapsto \phi(f)(p)$ depends on only a finite number of values of $f$, i.e. there is some finite set $Q_p \subsetneq \mathbb Z^n$ such that $\phi(f)(p)$ is a function of $f|_{Q_p}$. (So $\phi$ is, in particular, continuous.)

(For convenience, assume that each $Q_p$ is minimal.)

Now, the question:

Question: Is it possible for $\phi$ to be injective? If not, do we actually have the stronger statement that any fiber $\phi^{-1}(f')$ of $\phi$ is either empty or infinite?

This seems similar in spirit to the statement that a continuous map from $\mathbb R^n$ to $\mathbb R^m$ with $n > m$ cannot be injective; here the notion of continuity is given by the above 2 properties on $\phi$.

  • $\begingroup$ I don't think such a $\phi$ can exist most of the time. $\endgroup$
    – mercio
    Jul 23, 2017 at 16:38
  • $\begingroup$ @mercio yeah, that's probably right. There are plenty of examples where $\phi$ can exist, though -- for example, if the transition rules $u$ and $u'$ are "simple enough" in the sense that $u(f)(p)$ depends only on $f(p + \tau)$ for some finite set of $\tau \in \mathbb Z^n$ which span an $m$-dimensional (or lower) subset. $\endgroup$
    – feralin
    Jul 23, 2017 at 16:55
  • $\begingroup$ :s i don't see how you would simulate a simple translation to the right on $\Bbb Z^2$ with a linear automaton. $\endgroup$
    – mercio
    Jul 23, 2017 at 17:05
  • $\begingroup$ @mercio sorry, I don't understand your comment. If $f : \mathbb Z^2 \to V$ is a state in a 2d automaton, then the transition rule (EDIT: $u$ instead of $\phi$) $u(f) = (x, y) \mapsto f(x - 1, y)$ is a simple translation to the right. What do you mean by a "linear automaton"? $\endgroup$
    – feralin
    Jul 23, 2017 at 17:08
  • $\begingroup$ I mean $u(f)(x,y) = f(x-1,y)$ and by linear automaton I mean $m=1$ and not $2$ so you can't do $\phi(f)(x,y) = f(x-1,y)$. By simulation with a linear automaton I mean a linear automaton transition function $v : V'^\Bbb Z \to V'^\Bbb Z$ and a simulation map $\phi$ $\endgroup$
    – mercio
    Jul 23, 2017 at 17:10

1 Answer 1


Yes, it is possible to construct cellular automata $u:V^{\mathbb{Z}^n}\to V^{\mathbb{Z}^n}$ and $u':V'^{\mathbb{Z}^m}\to V'^{\mathbb{Z}^m}$ and continuous bijection $\phi:V^{\mathbb{Z}^n}\to V'^{\mathbb{Z}^m}$ such that $\phi\circ u=u'\circ\phi$.

Let $V=V'=\{0,1\}$ and let $u$ and $u'$ be the maps (one on $V^{\mathbb{Z}^n}$, the other on $V'^{\mathbb{Z}^m}$) that turn every configuration to the all-$0$ configuration. Let $\gamma:\mathbb{Z}^n\to\mathbb{Z}^m$ be a bijection between $\mathbb{Z}^n$ and $\mathbb{Z}^m$ and set $\phi(f)(p):=f(\gamma^{-1}(p))$.

However, if you require that $\phi$ commutes with $\mathbb{Z}^m$-translations (in the spirit of cellular automata), then the answer becomes negative, because there is an entropy obstruction. More specifically, for each $i=(i_1,i_2,\ldots,i_m)\in\mathbb{Z}^m$, let us write $\overline{i}:=(i_1,i_2,\ldots,i_m,0,0,\ldots,0)\in\mathbb{Z}^m$. Denote by $\sigma^i$ and $\sigma^{\overline{i}}$ the translation maps on $V^{\mathbb{Z}^m}$ and $V'^{\mathbb{Z}^n}$ by vectors $i$ and $\overline{i}$, respectively. Then, provided $|V|,|V'|\geq 2$, there exists no continuous bijection $\phi$ such that $\phi\circ\sigma^{\overline{i}}=\sigma^i\circ\phi$ for each $i\in\mathbb{Z}^m$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .